LINKED LIST

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 :

info start next info next info next info next node ke-1 node ke-2 node ke-3 node ke-4

null 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

CATATAN :

- Ada dua hal yang menjadi kerugian dengan representasi suatu data dengan linked list 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 pointernya

saja.

OPERASI DASAR PADA LINKED LIST.

Ada beberapa aturan yang didefinisikan pada operasi didalam linked list, yaitu :

- 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.

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.

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;

info next info next info next info next

null

...

Avail

(b) Avail := Next(Avail);

info next info next info next info next

null

...

Getnode

Avail

(c) Next(Getnode) : = Null;

end;

info next info next info next info next

null

...

Getnode Avail

null

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

info next info next info next info next

...

first

Head Nodes

info next info next info next info next

...

Head

Circular Linked List dengan Head Node

info next

Head

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

next

...

Head

prior info

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 next

head

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

prior info next

P

(b) Ubah pointer pada node Next predecessor P ke node

Successor P

prior info next

P

(c) Ubah pointer pada node dari prior Successor P ke node

Predeccssor P

prior info next

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

IN

P

NEW

AVAIL

(c) Ubah pointer Next P menunjuk ke node baru

(d) Ubah pointer Prior dari Successor P menunjuk ke node baru

IN

P

NEW

AVAIL

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

POLY 1

EXP COEF

4 143 2 20 1 14 0 2