Linked list
A. Linked list
Linked List
adalah suatu struktur data linier. Berbeda dengan array yang juga merupakan
struktur data linier dan tipe data komposit, linked list dibentuk secara
dinamik. Pada saat awal program dijalankan elemen linked list belum data. Elemen
linked list (disebut node) dibentuk sambil jalan sesuai instruksi. Apabila
setiap elemen array dapat diakses secara langsung dengan menggunakan indeks,
sebuah node linked list diakses dengan menggunakan pointer yang mengacu
(menunjuk) ke node tersebut. Linked List
merupakan bangunan data yang paling sederhana dan paling biasa, dan
dipergunakan untuk melaksanakan banyak struktur data abstrak yang penting,
seperti stacks (tumpukan-tumpukan), queues (antrian), hash tables, symbolic
expressions, skip list (melewati daftar), dan banyak lagi.
Kelebihan linked list dengan
array konvensional yaitu apabila perintah data yang dimaksudkan berbeda dengan
perintah data yang disimpan di memori atau di disk, linked list membolehkan
sisipan dan pemindahan nodes di titik yang mana pun di daftar, dengan jumlah
terus-menerus pelaksanaan. Di pihak yang lain, linked list sendiri tidak
membolehkan akses acak ke data, atau bentuk yang mana pun untuk mengindeks.
Dengan begitu, banyak dasar pelaksanaan seperti mendapatkan data yang terakhir
dari node daftar, atau menemukan node itu berisi data yang dimasukan, atau
menemukan tempat di mana node baru sebaiknya dimasukkan, mungkin diperlukan
untuk memindai semua elemen daftar.
Linked List bisa dilaksanakan di
kebanyakan bahasa,seperti Lisp (pelat) dan Scheme (siasat) yang menyebabkan
struktur data tambahan dibuat, serta pelaksanaan sampai akses linked list.
Prosedur atau bahasa yang diorientasikan dengan benda seperti C, C++, dan Java
biasanya mengandalkan referensi untuk membuat linked list.
Dalam
struktur data algortima linked list mempunyai beberapa jenis yaitu:
1. Single Linked List
Tempat yang
disediakan pada satu area memori tertentu untuk menyimpan data dikenal dengan
sebutan node atau simpul. Setiap node memiliki pointer
yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, dengan
demikian hanya diperlukan sebuah variabel pointer. Susunan berupa
untaian semacam ini disebut Single Linked List (NULL memilik nilai
khusus yang artinya tidak menunjuk ke mana-mana. Biasanya Linked List
pada titik akhirnya akan menunjuk ke NULL). Pembuatan Single Linked List
dapat menggunakan 2 metode:
1. LIFO (Last
In First Out), aplikasinya : Stack (Tumpukan)
2. FIFO (First
In First Out), aplikasinya : Queue (Antrian)
Operasi-Operasi
yang ada pada Linked List :
a. Insert
Istilah Insert berarti
menambahkan sebuah simpul baru ke dalam suatu linked list.
b. IsEmpty
Fungsi ini menentukan apakah linked
list kosong atau tidak.
c. Find First
Fungsi ini mencari elemen
pertama dari linked list
d. Find Next
Fungsi ini mencari elemen
sesudah elemen yang ditunjuk now
e. Retrieve
Fungsi ini mengambil elemen
yang ditunjuk oleh now. Elemen tersebut lalu dikembalikan oleh fungsi.
f. Update
Fungsi ini mengubah elemen
yang ditunjuk oleh now dengan isi dari sesuatu.
g. Delete Now
Fungsi ini menghapus elemen
yang ditunjuk oleh now. Jika yang dihapus adalah elemen pertama dari linked
list (head), head akan berpindah ke elemen berikut.
h. Delete Head
Fungsi ini menghapus elemen
yang ditunjuk head. Head berpindah ke elemen sesudahnya.
i. Clear
Fungsi ini menghapus linked
list yang sudah ada. Fungsi ini wajib dilakukan bila anda ingin mengakhiri
program yang menggunakan linked list. Jika anda melakukannya, data-data
yang dialokasikan ke memori pada program sebelumnya akan tetap tertinggal di
dalam memori.
Gambar 1.1 Single Linked List
2. Circular singly linked list
Single Linked List Circular adalah Single Linked List
yang pointer nextnya menunjuk pada dirinya sendiri. Jika Single Linked List tersebut
terdiri dari beberapa node,
maka pointer
next pada node terakhir akan menunjuk ke node terdepannya.
Pengertian:
Sing : leartinya
field pointer-nya hanya satu buah saja dan satu arah.
Circular : artinya
pointer next-nya akan menunjuk pada dirinya sendiri sehingga berputar
Ilustrasi
Single Linked List Circular
- Setiap
node pada linked list mempunyai field yang berisi pointer ke node
berikutnya, dan juga memiliki field yang berisi data.
- Pada akhir
linked list, node terakhir akan menunjuk ke node terdepan
sehingga linked list tersebut berputar. Node terakhir akan menunjuk lagi
ke
head.
Gambar 1.2 Circular Singly Linked List
3. Double Linked List
Salah satu
kelemahan single linked list adalah pointer (penunjuk) hanya
dapat bergerak satu arah saja, maju/mundur, atau kanan/kiri sehingga pencarian
data pada single linked list hanya dapat bergerak dalam satu arah saja.
Untuk mengatasi kelemahan tersebut, dapat menggunakan metode double linked
list. Linked list ini dikenal dengan nama Linked list
berpointer Ganda atau Double Linked List. Operasi-operasi dasar yang ada pada
double linked list:
a. Insert tail
: fungsi insert tail berguna untuk menambah simpul di belakang (sebelah kanan)
pada sebuah linked list.
b. Insert head
: sesuai dengan namanya, fungsi insert head berguna untuk menambah simpul di depan
(sebelah kiri). Fungsi ini tidak berada jauh dengan fungsi insert tail yang
telah dijelaskan sebelumnya.
c. Delete tail
: fungsi delete tail berguna untuk menghapus simpuldar belakang. Fungsi ini
merupakan kebalikan dari fungsi insert tail yang menambah simpul dibelakang. Fungsi
delete tail akan mengarahkan now keapada tail dan kemudian memanggil fungsi
delete now.
d. Delete head
: fungsi delete head merupakan kebalikan dari fungsi delete tail yang menghapus
simpul dari belakang, sedangakn delete head akan menghapus simpul dari
epan(sebelah kiri). Fungsi delete head akan mengarahkan now kepada head an
kemudian memanggil fungsi delete now.
Gambar 1.3 Double Linked List
4.
Circular Double Linked List
Merupakan double
linked list yang simpul terakhirnya menunjuk ke simpul terakhirnya menunjuk
ke simpul awalnya menunjuk ke simpul akhir sehingga membentuk suatu lingkaran.
Operasi-Operasi yang ada pada Linked List :
Gambar 1.4 Circular Double Linked List
5. Multiple Linked List
Multiple Linked List merupakan suatu linked list yang
memiliki lebih dari 2 buat variabel pointer. contoh :
Gambar 1.5 Multiple Linked List
Contoh program
dan algoritma operasi insert(push) dan delete(pop) pada linked list
a. Insert(push)
INSERT KANAN/BELAKANG
INSERT KANAN/BELAKANG
Penambahan data di belakang Penambahan data dilakukan
di belakang, namun pada saat pertama kali data langsung ditunjuk pada head-nya.
Penambahan di belakang lebih sulit karena kita membutuhkan pointer bantu untuk
mengetahui data terbelakang, kemudian dikaitkan dengan data baru. Untuk
mengetahui data terbelakang perlu digunakan perulangan.
Algoritma :
Void Ins_Akhir()
{
Last -> Link = P;
Last = P;
P -> Link = NULL;
}
Coding:
void insertBelakang (int
databaru)
{
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next != head){
bantu=bantu->next;
}
bantu->next = baru;
baru->next = head;
}
cout<<"Data
masuk\n";
}
INSERT KIRI/DEPAN
Penambahan data di depan
INSERT KIRI/DEPAN
Penambahan data di depan
Penambahan node baru akan dikaitan
di node paling depan, namun pada saat
pertama kali (data masih kosong),
maka penambahan data dilakukan pada
head nya. Pada prinsipnya adalah
mengkaitkan data baru dengan head, kemudian head
akan menunjuk pada data baru
tersebut sehingga head akan tetap selalu
menjadi data terdepan. Untuk
menghubungkan node terakhir dengan node
terdepan dibutuhkan pointer bantu.
Algoritma :
void Ins_Awal() {
Algoritma :
void Ins_Awal() {
P -> Link = First;
First = P;
}
Coding :
void insertDepan(int
databaru){
TNode *baru,*bantu;
baru = new TNode;
baru->data = databaru;
baru->next = baru;
if(isEmpty()==1){
head=baru;
head->next=head;
}
else {
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
baru->next = head;
head = baru;
bantu->next = head;
}
cout<<"Data
masuk\n";
}
b. Delete(pop)
DELETE
KANAN/BELAKANG
Algoritma :
void Del_Akhir()
{
Free(last);
Last = Q;
Last -> Link = NULL;
}
Coding :
void hapusBelakang()
{ TNode *hapus,*bantu;
if (isEmpty()==0)
{
int d;
hapus = head;
if(head->next == head){
head = NULL;
}
else
{
bantu = head;
while(bantu->next->next !=
head){
bantu = bantu->next;
}
hapus = bantu->next;
d = bantu->data;
bantu->next = head;
delete hapus;
}
cout<<<"
terhapus\n";
}
else
cout<<"Masih
kosong\n";
}
- Membutuhkan pointer bantu dan
hapus.
- Pointer hapus digunakan untuk
menunjuk node yang akan dihapus, dan pointer bantu digunakan untuk menunjuk
node sebelum node yang dihapus.
- Pointer bantu akan digunakan untuk
menunjuk ke nilai NULL.
- Pointer bantu akan selalu bergerak
bersama dengan pointer hapus tapi letak pointer bantu harus selalu dibelakang
pointer hapus.
DELETE KIRI/DEPAN
Algoritma :
void Del_Awal()
{
Q = First;
First = Q -> Link;
free(q);
}
Coding :
void hapusDepan ()
{ TNode *hapus,*bantu;
if (isEmpty()==0)
{
int d;
hapus = head; d =
head->data;
if(head->next != head){
bantu = head;
while(bantu->next!=head){
bantu=bantu->next;
}
head = head->next;
delete hapus;
bantu->next = head;
}else{
head=NULL;
}
cout<<<"
terhapus\n";
}
else cout<<"Masih
kosong\n";
}
- Function di atas akan menghapus
data teratas (pertama) yang ditunjuk oleh head pada linked list
- Penghapusan node tidak boleh
dilakukan jika keadaan node sedang ditunjuk oleh pointer, maka harus ditampung
dahulu pada variabel hapus dan barulah kemudian menghapus variabel hapus dengan
menggunakan perintah delete.
- Sebelum data terdepan dihapus,
head harus ditunjukkan ke data sesudahnya terlebih dahulu sehingga data
setelah head lama akan menjadi head baru (data terdepan yang baru).
- Jika head masih NULL maka berarti
data masih kosong!
Referensi :
Komentar
Posting Komentar