Linked List

Linked list merupakan suatu bentuk penggunaan pointer dan struct dalam bahasa pemrograman C. Linked list berfungsi untuk menyimpan data seperti pada array of structs. Bedanya, array diletakkan pada memory secara berurutan, sementara linked list dapat ditempatkan secara sembarang dalam memory selama node-nodenya saling terkait. Untuk menggunakan linked list dengan struct, kita bisa membuat struct seperti di bawah ini.

typedef struct LinkedList {
int i;
LinkedList *next;
};

Dalam struct LinkedList tersebut ditambahkan variabel pointer *next dengan tipe data LinkedList untuk menunjuk ke node berikutnya dari linked list tersebut. Untuk menggunakan linked list dari struct tersebut, kita bisa membuat program seperti ini.

int main () {
LinkedList *head, *temp, *node;
int i;

head = NULL;
do {
scanf("%d", &i);

if (head == NULL) {
node = (LinkedList*) malloc (sizeof (LinkedList));
node->next = NULL;
node->i = i;
head = node;
temp = head;
}

else {
temp = head;
while (temp->next != NULL) temp = temp->next;

node = (LinkedList*) malloc (sizeof (LinkedList));
node->next = NULL;
node->i = i;
temp->next = node;
}
} while (i != 0);

temp = head;
while (temp != NULL) {
printf("%d\n", temp->i);
temp = temp->next;
}

getchar();
temp = head;
while (head != NULL) {
head = head->next;
free(temp);
temp = head;
}
return 0;
}

Karena variabel-variabel yang dideklarasikan untuk tipe data LinkedList berupa pointer, gunakan function malloc untuk mengalokasikan memory yang akan ditunjuk oleh variabel pointer tersebut. Untuk dapat menggunakan function malloc, jangan lupa meng-include stdlib.h atau malloc.h pada source code. Pada saat node dibuat, pastikan node->next = NULL agar node->next tidak menunjuk ke sembarang alamat dalam memory.

Jika linked list sudah tidak digunakan, gunakan function free untuk membebaskan alamat-alamat memory yang digunakan untuk linked list, karena jika tidak dibebaskan maka akan terjadi memory leak, di mana alamat-alamat memory yang seharusnya sudah tidak digunakan lagi tidak dibebaskan oleh program sehingga alamat-alamat tersebut tidak dapat digunakan oleh program lainnya.

Dengan C++, linked list dapat dibuat dengan menggunakan class sebagai pengganti struct dan keyword new & delete sebagai pengganti function malloc & free. Classnya bisa kita buat seperti ini.

class LinkedList {
public:
int i;
LinkedList *next;
};

Seperti pada struct LinkedList tadi, class LinkedList ini punya sebuah pointer yang menggunakan tipe data LinkedList. Di bawah ini program yang sama dengan yang kita buat tadi, tetapi dengan menggunakan class LinkedList untuk membuat linked list-nya dengan menggunakan bahasa C++.

int main () {
LinkedList *head, *temp, *node;
int i;

head = NULL;
do {
cin>>i;

if (head == NULL) {
node = new LinkedList;
node->next = NULL;
node->i = i;
head = node;
temp = head;
}

else {
temp = head;
while (temp->next != NULL) temp = temp->next;

node = new LinkedList;
node->next = NULL;
node->i = i;
temp->next = node;
}
while (i != 0);

temp = head;
while (temp != NULL) {
cout<<temp->i<<endl;
temp = temp->next;
}

getchar();
temp = head;
while (head != NULL) {
head = head->next;
delete temp;
temp = head;
}
return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s