Pertemuan 8

LINKED LIST

PENDAHULUAN

• Dalam suatu linear list kita dapat melakukan operasi penyisipan atau penghapusan atau elemen-elemnya 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 elemn ke-55 tidak akan berubah posisinya pada linear tersebut.
• Tetapi elemen ke-57 akan menjadi elemen ke-56, elemen ke-58 akan menjadi elemen ke-57 dst.
• Selanjutya, jika kita sisipkan satu elemen pada posisi setelah elemen ke-41, maka elemen ke-41 s/d 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 mempresentasikan suatu data.

ARRAY VS LINKED LIST

ARRAY	LINKED LIST
Statis	Dinamis
Penambahan / penghapusan data terbatas	Penambahan / penghapusan data tidak terbatas
Random acces	Sequential acces
Penghapusan array tidak mungkin	Penghapusan linked list mudah

DEFINISI 

Linked list (one way list) adalah suatu kumpulan elemen data (yang disebut sebagai node)

dimana urutanya ditentukan oleh suatu pointer.

Setiap elemen (node) dari suatu linked list terdiri dari 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.

Bentuk Node Single Linked List non Circular 

Pengertian :

Single        : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menuju NULL

Linked list : artinya node-node tersebut saling terhubung satu sama lain.

Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data.

Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.

Berikut ini sebuah linked list yang terdiri atas 4 node :

Pada node ke-4 field NEXT-nya berisi NULL, artinya node ke-4 tersebut adalah node terakhir.

Node-node dalam linked list tidak harus selalu digambarkan paralelseperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan sebagai berikut :

CATATAN

Ada dua hal yang menjadi kerugian dengan representasi suatu data dengan linked list ini, yaitu :

• Diperlukan ruang tambahan untuk menyatakan /  tempat field folder.
• Diperlukan waktu yang lebih banyak untuk mencari suatu node dalam linked list.

Sedangkan keuntunganya adalah :

• Jenis data yang berbeda dapat di-link.
• 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 :

- Test apakah sama dengan NULL.

- Test untuk kesamaan dengan variabel pointer lain.

- Menetapkan sama dengan NULL.

- Menetapkan menuju ke node lain

• Notasi yang didefinisikan sehubungan dengan operasi di atas adalah:

- NODE(P), artinya node yang ditunjuk oleh pointer P.

- INFO(P), artinya nilai INFO dari node yang ditunjuk pointer P.

- 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 KEDALAM 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 kedalam 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 umunya dalam menginput data digunakan data cara sequintial)

(b) Jika menggunakan logika linked list

Contoh soal Operasi Logika Linked List:

1. Insert A           6. Delete A

2. Insert B            7. Delete D

3. Insert C            8. Insert E

4. Delete B          9. Insert F

5. Insert D           10. Insert G

Jawaban:

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 : nodeptype;

*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;

INSERT-END

PENYISIPAN 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:=newnoade;

      rear:=newnode;

end;