Singular Linked List dan Double Linked List
Linked List
Rangkuman Single Linked
List dan Double Linked List
A.
Pointer
Dalam data structure,
kita menggunakan fungsi pointer. Untuk itu kita harus lebih mengerti dulu
tentang pointer. Pointer bisa dikatakan sebagai penunjuk. Yang ditunjuk ialah
suatu alamat memori dari suatu tipe data. Jadi bisa dikatakan pointer ialah
suatu variabel yang berisi alamat memori dari suatu variabel, yang bertujuan
agar alamat dari variable tersebut dapat diketahui dengan mudah. Contoh pemakaian di bahasa C:
int angka=10;
int *ptr=&angka;
printf(“%d”, *ptr);
Outputnya = 10;
Hal ini dikarenakan
pointer tersebut menyimpat alamat memori dari integer angka, dan memunculkan
nilai dari variable alamat memorinya disimpan.
B.
Single atau Single
Linked List
Suatu struktur data yang
berisi urutan record data dimana setiap record memiliki field untuk menyimpan
alamat record selanjutnya. Nama lain dari record yang terhubung ialah node.
Setiap node memiliki dua bagian, bagian pertama untuk value dan kedua untuk
menyimpan alamat node lain. Untuk lebih jelasnya lihat gambar berikut :
Dalam membuat algoritma singly linked list kita harus
membuat empat pointer global, yakni *next, *head, *curr, dan *tail. Mungkin
butuh pointer lain, tapi pointer tersebut tidak harus global. Contoh coding di
bahasa C nya :
struct node{
int
value;
struct
node *next;
}*head, *curr, *tail;
Untuk pointer head digunakan sebagai kepala atau
bagian ujung dari suatu linked list. Head harus node pertama dari linked list
dan pointer head tidak bisa berpindah pindah seenaknya. Untuk ponter curr sebagai
node yang mudah untuk berpindah-pindah apabila mau menggunakan fungsi insertion
dan deletion. Untuk pointer tail digunakan sebagai node terakhir atau node
paling belakang. Kalau untuk single linked list pointer tail menunjuk ke NULL
atau node yang kosong. Dalam linked list di bahasa C untuk menghubungkan suatu
node ke node lain menggunakan simbol node->valu=value.
Dalam single atau singly linked list terdapat fungsi yang
bisa kita gunakan yakni insertion (push) dan deletion (pop). Fungsi dari
insertion untuk menambahkan suatu node pada linked list. Sedangkan fungsi deletion
untuk menghilangkan atau menghapus suatu node. Untuk insertion sendiri dibagi
menjadi tiga yakni sebagai berikut :
1.
Insertion at the
head (push head)
Insertion ini menambahkan node pada bagian depan suatu
linked list. Jadi head yang berada pada node tersebut berpindah ke node yang diinsert.
Setelah kita memindahkan headnya, kita harus membuat linked tersebut terhubung.
2.
Insertion at the
mid or specific position (push mid)
Insertion ini menambahkan atau menyisipkan node pada bagian
tengah suatu linked list. Untuk menyisipkan node tersebut kita memerlukan
pointer temporary yang dibuat lokal variabel. Intinya setelah kita menyisipkan
node tersebut, pastikan node tersebut bisa terhubung.
3.
Insertion at the
tail (push tail)
Insertion ini menambahkan node pada bagian belakang (tail)
suatu node. Jadi, tail yang tadinya berada pada node tersebut sekarang berada
pada node yang baru. Pastikan juga bahwa semua node tersebut terhubung.
Untuk fungsi deletion juga diba tiga, yakni sebagai
berikut :
1.
Deletion at the
head (pop head)
Deletion ini ialah menghapus node pada bagian head
atau node paling depan, sehingga node head berpindah ke node yang selanjutnya
atau node next. Pastikan juga node yang dihapus kita free kan agar memorinya
tidak tertinggal dan pastikan juga linked listnya terhubung.
2.
Deletion at the
mid (pop mid)
Deletion ini ialah menghapus suatu node pada bagian
tengah linked list, sehingga memerlukan pointer lokal baru (node *temp) untuk
memudahkan. Pastikan node yang dihapus kita free kan agar memorinya tidak
menumpuk dan pastikan linked list itu tetap terhubung.
3.
Deletion at the
tail (pop tail)
Deletion ini ialah menghapus suatu node pada bagian
belakang linked list atau node tail. Jadi node tail yang tadinya di node paling
belakang linked list, berpindah ke node yang sebelumnya. Pastika node yang
dihapus kita free kan agar tidak ada memori yang menumpuk dan pastikan juga linked
list tersebut masih terhubung.
C.
Circular Single
atau Singly Linked List
Sebenarnya konsep dari
circular single linked list tidak terlalu beda dengan single linked list, biasanya
node tail menunjuk pada NULL atau node kosong, namun node tail pada circular single
linked list menunjuk kepada node head atau paling depan. Sehingga di linked
list ini tidak ada node kosong atau NULL. Berikut ilustrasinya :
D.
Double Linked List
Sebenarnya pengertian
double linked list mirip dengan single linked list, hanya saja perbedaannya,
apabila double ia mempunyai dua tangan atau dua pointer, yakni pointer prev dan
pointer next. Berikut contoh codingan dalam C :
struct node{
int value;
struct node *prev, *next;
}*head, *curr, *tail;
struct node(int value){
node *temp=(node*)malloc(sizeof(node));
temp->value=value;
temp->next=temp->prev=NULL;
head=tail=NULL;
return temp;
return temp;
}
Untuk fungsinya juga sama,
yakni insertion dan deletion. Insertion juga dibagi tiga sebagai berikut :
1.
Insertion at the
head atau Push head
2.
Insertion at the mid
atau Push mid
3.
Insertion at the tail
atau Push tail
Untuk deletion juga ada tiga, yakni sebagai berikut :
1.
Deletion at the
head atau Push head
2.
Deletion at the
mid atau Push mid
3.
Deletion at the
tail atau Push tail
Sebagai catatan untuk
double linked list, algoritma yang digunakan agak ribet karena terdapat dua
pointer yang digunakan, dimana apabila ingin menginsert atau mendelet sesuatu, pointer
prev dan next harus saling berhubungan. Dan juga pastikan head selalu di depan
dan tail selalu di belakang. Berikut adalah ilustrasi double linked list :
E.
Circular Double
Linked List
Konsep dari circular
double linked list tidak jauh beda dengan double linked list, karena perbedaan
nya terletak pada node head dan tail. Untuk node head pointer prev biasanya
menunjuk pada NULL, namun pada circular menunjuk pada node tail. Sedangkan node
tail pointer next nya biasanya menunjuk pada NULL, namun pada circular menunjuk
pada node head. Jadi, untuk circular double linked list tidak ada node yang kosong
atau NULL. Berikut adalah ilustrasinya :
Referensi :
https://www.coursehero.com/file/20781416/Pengertian-Pointer/
Comments
Post a Comment