linked list - · pdf filestring yang dinyatakan oleh gambar 5.4 tersebut adalah no exit. start...

Click here to load reader

Post on 12-Feb-2019

217 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

Pengantar Struktur Data Bab 5 Linked List

83

LINKED LIST

5.1 STRUKTUR BERKAIT

Pada pembicaraan kita dalam Bab 1, telah disinggung sekilas tentang sejenis struktur yang dibentuk dengan cara mengaitkan struktur yang lebih sederhana. Perhatikan Gambar 5.1.

A B50

100

POINTER

50Alamat memori

POINTER

Gambar 5.1. Struktur berkait

Salah satu di antara struktur berkait tersebut adalah yang disebut sebagai linear linked list atau one-way list. Selain itu dikenal pula beberapa jenis struktur berkait yang lain seperti linked-stack, linked-queue, doubly linked-list, linked-generalized list dan sebagainya.

Pengantar Struktur Data Bab 5 Linked List

84

Kali ini kita bahas secara sederhana bagaimana operasi penyisipan atau insertion dan operasi penghapusan atau deletion bekerja pada struktur berkait. Kita mulai dengan struktur singly linked-list atau singkatnya linked list. Linked-list, yang kerap kali disebut pula one-way List, adalah koleksi linear dari elemen data yang disebut simpul atau node. Cara melinearkan urutan, adalah dengan menggunakan penuding atau pointer. Dalam hal ini, setiap simpul terdiri atas dua bagian. Bagian pertama berisi informasi data tersebut, sedangkan bagian kedua merupakan field, link, atau nextpointer. Link inilah yang menghubungkan satu elemen data ke elemen data lainnya, sehingga urutan elemen data tersebut membentuk suatu linear list. Field link ini berisi alamat dari simpul berikutnya dalam list. Ia bernilai 0 bila link tersebut tidak menuding ke data (simpul) lainnya. Penuding ini disebut penuding nol.

Gambar 5.2 merupakan diagram secara skematik dari sebuah linked list dengan 6 buah simpul. Setiap Simpul digambarkan sebagai dua kotak, Kotak kiri menyajikan bagian informasi (dapat berupa sebuah field NAMA, ataupun field NOMOR-POKOK, ataupun dapat pula berupa sebuah record). Kotak kanan menyajikan field nextpointer.

Dari kotak kanan ini tergambar panah mengarah ke simpul berikut. Penuding nol adalah penuding ke simpul akhir dari list yang disajikan dengan tanda X.

Nextpointer field of third node

x

Information part of third node

Gambar 5.2 Linked list dengan 6 simpul (nodes)

Linked list juga mengandung sebuah variabel penuding list, yang biasanya diberi nama

START, yang berisi alamat dari simpul pertama dalam list. Di sini tergambar panah dari START mengarah ke simpul pertama tersebut.

Hal khusus dapat terjadi, yakni list tidak mengandung sebuah simpulpun. List semacam itu disebut list hampa atau list nol. List ini disajikan dengan menempatkan penuding nol pada variabel START.

Contoh 5.1

Pada bangsal sebuah rumah sakit terdapat 12 tempat tidur. Sembilan di antaranya, telah ditempati pasien, seperti digambarkan pada Gambar 5.3. Kita hendak membuat list nama

Pengantar Struktur Data Bab 5 Linked List

85

para pasien tersebut diurut secara alfabetik. Untuk itu kita buat sebuah linked list, dengan penuding NEXT.

Variable START kita gunakan untuk menyatakan lokasi pasien pertama dalam list. Jadi START berisi 5, karena pasien pertama tersebut, yakni Adam, menempati tempat tidur nomor 5. Selanjutnya penuding dari Adam bernilai 3, karena pasien kedua dalam list adalah Deni, menempati tempat tidur nomor 3, demikian seterusnya.

Akhirnya, untuk pasien terakhir, Samuel, penudingnya merupakan penuding nol (dinyatakan dengan bilangan 0).

Gambar 5.3. Sortir data dalam linked list

5.2 PENYAJIAN LINKED LIST DALAM MEMORI

Misalkan LIST adalah sebuah linked list. Kalau tidak disebutkan lain, LIST akan disajikan dalam memori adalah dengan cara sebagai berikut. Kita bentuk larik INFO(K) dan LINK(K), berturut-turut untuk menyajikan bagian informasi dan field nextpointer. Juga kita pakai sebuah variabel START untuk menyimpan alamat dari elemen LIST. Pada

Pengantar Struktur Data Bab 5 Linked List

86

bagian akhir dari LIST, nextpointer bernilai NULL. Apabila tidak disebutkan, nilai NULL adalah 0, dan nilai dari subscript larik INFO serta LINK selalu diambil positif.

Contoh linked list berikut memperlihatkan bahwa elemen tak perlu menempati posisi yang berdampingan pada larik INFO serta LINK. Juga lebih dari satu linked list dapat disimpan dalam kedua larik yang sama tersebut di atas.

Contoh 5.2

