Linked List adalah struktur data yang terdiri dari urutan record data dimana setiap record memiliki field yang menyimpan alamat dari record selanjutnya.
- Linked List lebih efisien dalam penggunaan memori, karena ketika kita hendak menyimpan data, baru kemudian dia akan meminta memorinya.
- Linked List akan mendukung bentuk struktur data yang lain
Ada beberapa macam Linked List yaitu :
1. Single Linked List
2. Circular Single Linked List
3. Double Linked List
4. Circular Double Linked List
5. Header Linked List
Single
Linked List
Single Linked List = Menggunakan sebuah variabel pointer dan Pointer next nya menunjuk ke
node selanjutnya.
Nodes = Objek yang mereferensikan dirinya sendiri
Syntax :
struct tnode{
int value;
struct tnode *next;
};
struct tnode *head =0;
- Single Linked List : Insert
Untuk insert ada 4 macam cara :
1. Didepan (head)
Syntax :
struct tnode * node =
(struct tnode*) malloc (sizeof(struct tnode) );
node -> value = x; //Berarti kita isi variable value yang ada di node yang baru
node -> next = head;
head = node;
2. Dibelakang (tail)
3. Ditengah (Setelah node yang kita tentukan)
4. Ditengah (Sebelum node yang kita tentukan)
- Single Linked List : Delete
Ada 2 kondisi yang harus kita perhatikan : Jika x ada didepan node / x tidak ada didepan node
Syntax :
struct tnode *curr = head;
//Jika x ada dibagian depan node
if(head -> value == x){
head = head -> next; //Maka head akan pindah ke sebelahnya
free(curr);
}
//Jika x ada dibagian belakang node
else if(tail -> value == x ){
while (curr -> next !=tail) curr = curr-> next;
free(tail); tail = curr;
tail -> next = NULL;
}
//Jika x tidak ada di depan node, cari lokasinya
else{
while(curr -> next -> value != x) curr = curr -> next;
struct tnode *del = curr -> next;
curr -> next = del -> next;
free(del);
}
Polynomial Representation
Contoh :
Polynomial p(x) = p(x) = 8x5 + 7x6 + 4x2 + 8. Secara khusus, polynomial dibagi menjadi 2 bagian
yaitu Koefisien dan Eksponen dari suku yang bersangkutan. Maka dapat direpresentasikan seperti
berikut :
| 8 | 5 | | -> | 7 | 6 | | -> | 4 | 2 | | -> | 8| 0 | x |
Circular Single Linked List
Circular Single Linked List = Single Linked List
yang pointer nextnya menunjuk pada dirinya
sendiri.
- Jika terdiri dari beberapa node, maka pointer next pada node terakhir akan menunjuk ke node
terdepannya sehingga Linked List tersebut berputar.
- Node terakhir akan menunjuk lagi ke head.
Double Linked List
Double Linked List = Memiliki 2 variabel pointer yaitu pointer yang menunjuk ke node selanjutnya
dan pointer yang menunjuk ke node sebelumnya
Syntax :
struct tnode{
int value;
struct tnode *next;
strcut tnode *prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;
- Double Linked List : Insert
Pertama, kita harus mengalokasi node baru dan memberikan nilai kepadanya. Lalu kita hubungkan
node tersebut dengan Linked List yang sudah ada
Syntax :
struct tnode *node =
(struct tnode*) malloc (sizeof(struct tnode) );
node -> value = x;
node -> next = NULL;
node -> prev = tail
tail -> next = node;
tail = node;
- Double Linked List : Delete
Ada 4 kondisi yang perlu diperhatikan ketika "Delete":
1. Kondisi jika Node tersebut hanya satu - satunya di Linked List
Syntax :
free(head);
head = NULL;
tail = NULL;
2. Kondisi jika Node ada di Head
Syntax :
head = head -> next;
free (head -> prev);
head -> prev = NULL;
3. Kondisi jika Node ada di Tail
Syntax :
tail = tail -> prev;
free (tail -> next);
tail -> next = NULL;
4. Kondisi jika Node tidak di Head / Tail
Syntax :
struct tnode *curr = head;
while(curr -> next -> value != x) curr = curr -> next;
struct tnode *a = curr;
struct tnode *del = curr -> next;
a -> next = b;
b -> prev = a;
free(del);
Circular Double Linked List
Circular Double Linked List = Terdapat node yang memiliki 3 field, yaitu 1 field pointer
yang
menunjuk pointer berikutnya (next), 1 field menunjuk pointer sebelumnya
(prev), serta sebuah field
yang berisi data untuk node tersebut.
Header Linked List
Header Linked List = Header spesial yang
terdiri dari node headernya. Jadi Linked List tersebut
tidak menunjuk pada
node pertama (head) namun hanya menyimpan alamat dari node headernya.
Contoh Tanpa Header Node:
L : | | -> | ant | | -> | bat | | -> | cat | \ |
Contoh dengan Header Node :
L : | | -> | | | -> | ant | | -> | bat | | -> | cat | \ |
