Linked List

Konsep dasar struktur data dinamis adalah alokasi memori yang dilakukan secara dinamis. Pada konsep ini, terdapat suatu struktur yang disebut dengan struktur referensi diri (self-referential structure), mempunyai anggota pointer yang menunjuk ke struktur yang sama dengan dirinya sendiri.

Struktur data dinamis sederhana dapat dibagi menjadi empat jenis, yaitu :

1. Linked list

2. Stack

3. Queue

4. Binary tree

Definisi ini dapat dituliskan secara sederhana dengan struktur :

struct node {

int info;

struct node *nextPtr;

}

Struktur ini mempunyai dua anggota, yaitu bilangan bulat info dan pointer nextPtr. Variabel pointer nextPtr ini menunjuk ke struktur bertipe struct node, yang sama dengan deklarasi induknya. Untuk membuat dan menangani struktur data dinamis dibutuhkan alokasi memori dinamis agar tersedia ruang bagi node-node yang ada. Fungsi malloc, free, dan operator sizeof banyak digunakan dalam alokasi memori dinamis ini.

Contoh :

typedef struct node NODE;

typedef NODE *NODEPTR;

NODEPTR newPtr = malloc (sizeof (NODE));

newPtr -> info = 15;

newPtr -> nextPtr = NULL;

Fungsi free digunakan untuk menghapus memori yang telah digunakan untuk node yang ditunjuk oleh pointer tertentu. Jadi free (newPtr); akan menghapus memori tempat node yang ditunjuk oleh newPtr.

DEFINISI LINKED LIST

Linked list adalah suatu cara untuk menyimpan data dengan struktur sehingga dapat secara otomatis menciptakan suatu tempat baru untuk menyimpan data yang diperlukan. Program akan berisi suatu struct atau definisi kelas yang berisi variabel yang memegang informasi yang ada didalamnya, dan mempunyai suatu pointer yang menunjuk ke suatu struct sesuai dengan tipe datanya. Struktur dinamis ini mempunyai beberapa keuntungan dibanding struktur array yang bersifat statis. Struktur ini lebih dinamis, karena banyaknya elemen dengan mudah ditambah atau dikurangi, berbeda dengan array yang ukurannya

bersifat tetap. Manipulasi setiap elemen seperti menyisipkan, menghapus, maupun menambah dapat dilakukan dengan lebih mudah.

Contoh :

//Program:link1.cpp

#include 

#include 

#include 

typedef struct nod {

int data;

struct nod *next;

} NOD, *NODPTR;

void CiptaSenarai(NODPTR *s)

{

*s = NULL;

}

NODPTR NodBaru(int m)

{

NODPTR n;

n = (NODPTR) malloc(sizeof(NOD));

if(n != NULL) {

n -> data = m;

n -> next = NULL;

}

return n;

}

void SisipSenarai (NODPTR *s, NODPTR t, NODPTR p)

{

if (p==NULL) {

t -> next = *s;

*s = t;

}

else {

t -> next = p -> next;

p ->next = t;

}

}

void CetakSenarai (NODPTR s)

{

NODPTR ps;

for (ps = s; ps != NULL; ps = ps -> next)

printf("%d -->", ps -> data);

printf("NULL\n");

}

int main ()

{

NODPTR pel;

NODPTR n;

CiptaSenarai(&pel);

n = NodBaru(55);

SisipSenarai(&pel, n, NULL);

Modul 6 Struktur Data (Arie) - 3

n= NodBaru(75);

SisipSenarai(&pel, n, NULL);

CetakSenarai(pel);

return 0;

}

Bila program dijalankan maka :

75->55->NULL

TEKNIK DALAM LINKED LIST

Pengulangan Linked List

Secara umum pengulangan ini dikenal sebagai while loop. Kepala pointer (head pointer) dikopikan dalam variabel lokal current yang kemudian dilakukan perulangan dalam linked list. Hasil akhir dalam linked list dengan current!=NULL. Pointer lanjut dengan current=current->next.

Contoh :

// Return the number of nodes in a list (while-loop version)

int Length(struct node * head) {

int count = 0;

struct node* current = head;

while (current != NULL) {

count++;

current=current->next;

}

return (count);

}

Mengubah Pointer Dengan Referensi Pointer

Banyak fungsi pada linked list perlu untuk merubah pointer kepala. Pointer ke pointer disebut dengan “reference pointer”.

Langkah utamanya dalam teknik ini adalah :

• Merancang fungsi untuk mengambil pointer ke pointer kepala. Untuk melewati pointer ke “value of interest” yang dibutuhkan untuk diubah. Untuk mengubah struct node*, lewati struct node**.

• Gunakan ‘&’ dalam panggilan untuk menghitung dan melewati pointer ke value of interest.

• Gunakan ‘*’ pada parameter dalam fungsi pemanggil untuk mengakses dan mengubah value of interest.

Contoh :

void ChangeToNull (struct node** headRef)

*headRef=NULL;

void ChangeCaller() {

struct node* head1;

struct node* head2;

ChangeToNull (&head1);

ChangeToNull (&head2);

}

Fungsi sederhana tersebut akan membuat pointer kepala ke NULL dengan menggunakan parameter reference.