Gambar 5.4 menggambarkan suatu linked list dalam memori. Data dalam larik INFO(K) adalah sebuah karakter tunggal. Dengan setiap kali kita mengubah nilai larik LINK(K) serta START, kita dapat membentuk linked list lain, yang kalau dibaca elemennya akan merupakan sebuah string atau untai.

String yang dinyatakan oleh Gambar 5.4 tersebut adalah NO EXIT.

START = 9, jadi INFO(9) = N adalah karakter pertama yang dikunjungi, LNK(9) = 3, jadi INFO(3) = O adalah karakter kedua, LNK(3) = 6, jadi INFO(6) = (blank) adalah karakter ketiga, LNK(6) = 4, jadi INFO(4) = E adalah karakter keempat, LNK(4) = 7, jadi INFO(7) = X adalah karakter kelima, LNK(7) = 1, jadi INFO(1) = I adalah karakter keenam, LNK(1) = 5, jadi INFO(5) = T adalah karakter ketujuh, LNK(5) = 0, null pointer, list berakhir.

1

2

3

4

5

6

7

8

9

INFO LINK

O

T

X

I

N

START

9

0

4

6

1

3

5

E 7

Gambar 5.4. Linked list yang menghasilkan string

Pengantar Struktur Data Bab 5 Linked List

87

Contoh 5.3

Pada contoh ini diperlihatkan dua buah linked list, ALG dan GEOM, yang berturut-turut berisi nilai testing mata kuliah Algoritma dan Geometri, dapat tersimpan bersama dalam larik TEST dan LINK yang sama. Perhatikan bahwa nama dari list sekaligus digunakan sebagai variabel penuding.

Di sini penuding ALG berisi nilai 11, yakni lokasi dari simpul pertama list ALG, sedangkan penuding GEOM berisi nilai 5, yakni lokasi simpul pertama dari list GEOM. Mengikuti penuding tersebut, dapat dilihat bahwa list ALG berisi nilai-nilai :

88 74 93 82

dan list GEOM berisi nilai-nilai

84 62 74 100 74 78

11

5

ALG

GEOM

1

2

3

4

5

6

7

8

9

10

11

12

TEST LINK

13

14

15

16

74

82

84

78

74

100

88

62

74

93

16

14

1

0

12

0

8

13

10

3

2

7

6

4

0

15

Gambar 5.5. Contoh linked list hasil testing 2 mata kuliah

Pengantar Struktur Data Bab 5 Linked List

88

Contoh 5.4

Lihat Gambar 5.6. Pandang suatu agen penjualan yang mempunyai 4 orang broker (perantara). Setiap broker mempunyai list customer (pelanggan) masing-masing. Data dapat diorganisir seperti pada Gambar 5.6. Di sini keempat list pelanggan digabung dalam satu linked list dengan larik CUSTOMER berisi nama pelanggan dan larik LINK merupakan nextpointer.

Nama broker ditempatkan dalam larik BROKER, dan digunakan pula variabel penuding dalam bentuk larik POINT, sedemikian sehingga POINT(K) menuding ke lokasi dari simpul pertama BROKER(K). Dapat kita lihat bahwa broker Bond mempunyai pelanggan berturut-turut Grant, Scott,Vito, Katz

Di sana, Tall tidak mempunyai pelanggan, karena POINT(3)=0. Kita dapat berbicara secara lebih umum, yakni bahwa bagian informasi dari setiap simpul merupakan sebuah record, dengan lebih dari satu satuan data. Dalam kasus ini, kita harus menyimpan data tersebut dalam bentuk struktur record ataupun dalam bentuk koleksi larik sejajar. Perhatikan contoh berikut :

Contoh 5.5

Lihat Gambar 5.8. Pandang berkas personalia dari sebuah perusahaan kecil, yang terdiri dari record 9 orang pegawai, dengan field NAMA, SSN (Social Security Number), SEX dan Gaji per bulan (monthly salary) Gambar tersebut memperlihatkan bagaimana berkas diorganisir sebagai linked list yang terurut (alfabetik), dengan menempatkan informasi dalam empat buah larik sejajar NAMA, SSN, SEX, dan SALARY, serta menggunakan pula larik LINK sebagai nextpointer, dan variabel START yang menuding record pertama. Di sana 0 digunakan sebagai penuding nol.

5.3 KUNJUNGAN LINKED LIST

Pandang sebuah linked list, LIST yang tersimpan dalam memori berupa larik INFO dan LINK, dilengkapi dengan variabel penuding START, yang berfungsi menuding lokasi simpul pertama dari list, dan NULL yang digunakan untuk menyatakan berakhirnya list.

Sekarang kita akan melakukan traversal atau kunjungan simpul list, sesuai urutan, untuk memproses setiap simpul tepat satu kali. Algoritma traversal kita, menggunakan variabel penuding PTR untuk menuding simpul yang sedang diproses saat itu. Karena itu LINK (PTR) akan menuding simpul berikut dalam list.

Pengantar Struktur Data Bab 5 Linked List

89

0 14

12

0

20

9

13

10

19

18

17

1

2

3

4

15

BROKER LINK

Hunter

Katz

POINT

Evans

COSTUMER

0

3

Bond

Kelly

Hall

Nelson

1

2

3

4

5

6

7

8

9

10

11

12

13

14