Dinamik Linked List Pendahuluan Pada pertemuan ini, kita akan membahas struktur data Linked List (senarai berantai) yang berbeda dengan struktur data array. Tetapi sebelum itu, akan direview sedikit mengenai penggunaan struct serta typedef dalam C sehingga saat membahas Linked List serta pemrogramannya tidak mengalami kesulitan. Tujuan dari materi ini adalah mengajarkan struktur data Linked List dan bagaimana membentuknya. Selain itu, proses penyisipan, penghapusan dan pencarian simpul (node) dalam struktur data ini juga akan dibahas secara detail. Struct Struct atau structure dalam C digunakan untuk membentuk tipe data dengan anggota (member) dengan tipe data tertentu. Berikut cara deklarasi dari sebuah struct: struct tgl { int hari; int bulan; int tahun; } struct tgl Tanggal;
Bila divisualisasikan kira-kira sebagai berikut:
Tanggal =
hari bulan tahun
struct tgl
Contoh di atas memperlihatkan bagaimana mendeklarasi sebuah struct dengan nama struct tgl yang memiliki tiga member bertipe int yaitu hari, bulan dan tahun. Kemudian sebuah variabel Tanggal dibuat bertipe struct tgl. Untuk mempersingkat dan menyederhanakan pendeklarasian sebuah struct, kata cadang typedef dapat digunakan. Sesuai namanya, typedef digunakan untuk mendefinisikan sebuah tipe data menjadi suatu alias tertentu. Perhatikan contoh berikut: Kata cadang typedef Type data typedef int Integer; Integer i,j,k; alias
Dengan cara yang sama, pendeklarasian struct tgl di atas dapat disederhanakan menggunakan kata cadang typedef. Perhatikan statemen berikut ini:
Struktur Data Author: Dr. Taufik Fuadi Abidin, M.Tech
1 www.informatika.unsyiah.ac.id/tfa
typedef struct tgl { int hari; int bulan; int tahun; } Date; Date tanggal;
Single Linked List (Senarai Berantai Tunggal) 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 kita jajaki. Berikut ilustrasi dari sebuah linked list.
LL =
head
5
15
6
NULL
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 Pada Single Linked List 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: LL =
head
5
Buat simpul baru dan masukkan datanya
15
6
NULL
3
Kemudian, atur kembali susunan linked list menjadi:
Struktur Data Author: Dr. Taufik Fuadi Abidin, M.Tech
2 www.informatika.unsyiah.ac.id/tfa
LL =
head
5
15
6
NULL
3
Atau:
LL =
head
3
5
15
6 NULL
Pencarian Simpul Pada Single Linked List Pencarian simpul dalam sebuah single linked list harus dilakukan secara linier atau O(n). Hal ini disebabkan karena simpul-simpul dalam linked list biasanya disusun secara tidak berurut. Dan 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, 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). Oleh karena itu proses pencarian selalu berjalan secara linier. 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 terurut. Penghapusan Simpul Pada Single Linked List Sebelum proses penghapusan dilakukan, proses pencarian simpul yang ingin dihapus harus terlebih dahulu dilakukan. Bila simpul yang ingin dihapus ditemukan, suatu hal yang selalu harus diperhatikan adalah bagaimana mengeluarkan sebuah simpul dalam linked list kemudian menyambung linked list tersebut kembali. Jumlah biaya yang diperlukan untuk menghapus sebuah simpul dalam single linked list adalah O(n). Bila diketahui sebuah linked list tersusun dalam susunan seperti pada gambar berikut ini:
LL =
head
3
5
15
6 NULL
Bila simpul dengan nilai 15 dihapus maka susunan linked list menjadi:
LL =
head
3
5
15
6 NULL
Struktur Data Author: Dr. Taufik Fuadi Abidin, M.Tech
3 www.informatika.unsyiah.ac.id/tfa
/* Program berikut disimpan dalam file linkedlist.h */ 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 *);
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 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; Struktur Data Author: Dr. Taufik Fuadi Abidin, M.Tech
4 www.informatika.unsyiah.ac.id/tfa
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
Kompile program di atas dengan menulis perintah berikut pada C prompt: 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 langsung melalui prompt dengan perintah: mylist
Struktur Data Author: Dr. Taufik Fuadi Abidin, M.Tech
5 www.informatika.unsyiah.ac.id/tfa
