LINKED LIST
Pengertian Linked
List
Salah satu bentuk struktur data, berisi kumpulan
data (node) yang tersusun secara sekuensial, saling sambung-menyambung, dinamis
dan terbatas.
Linked dapat divisualisasikan sebagai
rantai node, di mana setiap node menunjuk ke node
berikutnya.
Sebagai contoh :
Keterangan :
· Linked list berisi elemen tautan yang disebut pertama.
· Setiap link membawa bidang data dan bidang link yang disebut berikutnya.
· Setiap link ditautkan dengan link berikutnya menggunakan link berikutnya.
· link terakhir membawa link sebagai nol untuk menandai akhir daftar.
Tipe Linked List :
Linked list terdiri dari 2 macam yaitu :
1. Single Linked List
2. Double Linked List
Operasi yang biasanya ada di linked list adalah insert dan
delete.
Single
Linked List :
- Item hanya
memiliki 1 penghubung ke node lain.
- Insert operation
Untuk menyisipkan nilai baru, pertama-tama kita harus
mengalokasikan node baru dan
menetapkan nilai padanya lalu menghubungkannya
dengan linked list yang ada.
Biasanya insert sering disebut push.
Push merupakan sebuah operasi insert
dimana di dalam linked list terdapat 2 kemungkinan
insert yaitu insert
melalui depan (pushDepan) ataupun belakang (pushBelakang).
Operasi
pushDepan berarti data yang paling baru dimasukkan akan berada di depan
data
lainnya.
sebaliknya pushBelakang berarti data yang paling baru
akan berada di belakang data lainnya.
Representasinya adalah sebagai berikut:
pushDepan: 5, 3, 7, 9 maka hasilnya adalah: 9 ->7 ->3 -> 5 -> NULL
pushBelakang: 5, 3, 7, 9 maka hasilnya adalah: 5 ->3 ->7 ->9 -> NULL
yang ingin kita hapus, hapus, dan hubungkan daftar yang tertaut lainnya.
Delete operations sering disebut pop.
Pop merupakan operasi delete, dimana di dalam linked list memiliki 2 kemungkinan delete, yaitu
melalui depan (popDepan) dan melalui belakang (popBelakang).
PopDepan berarti data yang akan dihapus adalah data paling depan.
Ada 2 hal yang harus diperhatikan :
1. jika x ada di simpul kepala atau
2. jika x tidak dalam simpul kepala.
struct tnode *curr = head;
//
if x is in head node
if ( head->value == x ) {
head
= head->next;
free(curr);
}
//
if x is not in head node, find the location
else {
while
( curr->next->value != x ) curr = curr->next;
struct
tnode *del = curr->next;
curr->next
= del->next;
free(del);
}
DOUBLE LINKED LIST
- Items dapat diatur maju dan mundur.
struct
tnode {
int value;
struct tnode *next;
struct tnode *prev;
};
struct tnode *head = 0;
struct tnode *tail = 0;
Beberapa operasi yang ada di dalam sebuah doubly linked list pada dasarnya sama
dengan yang ada di dalam single linked list :
- Insert Operation
jika ingin menambahkan node di belakang tail
struct
tnode *node =
(struct tnode*) malloc(sizeof(struct tnode));
node->value = x;
node->next
= NULL;
node->prev
= tail;
tail->next
= node;
tail = node;
jika ingin menambahkan node di posisi tertentu (antara head dan tail)
struct
tnode *a = ;
struct
tnode *b = ;
// the new node will be inserted between
a and b
struct
tnode *node =
(struct tnode*)
malloc(sizeof(struct tnode));
node->value = x;
node->next = b;
node->prev = a;
a->next = node;
b->prev = node;
- Delete Operation / pop
Ada 4 kondisi yang harus kita perhatikan saat menghapus:
1. Node yang akan dihapus adalah satu-satunya node dalam linked list.
2. Node yang akan dihapus adalah head.
3. Node yang akan dihapus adalah tail.
4. Node yang akan dihapus bukan head atau tail.
• Jika node yang akan dihapus hanya satu-satunya node
free(head);
head = NULL;
tail = NULL;
• Jika node yang akan dihapus hanya head:
head = head->next;
free(head->prev);
head->prev = NULL;
• Node yang akan dihapus adalah tail.
tail = tail->prev;
free(tail->next);
tail->next = NULL;
• Node yang akan dihapus bukan head atau tail.
struct
tnode *curr = head;
while ( curr->next->value != x ) curr =
curr->next;
struct tnode *a = curr;
struct tnode *del = curr->next;
struct tnode *b = curr->next->next;
a->next = b;
b->prev = a;
free(del);
Referensi :
https://socs.binus.ac.id/2017/03/15/doubly-linked-list/
https://socs.binus.ac.id/2017/03/15/single-linked-list/
https://www.tutorialspoint.com/data_structures_algorithms/linked_list_algorithms.htm
