STRUKTUR DATA

LINKED LIST

• Dalam suatu linear list kita dapat melakukan operasi penyisipan / 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

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

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 2 bagian yaitu :

1. Info, berisi informasi tentang elemen data yang bersangkutan
2. Next (linked field / next pointer field), berisi alamat dari elemen (node) selanjutnya yang dituju

BENTUK NODE SINGLE LINKED LIST NON CIRCULAR

Pengertian :

• Single : artinya field pointernya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk 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 contoh linked list yang terdiri atas 4 node
• 
• Pada node ke 4 field nextnya berisi null artinya node ke 4 tersebut adalah node terakhir
• Node – node dalam linked list tidak harus selalu di gambarkan parallel seperti pada gambar diatas. Linked list pada contoh diatas dapat pula digambarkan seperti berikut
• 
• Catatan :

·         Ada 2 hal yang menjadi kerugian dengan representasi suatu data dengan linked list ini yaitu

2.   Di perlukan ruang tambahan untuk menyatakan / tempat field pointer

3.   Diperlukan waktu yang lebih banyak untuk mencari suatu node ke dalam linked list

·         Sedangkan keuntungannya adalah

5.    Jenis data yang berbeda dapat di link

6.    Operasi remove / insert hanya dilakukan dengan mengubah pointernya saja

OPERASI DASAR PADA LINKED LIST

Ada beberapa aturan yang dapat didefinisikan pada operasi didalam linked list yaitu

·         Jika P adalah suatu variabel pointer, maka nilainya adalah alamat / lokasi dari variabel lain yang dituju

·         Operasi yang didefinisikan pada suatu variabel pointer adalah

9.    Test apakah sama dengan null

10. Test untuk kesamaan dengan variabel pointer lain

11.  Menetapkan sama dengan null

12. Menetapkan menuju ke node lain

·         Notasi yang didefinisikan sehubungan dengan operasi diatas adalah

14. Node (P) artinya node yang ditunjuk oleh pointer P

15. INFO (P) artinya nilai info dari node yang ditunjuk pointer P

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

·         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 1

Q := NEXT(P)

·         Langkah 2

NEXT(P) := NEXT (Q)

·         Langkah 3

FREENODE(Q)

·         Procedure freenode (Q)

2.            NEXT (Q) := avail

3.            ·         INFO (Q) := NULL

·         Avail := Q

·         MENYISIPKAN SUATU NODE KEDALAM LINKED LIST

·         Untuk menyisipkan node kedalam linked list digunakan procedure GETNODE

·         Jika NEW adalah suatu variabel pointer, maka GETNODE(NEW) akan menyebabkan node yang ditunjuk oleh variabel pointer NEW di sisipkan ke dalam linked list

PROCEDURE GETNODE (NEW)

If Avail = Null

Then out-of-free-space

·         Else begin

Getnode := avail;

·         Avail := Next(Avail);

·         Next(Getnode) := Null;

·         End;

·         ALGORITMA MENYISIPKAN SEBUAH NODE

·         Getnode(NEW);

·         Info(NEW) := Name;

·         Q := Next(P)

·         Next(P) := NEW

·         Next(NEW) := Q

·         LOGIKA LINKED LIST PADA ARRAY

• Jika tidak menggunakan logika linked list (pada umumnya dalam meng-input data digunakan cara sequential)

• Jika menggunakan logika linked list

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

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

INSERT-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^. <> 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 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;