LINKED
LIST
PENDAHULUAN.
Dalam suatu linear list kita dapat melakukan
operasi penyisipan atau penghapusan atas elemen-elemennya pada sembarang
posisi.
Misalkan ada 1500 item yang merupakan elemen
dari suatu linear list.
Jika elemen ke-56 akan kita keluarkan, maka
elemen ke-1 s/d elemen ke-55 tidak akan berubah posisinya pada linear list
tersebut. Tetapi elemen ke-57 akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke-57 dst. Selanjutnya,
jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen
ke-42 s/d elemen ke-1500 akan berubah posisinya.
Untuk menyatakan keadaan diatas diperlukan
suatu konsep yang berbeda dengan konsep sekuensial sebelumnya.
Linked list merupakan suatu cara
non-sekuensial yang digunakan untuk merepresentasikan suatu data.
DEFINISI.
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 :
CATATAN :
-
Ada
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