LINKED LIST
Linked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node) dimana urutannya ditentukan oleh suatu pointer.
Setiap elemen (node) dari suatu linked list terdiri atas dua bagian, yaitu :
- INFO , berisi informasi tentang elemen data yang bersangkutan.
- NEXT (link field/next pointer field), berisi alamat dari elemen (node) selanjutnya yang dituju.
Berikut ini sebuah contoh linked list yang terdiri atas 4 node :
Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tsb. adalah node terakhir.
Node-node dalam linked list tidak harus selalu digambarkan paralel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut ini :
-
yaitu :
1. Diperlukan ruang tambahan untuk menyatakan/tempat field pointer.
2. Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.
- Sedangkan keuntungannya adalah :
1. Jenis data yang berbeda dapat di-link.
2. Operasi REMOVE atau INSERT hanya dilakukan dengan mengubah pointer-nya saja.
OPERASI DASAR PADA LINKED LIST.
- Jika P adalah suatu variabel pointer, maka nilainya adalah alamat atau lokasi dari variabel lain yang dituju.
- Operasi yang didefinisikan pada suatu variabel pointer adalah :
1. Test apakah sama dengan NULL.
2. Test untuk kesamaan dengan variabel pointer lain.
3. Menetapkan sama dengan NULL.
4. Menetapkan menuju ke node lain.
Notasi yang didefinisikan sehubungan dengan operasi diatas adalah :
1. NODE(P), artinya node yang ditunjuk oleh pointer P.
2. INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P.
3. NEXT(P), artinya hubungan (link) selanjutnya dari node yang ditunjuk oleh pointer P.
Sebagai contoh, perhatikan linked list dibawah ini :
NODE(P) = node yang ditunjuk oleh P yaitu node pertama.
INFO(P) = A
NEXT(P) = node ke-dua
INFO(NEXT(NEXT(P))) = C
MENGHAPUS SUATU NODE DARI LINKED LIST (REMOVE).
Untuk menghapus node dalam linked list digunakan procedure FREENODE.
Jika Q adalah suatu variabel pointer, maka FREENODE(Q) akan menyebabkan node yang ditunjuk oleh variabel pointer Q dihapus dari linked list.
Perhatikan linked list berikut :
langkah ke-1 :
Q := Next(P)
langkah ke-2 :
Next(P) := Next(Q)
langkah ke-3 :
Freenode(Q)
procedure Freenode(Q)
(a) Next(Q) := Avail
(b) Info(Q) := Null
(c) Avail := Q
MENYISIPKAN SUATU NODE KE DALAM LINKED LIST
Untuk menyisipkan node dalam linked list digunakan procedure GETNODE.
Jika NEW adalah suatu variabel pointer, maka GETNODE(NEW) akan menyebabkan node yang ditunjuk oleh variabel pointer NEW disisipkan ke dalam linked list.
procedure Getnode(NEW)
if Avail = Null
then out-of-free-space
(a) else begin
Getnode := Avail;
(b) Avail := Next(Avail);
(c) Next(Getnode) : = Null;
end;
Algoritma menyisipkan sebuah Node :
(a) Getnode(NEW);
(b) Info(NEW) := Name;
(c) Q := Next(P)
(d) Next(P) := NEW
(e) Next(NEW) := Q
Logika Linked List pada Array
(a) Jika tidak menggunakan logika linked list
(pada umumnya dalam meng-input data digunalan cara sequential)
| | Awal | | Insert E | | Delete C | | Insert F |
| 1 | A | 1 | A | 1 | A | 1 | A |
| 2 | C | 2 | C | 2 | | 2 | |
| 3 | | 3 | E | 3 | E | 3 | E |
| 4 | | 4 | | 4 | | 4 | F |
| | | | | | | | |
| | | | Insert G | | | | |
| | Delete E | | (overflow) | | | | |
| 1 | A | 1 | A | | | | |
| 2 | | 2 | | | | | |
| 3 | | 3 | | | | | |
| 4 | F | 4 | F | | | | |
(b) Jika menggunakan logika Linked List
Keadaan awal Insert E Delete C
| | Info | Next | | Info | Next | | Info | Next |
| 1 | A | 2 | 1 | A | 2 | 1 | A | 3 |
| 2 | C | 0 | 2 | C | 3 | 2 | | 4 |
| 3 | | 4 | 3 | E | 0 | 3 | E | 0 |
| 4 | | 0 | 4 | | 0 | 4 | | 0 |
Insert F Delete E Insert G
| | Info | Next | | Info | Next | | Info | Next |
| 1 | A | 3 | 1 | A | 2 | 1 | A | 2 |
| 2 | F | 0 | 2 | F | 0 | 2 | F | 3 |
| 3 | E | 2 | 3 | | 4 | 3 | G | 0 |
| 4 | | 0 | 4 | | 0 | 4 | | |
Mendefinisikan Linked List dalam Pascal
Type nodeptr = ^ nodetype;
nametype = packed array [1..10] of char;
nodetype = record
info : nametype;
next : nodeptr;
end;
Var p : nodeptr;
node : nodetype;
* Catatan :
P ^. Info : Info dari node yang ditunjuk oleh pointer P
P^. Next : Next dari node yang ditunjuk oleh pointer P
P := nil : pointer P berisi nilai Null
New(P) : fungsi Getnode dalam Pascal
dispose(P) : procedure Freenode dalam Pascal
Menghapus sebuah Node dalam Pascal
procedure removaf(p:nodeptr, var out:nametype);
var q : nodeptr;
begin
if (p^.Next = nil)
then UNDERFLOW-CONDITION
else begin
q := p^.Next;
p^.Next := q^.Next;
out := q^.Info;
dispose(q);
end;
end;
Menyisipkan sebuah Node dalam Pascal
procedure inseraf(p:nodeptr, in:nametype);
var q : nodeptr;
begin
New(q);
q^.Info := in;
q^.Next := p^.Next;
p^.Next := q;
end;
Penyisipan pada akhir dari suatu Linked List (Linked List Antrean) dalam Pascal
Procedure Inserend(first : nodeptr, in :nametype);
Var newnode, q : nodeptr;
Begin
New(newnode);
newnode^.Info := in;
newnode^.Next := nil;
q := first;
do while (q^.next <> nil)
q := q^.Next;
q^.Next := newnode;
End;
Jika sebuah Linked List digunakan untuk menggambarkan suatu antrean, dalam hal ini pointer dapat langsung menunjuk ke rear/akhir dari antrean untuk menghindari pengulangan melalui semua node untuk menemukan node terakhir.
procedure inserend(in : nametype, var rear : nodeptr);
var newnode : nodeptr;
begin
New(newnode);
newnode^.Info := in;
newnode^.Next := nil;
rear^.Next := newnode;
rear := newnode;
end;
Circular Linked List
Head Nodes
Circular Linked List dengan Head Node
Circular Linked List dengan Head Node kosong
Algoritma penyisipan node yang berisi variabel Name pada head dalam Linked List
(a) Ambil node baru pada free storage kemudian node tersebut ditunjuk oleh pointer NEW
(b) Isikan Info dengan Name pada node baru tsb.
(c) Next dari node baru tsb. menunjuk ke node yang ditunjuk oleh pointer Head
(d) Pindahkan pointer Head menunjuk ke node yang baru.
Menghapus Node Khusus
Procedure removp(head : nodeptr, var p:nodeptr, out : nametype);
Var prior, this : nodeptr;
flag : 0..2;
Begin
prior := head;
this := head^.next;
flag := 1;
While flag = 1
do begin
if (this = head)
then flag := 2;
if (this = p)
then flag := 0
else begin
prior := this;
this := this^.next;
end;
end;
if (flag > 0)
then Node yang ditunjuk oleh pointer p tidak ada dalam List else begin
prior^.next := p^.next;
out := p^.info;
dispose(p)
end;
End;
Doubly Linked List
Tiap node memiliki pointer yang menunjuk ke node sesudahnya dan pointer yang menunjuk
ke node sebelumnya.
Node Sesudahnya : Next(Node)
Node sebelumnya : Prior(Node)
Next(Prior(P)) = P dan P = Prior(next(P))
Double Linked List Kosong :
prior head next Prior(Head) = Head
Next(Head) = Head
Dalam Pascal :
Type nodeptr = ^ nodetype
nodetype = record
prior : nodeptr;
info : nametype;
next : nodeptr
end;
Procedure menghapus sebuah node pada Double Linked List
(a) Set pointer P
(b) Ubah pointer pada node Next predecessor P ke node Successor P
(c) Ubah pointer pada node dari prior Successor P ke node Predeccssor P
(d) bebaskan node yang ditunjuk pointer P
Dalam Pascal :
Procedure Removp(var p:nodeptr, out : nametype);
Var pred, succ : nodeptr;
Begin
pred := p^.prior;
succ := p^.next;
pred^.next := succ;
succ^.prior := pred;
out := p^.info;
dispose(p)
End;
Penyisipan sebuah Node pada Doubly Linked List
(a) Ambil sebuah node baru dan isikan datanya
(b) Set pointer dari Next node baru menunjuk ke Successor P dan pointer Proirnya ke P
(c) Ubah pointer Next P menunjuk ke node baru
(d) Ubah pointer Prior dari Successor P menunjuk ke node baru
Contoh Aplikasi Linked List
Polynomial
anxn + an-1 xn-1 + ... + a2 x2 + a1 x + a0
Type nodeptr = ^nodetype;
nodetype = record
exp : integer;
coef : integer;
next : nodeptr;
end;
143 x4 + 201 x2 + 14 x + 2
a4 = 143 a3 = 0 a2 = 201 a1 = 14 a0 = 2
Tidak ada komentar:
Posting Komentar