Linked list (list bertaut) adalah salah satu struktur data dasar yang sangat fundamental dalam bidang ilmu komputer. Dengan menggunakan linked list maka programmer dapat menimpan datanya kapanpun dibutuhkan. Linked list mirip dangan array, kecuali pada linked list data yang ingin disimpan dapat dialokasikan secara dinamis pada saat pengoperasian program (run-time).
Pada array, apabila programmer ingin menyimpan data, programmer diharuskan untuk mendefinisikan besar array terlebih dahulu, seringkali programmer mengalokasikan array yang sangat besar(misal 100). Hal ini tidak efektif karena seringkali yang dipakai tidak sebesar itu. Dan apabila programmer ingin menyimpan data lebih dari seratus data, maka hal itu tidak dapat dimungkinkan karena sifat array yang besarnya statik. Linked list adalah salah satu struktur data yang mampu menutupi kelemahan tersebut.
Secara umum linked list tersusun atas sejumlah bagian-bagian data yang lebih kecil yang terhubung (biasanya melalui pointer). Linked list dapat divisualisasikan seperti kereta, bagian kepala linked list adalah mesin kereta, data yang disimpan adalah gerbong, dan pengait antar gerbong adalah pointer.
-------- -------- --------
Mesin Data Data
-------- -------- --------
(kepala) ---> Pointer ---> Pointer --
-------- -------- --------
Programmer membaca data menyerupai kondektur yang ingin memeriksa karcis penumpang. Programmer menyusuri linked list melalui kepalanya, dan kemudian berlanjut ke gerbong (data) berikutnya, dan seterusnya sampai gerbong terakhir (biasanya ditandai dengan pointer menunjukkan alamat kosong (NULL)). Penyusuran data dilakukan secara satu persatu sehingga penyusuran data bekerja dengan keefektifan On. Dibandingkan array, ini merupakan kelemahan terbesar linked list. Pada array, apabilan programmer ingin mengakses data ke-n (index n), maka programmer dapat langsung mengaksesnya. Sedangkan dengan linked list programmer harus menyusuri data sebanyak n terlebih dahulu.
Jenis-Jenis Linked List
- Singly linked list
- Double linked list
- Circular Linked List
Adapaun linked list dapat di artikan sebagai berikut :
Linked List adalah struktur data yang berbeda dengan struktur data array. Linked list dapat dibayangkan seperti rantai yang bersambung satu sama lainnya. Tiap-tiap rantai (node) terhubung dengan pointer.
Gambar berikut memperlihatkan sebuah Linked List.
Sebelum kita membahas lebih jauh tentang Linked List, alangkah baiknya bila kita mengulang sedikit tentang struct dan typedef. Struct atau structure dalam bahasa pemograman C/C++ digunakan untuk mendefinisikan tipe data yang memiliki anggota (member) bertipe tertentu. Berikut contoh dan cara mendeklarasi sebuah struct:
struct tgl { int hari; int bulan; int tahun; } struct tgl Tanggal;
Bila divisualisasikan kira-kira sebagai berikut:
Contoh di atas memperlihatkan bagaimana mendeklarasi sebuah struct dengan nama struct tgl yang memiliki tiga member yaitu hari, bulan dan tahun yang bertipe int (integer). Kemudian, sebuah variabel Tanggal dideklarasikan bertipe struct tgl. Untuk mempersingkat dan menyederhanakan pendeklarasian sebuah struct, kata cadang typedef biasa digunakan. Sesuai namanya, typedef digunakan untuk mendefinisikan sebuah tipe data menjadi suatu alias tertentu. Perhatikan contoh berikut:
Dengan cara yang sama, pendeklarasian struct tgl di atas dapat disederhanakan menggunakan kata cadang typedef menjadi:
typedef struct tgl { int hari; int bulan; int tahun; } Date; Date Tanggal;
Single Linked List
Linked list dapat dianalogikan sebagai rantai yang terdiri dari beberapa node yang saling terkait. Dengan memegang node terdepan, maka node-node yang saling terkait lainnya dapat kita telesuri.
Dengan hanya mencatat atau memegang alamat dari alokasi data bertipe struct root pada sebuah variabel LL maka keberadaan node-node dalam linked list tersebut dapat diketahui. Bila data-data dalam node berupa bilangan bulat, maka struct yang diperlukan untuk membentuk linked list adalah sebagai berikut:
typedef struct node * NodePtr; typedef struct node { int data; NodePtr next; }Node;
typedef struct root { NodePtr head; unsigned size; }Root; Root LL; Penambahan Node Linked List
Bila setiap penambahan simpul pada linked list dilakukan pada bagian depan (paling dekat dengan head) maka kompleksitas yang diperlukan untuk menambah node baru dalam linked list konstan atau O(1). Penambahan sebuah node dengan nilai 3 pada linked list di atas dapat divisualisasikan sebagai berikut:
Penelusuran Node Linked List
Kompleksitas penelusuran (pencarian) node dalam linked list adalah linier atau O(n). Hal ini disebabkan karena node-node dalam linked list disusun secara acak (tidak berurut). Seandainya pun simpul-simpul dalam linked list disusun secara berurut, metode pencarian biner (binary search) tetap tidak dapat dipergunakan. Ada 2 alasan mengapa pencarian biner tidak dapat digunakan:
1. Linked list tidak memiliki indeks seperti array, sehingga akses langsung ke node tertentu tidak dapat dilakukan. Untuk menuju ke node tertentu, proses pemeriksaan tetap dimulai dari node head (node terdepan). Oleh karena itu proses pencarian selalu berjalan secara linier.
2. Tidak dapat membagi linked list menjadi 2 bagian yang sama besar seperti saat membagi array menjadi 2 bagian bila metode pencarian biner diaplikasikan pada array terurut.
Penghapusan Node Linked List
Sebelum proses penghapusan dilakukan, pencarian node yang ingin dihapus harus terlebih dahulu dilakukan. Bila node yang ingin dihapus ditemukan, suatu hal yang selalu harus diperhatikan adalah bagaimana mengeluarkan node tersebut dari linked list dan kemudian menyambung kembali linked list kembali. Kompleksitas menghapus sebuah node dalam linked list adalah O(n). Perhatikan gambar berikut ini:
Implementasi Linked List
typedef struct node * NodePtr; typedef struct node { int data; NodePtr next; }Node; typedef struct list { NodePtr head; unsigned size; }List; void initList(List *); int addList(List *, int); void displayList(List *); void freeList(List *); /* linkedlist.c: implementasi method dilakukan dalam file ini */ #include "linkedlist.h" #include #include void initList(List * lptr) { lptr->head = NULL; lptr->size = 0; } int addList(List * lptr, int data) { NodePtr new; new = malloc(sizeof(Node)); if(new == NULL) { printf("Error dalam membuat alokasi memori\n"); return 0; } new->data = data; new->next = lptr->head; lptr->head = new; lptr->size++; return 1; } void displayList(List * lptr) { NodePtr current = lptr->head; printf("\n"); while(current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("null\n"); } void freeList(List * lptr) { NodePtr next=lptr->head; NodePtr current=next; while(current != NULL) { next = current->next; free(current); current = next; } } /* main.c */ #include #include #include "linkedlist.h" int main(void) { int i, n, data; List LL; initList(&LL); /* Buat initial linked list */ printf("Jumlah simpul = "); scanf("%d", &n); /* Input data simpul */ for(i=0; i printf("Data = "); scanf("%d", &data); addList(&LL, data); } displayList(&LL); freeList(&LL); return EXIT_SUCCESS;
Compile program di atas dengan pernyataan berikut (diasumsikan OS linux digunakan):
%> gcc –Wall –pedantic –g –o mylist main.c linkedlist.c
Hasil kompilasi di atas akan membuat sebuah objek mylist (yang dibangkitkan dari dua file main.c dan linkedlist.c). Kemudian objek mylist tersebut dapat dijalan melalui command line.
