Universitas Syiah Kuala MMA-041 Struktur Data
Dynamic Linked List Dr. Taufik Fuadi Abidin, M.Tech
[email protected]
Single Linked List Linked list dapat dianalogikan sebagai rantai besi yang terdiri dari beberapa besi bulatan yang saling terhubung. Dengan mengingat atau memegang bulatan besi yang terdepan, maka bulatan-bulatan besi yang saling terkait lainnya dapat ditelusuri. Berikut adalah ilustrasi dari sebuah single linked list.
head
5
15
6
NULL
LL =
Dengan hanya mencatat atau memegang alamat dari alokasi data bertipe struct root pada sebuah variabel LL maka keberadaan simpul-simpul dalam linked list tersebut dapat dijaga. Bila data-data dalam node berupa bilangan bulat maka deklarasi struct yang diperlukan untuk membentuk linked list di atas adalah: typedef struct node * NodePtr; typedef struct node { int data; NodePtr next; }Node; typedef struct root { NodePtr head; unsigned size; }Root; Root LL;
Penambahan Simpul (Node) Bila disepakati bahwa setiap penambahan simpul pada linked list dilakukan pada bagian depan (paling dekat dengan head) maka jumlah biaya (complexitas) untuk penambahan simpul adalah konstan atau O(1). Sebagai contoh, penambahan sebuah simpul dengan nilai 3 pada linked list di atas dapat divisualisasikan sebagai berikut:
Struktur Data Author: Taufik Fuadi Abidin
2
head
5
15
6
NULL
LL =
Buat simpul baru dan masukkan datanya
3
Kemudian, atur kembali susunan linked list menjadi: head
5
15
6
3
5
15
NULL
LL =
3
Atau: head
6
LL = NULL
Pencarian Simpul Pencarian simpul dalam sebuah single linked list harus dilakukan secara linier. Kompleksitas pencarian sebuah simpul dalam linked list adalah O(n). Hal ini disebabkan karena simpul-simpul dalam linked list biasanya dikait secara tidak berurut. Seandainya pun linked list disusun secara terurut, metode pencarian biner (binary search) tetap tidak dapat diaplikasikan karena: 1. Linked list tidak memiliki indeks sehingga akses langsung ke simpul tertentu tidak dapat dilakukan. Untuk menuju ke simpul tertentu, proses pemeriksaan tetap dimulai dari simpul head (sisi depan linked list). 2. Tidak dapat membagi linked list menjadi 2 bagian yang sama besar seperti membagi array menjadi 2 bagian yang sama pada saat metode pencarian biner diaplikasikan pada array yang terurut.
Struktur Data Author: Taufik Fuadi Abidin
3
Penghapusan Simpul Sebelum sebuah simpul dihapus, pencarian terhadap simpul tersebut harus dilakukan terlebih dahulu. Bila simpul tersebut ditemukan dalam linked list, simpul tersebut harus dikeluarkan dan keterkaitan antar simpul dalam linked list harus diatur kembali. Kompleksitas untuk menghapus sebuah simpul dalam single linked list adalah O(n). Perhatikan contoh berikut ini:
head
3
5
15
6
LL =
NULL
Bila simpul 15 dihapus maka susunan linked list menjadi: head
3
5
15
6
LL = NULL
Implementasi Single Linked List (Sekaligus Bahan Praktikum) /* Program berikut disimpan dalam file linkedlist.h */ typedef struct node * NodePtr; typedef struct node { int data; NodePtr next; }Node;
Struktur Data Author: Taufik Fuadi Abidin
4
typedef struct list { NodePtr head; unsigned size; }List; void initList(List *); int addList(List *, int); void displayList(List *); void freeList(List *);
Prototype function ditulis disini
/* Program berikut disimpan dalam file linkedlist.c */ #include "linkedlist.h" #include <stdlib.h> #include <stdio.h> 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 mengalokasi 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; Struktur Data Author: Taufik Fuadi Abidin
5
} printf("null\n"); } void freeList(List * lptr) { NodePtr next=lptr->head; NodePtr current=next; while(current != NULL) { next = current->next; free(current); current = next; } }
/* Program berikut disimpan dalam file main.c */ #include <stdlib.h> #include <stdio.h> #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
Struktur Data Author: Taufik Fuadi Abidin
6
Compile program tersebut dengan cara berikut ini (diasumsikan anda menggunakan OS Linux): gcc –Wall –pedantic –g –o mylist main.c linkedlist.c
Hasil kompilasi di atas akan membuat sebuah file mylist (dibangkitkan dari dua buah file yaitu: main.c dan linkedlist.c). Selanjutnya, file mylist tersebut dapat dijalankan melalui prompt dengan perintah: mylist
Perhatikan dan pahami keluaran dari implementasi linked list tersebut dan diskusikan dengan teman.
Struktur Data Author: Taufik Fuadi Abidin
7
