linked list - elearning.gunadarma.ac.id · string yang dinyatakan oleh gambar 5.4 tersebut adalah...

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.


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


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


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


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


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.


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

15

16

17

18

19

20

Adams

Scott

Weston

McBride

Grant

Jones

Teller

Rogers

Vito 4

16

0

6

0

5

1

2

8

7

Gambar 5.6. Linked list empat orang broker

Statement : PTR := LINK(PTR)

akan menggerakkan penuding ke simpul berikutnya sebagai digambarkan dalam Gambar 5.8. Secara rinci, algoritma traversal kita adalah demikian: mula-mula, kita awali dengan memberi nilai kepada PTR, sama dengan START. Kita proses INFO(PTR), yakni informasi pada simpul pertama dalam list. Selanjutnya kita perbaharui PTR melalui statement PTR := LINK(PTR). Kita proses sekarang INFO(PTR), yakni informasi pada simpul kedua. Demikianlah selanjutnya kita perbaharui lagi PTR, melalui statemen PTR := LINK(PTR), Proses INFO(PTR), yakni informasi pada simpul ketiga, dan seterusnya sampai nilai PTR := NULL, pertanda berakhirnya traversal.


90

Gambar 5.7 Record dalam linked list

ALGORITMA

1. PTR : = START

2. Kerjakan

langkah 3 dan 4

dalam hal

PTR <> NULL

3. Proses INFO(PTR)

4. PTR := LINK(PTR)

5. EXIT


91

6

START 0

Kelly 7

12

Green 14

Lewis

Cohen

Evans

1

9

10

2

0

13

4

1

2

3

4

5

6

7

8

9

10

11

12

11

NAMA LINK

Gambar 5.8 Kunjungan dalam linked list

Davis

Brown

Rubin

13

14 Harris

165-64-3351

175-56-2251

181-58-9939

177-44-4557

168-56-8113

SSN

192-38-7282

178-52-1065

135-46-6262

208-56-1654

Female

Male

Male

Male

Female

SEX

Male

Male

Male

Male

19,000

27,200

16,400

19,000

34,200

SALARY

22,800

14,700

15,500

22,800

5

3

Proses yang dilakukan terhadap INFO(PTR) dapat dalam berbagai bentuk. Misalnya proses mencetak, ataupun yang lainnya lagi. Silakan Anda memodifikasi algoritma di atas untuk dapat mencetak semua informasi dalam list. Juga pikirkan bagaimana menghitung banyaknya elemen (simpul) dari list.

5.4 PENCARIAN (SEARCHING) DALAM LINKED LIST

Pandang linked list, LIST, yang disajikan dalam memori seperti cara yang lalu. Misalkan sekarang diberikan sebuah informasi tertentu ITEM. Diminta untuk menentukan lokasi dari simpul list, yang pertama ditemui memuat informasi ITEM tersebut.

Di sini kita akan membahas dua algoritma pencarian, untuk maksud di atas. Algoritma yang pertama tidak menuntut bahwa list telah terurut, sementara algoritma kedua menuntutnya.

Kalau ITEM adalah key, yakni bahwa kita tengah melakukan pencarian dalam sebuah berkas untuk mendapatkan record yang mempunyai key ITEM, maka ITEM tersebut pasti tidak akan muncul lebih dari satu kali dalam list.


92

5.4.1 CARI DALAM LIST TIDAK TERURUT

Untuk list yang tidak terurut, kita dapat melakukan proses cari dengan cara yang cukup sederhana. Cara tersebut adalah melakukan traversal simpul list, sambil setiap kali memeriksa apakah informasi dalam simpul yang tengah dikunjungi tersebut sama dengan ITEM.

Jadi dalam algoritma ini, kita memerlukan 2 buah pemeriksaan pada setiap putaran. Yang pertama adalah memeriksa apakah kita telah sampai pada akhir dari list, yakni dengan memeriksa apakah PTR = NULL. Yang kedua adalah memeriksa apakah ITEM telah diketemukan lokasinya, yakni dengan memeriksa apakah INFO(PTR):=ITEM.

ALGORITMA

Kompleksitas waktu dari algoritma ini adalah sama seperti kompleksitas waktu dari algoritma cari linier terhadap larik. Di sini worst-case running time adalah sebanding dengan n, banyaknya elemen list. Sedangkan average-case mendekati n/2. Di sini dengan catatan, kondisi adalah ITEM muncul paling banyak satu kali, serta probabilitas kemunculan ITEM dalam setiap simpul adalah sama.

Contoh 5.6

Pandang berkas personalia pada Gambar 5.7 yang lalu. Modul berikut ini akan mencari lokasi pegawai dengan SSN = NNN dan kemudian menaikkan gajinya sebesar 5 persen.

SEARCH(INFO, LINK, START, ITEM, LOC) 1 PTR := START 2 Kerjakan langkah 3 dalam hal PTR <> NULL 3 Jika INFO(PTR) = ITEM maka LOC := PTR exit kalau bukan PTR := LINK(PTR) 4 LOC := NULL (pencarian gagal) 5 Exit

1 Baca NNN 2 Panggil Prosedur

SEARCH(SSN,LINK,START,NNN,LOC) 3 Jika LOC <> NULL maka SALARY(LOC) = 1.05 * SALARY(LOC) kalau tidak Tulis NNN tidak ada dalam berkas


93

5.4.2 CARI DALAM LIST TERURUT

Untuk list yang terurut, kita dapat melakukan pencarian dengan cara yang hampir sama seperti dalam list yang tidak terurut. Cara tersebut adalah dengan melakukan traversal simpul list, sambil setiap kali memeriksa apakah informasi dalam simpul yang tengah dikunjungi tersebut, sama dengan ITEM. Karena terurutnya list, kita tidak perlu melakukan traversal sampai akhir dari list, walau ITEM tidak terdapat dalam list.

Begitu INFO(PTR) > ITEM, kita sudah boleh menghentikan pencarian kita. Jadi dalam algoritma ini, kita memerlukan 2 buah pemeriksaan pada setiap putaran. Yang pertama adalah memeriksa apakah ITEM sudah lebih besar dari INFO(PTR), yang berarti ITEM tidak terdapat dalam list, dan kita boleh menghentikan proses cari kita. Yang kedua adalah memeriksa apakah ITEM telah diketemukan lokasinya, yakni dengan memeriksa apakah INFO(PTR) := ITEM.

ALGORITMA

Kompleksitas waktu dari algoritma ini juga sama seperti kompleksitas waktu dari algoritma cari linear terhadap larik. Di sini worst-case running time adalah sebanding dengan n, banyaknya elemen list. Sedangkan average-case mendekati n/2.

Dapat dicatat bahwa untuk larik terurut, kita dapat menggunakan cari binar (binary search), yang waktu pelaksanaannya sebanding dengan log2n. Namun algoritma cari binar ini tidak dapat digunakan terhadap linked list terurut, karena kita tidak mempunyai cara untuk mengindeks elemen tengah dari list. Sifat ini adalah salah satu kelemahan pemakaian linked list sebagai sebuah struktur data.

SEARCH(INFO,LINK,START,ITEM,LOC) 1 PTR := START

2 Kerjakan langkah 3 dalam hal PTR <> NULL

3 Jika INFO(PTR) < ITEM maka PTR := LINK(PTR) bila tidak Jika ITEM = INFO(PTR) maka LOC := PTR Exit kalau tidak LOCK := NULL Exit

4 LOC := NULL


94

Contoh 5.7

Pandang sekali lagi, berkas personalia pada Gambar 5.7 yang lalu. Modul berikut ini akan mencari lokasi pegawai dengan NAMA = EMP dan kemudian menaikkan gajinya sebesar 5 persen.

1. Baca EMP 2. Panggil prosedur SEARCH(NAMA, LINK, START, EMP, LOC) 3. Jika LOC <> NULL Maka SALARY(LOC) := 1.05 * SALARY(LOC) kalau tidak Tulis EMP tidak ada dalam Berkas

Di sini kita dapat menggunakan algoritma cari untuk list terurut, karena NAMA telah terurut alfabetik.

5.5 ALOKASI MEMORI : KOLEKSI SAMPAH

Ketika kita menyimpan linked list dalam memori, diasumsikan bahwa selalu dapat dilakukan penyisipan (insertion) simpul baru ke dalam list, serta penghapusan (deletion) simpul dari list.

Untuk itu kita memerlukan suatu mekanisme guna menyediakan memori bagi simpul baru, ataupun guna mengelola memori yang sementara ini tidak berguna karena adanya penghapusan simpul, untuk sewaktu-waktu dapat dipakai lagi.

Untuk itu, biasanya bersama-sama dengan linked list dalam memori, ditempatkan juga list khusus yang berisi sel memori yang tak digunakan. List ini yang dilengkapi penuding sendiri, disebut list dari ruang yang tersedia, atau free-storage list atau free-pool.

Pandang linked list yang ditempatkan sebagai larik sejajar seperti dibicarakan yang lalu, dan katakanlah dilakukan beberapa penyisipan dan penghapusan simpul. Sel memori dari larik, yang tak digunakan, dihimpun menjadi sebuah linked list lain yang menggunakan variabel penuding list berupa larik AVAIL. Karena itu free-storage list ini biasa disebut list AVAIL. Struktur data serupa ini acap kali dituliskan sebagai :

LIST(INFO, LINK, START, AVAIL)


95

Contoh 5.8

Pandang daftar pasien pada contoh Gambar 5.3 yang lalu. Kali ini, daftar kita simpan dalam dua larik BED dan LINK. Di sini tempat tidur K dinyatakan sebagai BED(K). Maka ruang yang tersedia dalam larik BED tersebut dapat dikaitkan seperti pada Gambar 5.9.

Perhatikan bahwa BED(10) merupakan tempat tidur pertama yang tersedia, BED(2) adalah tempat tidur berikutnya, dan BED(6) merupakan yang terakhir tersedia. Karenanya BED(6) mempunyai field nextpointer nol atau LINK(6) = 0.

5

START

PATIENT

3

4

6

BEDNUMBER

1

2

3

4

5

6

7

8

9

10

11

12 12

10

9

8

1

11

12

3

4

0

8

9

1

7

Next

2

5

7

11

Kirk

Dean

Maxwell

Adams

Lane

Green

Samuels

Fields

Nelson

Gambar 5.9. Sel memori yang tidak digunakan

10

AVAIL

2

6

0

Contoh 5.9

(a) Ruang tersedia dalam larik TEST, pada Gambar 5.5, dapat dikaitkan seperti terlihat pada Gambar 5.10. Perhatikan bahwa masing-masing list ALG dan GEOM boleh menggunakan list AVAIL. Dapat dicatat bahwa AVAIL = 9, maka TEST(9) adalah simpul bebas yang pertama dalam list AVAIL tersebut. Karena LINK(AVAIL) = LINK(9) = 10, maka TEST(10) adalah simpul bebas kedua dalam AVAIL. Demikian selanjutnya.

b. Larik NAME dapat dikaitkan seperti pada Gambar 5.11. Perhatikan bahwa list ruang bebas dalam NAME mengandung elemen NAME(8), NAME(11), NAME(13),


96

NAME(5), dan NAME(1). Selanjutnya perhatikan nilai LINK yang secara bersama mendaftar ruang bebas untuk larik SSN, SEX dan SALARY.

11

5

ALG

GEOM

1

2

3

4

5

6

7

8

9

10

11

12

TEST LINK

13

14

15

16

AVAIL

9

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.10. Koleksi memori kosong dari Gambar 5.5

(c) Ruang tersedia dalam larik CUSTOMER pada Gambar 5.6, dapat dikaitkan secara Gambar 5.12. Kita tekankan bahwa masing-masing dari keempat list dapat menggunakan list AVAIL untuk pelanggan baru.

Contoh 5.10

Pandang LIST(INFO,LINK,START,AVAIL) mempunyai ruang memori untuk n = 10 simpul. Lebih lanjut pandang bahwa list pada keadaan awal adalah hampa. Gambar 5.13 menunjukkan nilai LINK sedemikian sehingga list AVAIL berisi barisan INFO(1), INFO(2), …, INFO(10).


97

6

8

START

AVAIL

0

Kelly 7

12

Green 14

Lewis

Cohen

Evans

1

9

10

2

0

13

4

1

2

3

4

5

6

7

8

9

10

11

12

11

NAMA LINK

Gambar 5.11 Koleksi memori kosong dari Gambar 5.7

Davis

Brown

Rubin

13

14 Harris

165-64-3351

175-56-2251

181-58-9939

177-44-4557

168-56-8113

SSN

192-38-7282

178-52-1065

135-46-6262

208-56-1654

Female

Male

Male

Male

Female

SEX

Male

Male

Male

Male

19,000

27,200

16,400

19,000

34,200

SALARY

22,800

14,700

15,500

22,800

5

3

KOLEKSI SAMPAH

Setelah penghapusan suatu simpul dari linked list, terdapat ruang memori yang bebas (tidak terpakai). Kita menginginkan ruang memori tersebut dapat digunakan lagi. Jelasnya kita menginginkan tersedianya ruang untuk kelak dapat kita pakai.

Salah satu caranya adalah memasukkannya segera ke dalam list ruang-bebas. Hal inilah yang kita kerjakan kalau kita mengimplementasikan linked list melalui larik, bahkan meskipun metode ini sangat memakan banyak waktu dalam sistem operasi komputer.

Untuk ini kita mungkin mengambil alternatif metode dengan sistem operasi dapat secara periodik mengumpulkan semua ruang akibat penghapusan simpul list tersebut ke dalam list ruang-bebas. Metode ini dikenal sebagai “koleksi sampah” atau garbage collection.


98

11

AVAIL

0 14

12

0

20

9

13

10

19

18

17

1

2

3

4

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

15

16

17

18

19

20

Adams

Scott

Weston

McBride

Grant

Jones

Teller

Rogers

Vito 4

16

0

6

0

5

1

2

8

7

Gambar 5.12. Koleksi memori kosong dari Gambar 5.6

Kerap kali kita ingin menambahkan data ke dalam suatu struktur data. Namun hal tersebut tak dapat dilaksanakan lagi, karena sudah tak ada lagi ruang yang tersedia, yakni dalam hal list ruang-bebas adalah hampa. Keadaan ini disebut overflow.


99

1

AVAIL

4

5

6

8

10

0

9

LINKINFO

1

2

3

4

5

6

7

8

9

10

2

3

7

0

START

Gambar 5.13. Memori dalam keadaan hampa

5.6 PENYISIPAN SIMPUL KE DALAM LINKED LIST

Misalkan LIST adalah linked list, dengan A dan B adalah dua simpul yang berurutan. Lihat Gambar 5.14(a). Misalkan sebuah simpul baru N akan disisipkan ke dalam LIST, antara simpul A dan simpul B. Diagram skematik dari proses penyisipan ini terlihat dalam Gambar 5.14(b). Di sini simpul A sekarang menuding ke simpul baru N, dan simpul baru N menuding ke simpul B, yang tadinya dituding oleh A.

Pandang bahwa linked list kita tersimpan di dalam memori dalam bentuk:

LIST(INFO,LINK,START,AVAIL)

Gambar 5.14 tidak dapat memperlihatkan bahwa simpul baru N memanfaatkan ruang memori dari list AVAIL. Untuk kemudahan dalam proses, simpul pertama dari list AVAIL dipakai untuk menyimpan simpul baru N tersebut. Diagram skematik yang lebih tepat, terlihat pada Gambar 5.15.


100

x

START

Gambar 5.14(a) Linked-list awal

Node A Node B

x

START

Node A Node B

Node N

Gambar 5.14(b) Penyisipan simpul N

Perhatikan bahwa field penuding berubah sebagai berikut :

1. Field nextpointer dari simpul A, sekarang menuding ke simpul baru N, ter-hadap mana, sebelumnya AVAIL menuding.

2. AVAIL sekarang menuding ke simpul kedua pada ruang bebas, terhadap mana, sebelumnya simpul N menuding.

3. Field nextpointer dari simpul N, sekarang menuding ke simpul B, yang tadinya dituding oleh simpul A.

Di sini juga terdapat 2 kasus khusus, yakni jika simpul baru N adalah simpul pertama dalam list, maka START akan menuding ke N, dan jika simpul baru N adalah simpul terakhir dalam list, maka N akan berisi penuding nol.

Contoh 5.11

a. Pandang Gambar 5.9, yakni daftar alfabetik pasien. Misalkan seorang pasien baru Hughes masuk. Perhatikan bahwa :

(1) Hughes ditempatkan di ranjang 10, yakni ranjang pertama yang kosong (tersedia).

(2) Hughes akan disisipkan dalam list, antara Green dan Kirk.


101

Terjadi 3 perubahan dalam field penuding, sebagai berikut :

LINK(8) = 10 (Sekarang Green menuding Hughes)

LINK(10) = 1 (Sekarang Hughes menuding Kirk)

AVAIL = 2 (Sekarang AVAIL menuding ranjang kosong kedua)

x

START

Node A Node B

x

AVAIL

Gambar 5.15 Penyisipan simpul N menghilangkan 1 lokasi memori di AVAIL

Node N

b. Pandang Gambar 5.12, daftar broker dan pelanggannya. Karena list pelanggan tidak terurut, asumsikan bahwa setiap pelanggan baru ditambahkan pada awal list. Misalkan Gordan adalah pelanggan baru dari Kelly. Perhatikan bahwa :

(1) Gordan dimasukkan sebagai CUSTOMER(11), yakni simpul tersedia pertama

(2) Gordan disisipkan di muka Hunter, yang tadinya adalah pelanggan pertama dari Kelly.

Di sini terjadi 3 perubahan dalam field penuding, yakni sebagai berikut :

POINT(2) = 11 (Sekarang list mulai dengan Gordan)

POINT(11) = 3 (Gordan menuding Hunter)

AVAIL = 18 (Sekarang AVAIL menuding ke simpul tersedia yang berikutnya).

c. Pandang bahwa elemen data A, B, C, D, E, dan F akan dimasukkan berturut-turut ke dalam list hampa Gambar 5.13. Sekali lagi kita asumsikan bahwa data disi-sipkan pada bagian awal list. Berdasarkan ini, sesudah 6 kali penyisipan, F menu-ding ke E; E menuding ke D, D menuding ke C, C menuding ke B, B menuding ke A. A berisi penuding nol. Di sini AVAIL = 7, yakni simpul pertama yang tersedia sesudah 6 penyisipan di atas, dan START = 6 yang menunjukkan lokasi simpul


102

pertama F. Gambar 5.16 menunjukkan list, setelah 6 penyisipan tersebut (untuk n = 10)

7

AVAIL

2

3

4

8

10

0

9

LINKINFO

1

2

3

4

5

6

7

8

9

10

0

1

5

6

STARTAB

EDC

F

Gambar 5.16. Penyisipan enam INFO dalam sebuah linked list

5.6.1 ALGORITMA PENYISIPAN

Algoritma penyisipan dapat kita bagi atas beberapa situasi atau kasus. Di sini kita bicarakan tiga di antaranya, yakni algoritma penyipan simpul pada bagian awal list, algoritma penyisipan simpul sesudah suatu simpul yang diketahui lokasinya, dan yang ketiga adalah penyisipan simpul ke dalam suatu list terurut.

Semua algoritma kita tersebut berasumsi bahwa linked list tersimpan di dalam memori dalam bentuk :

LIST(INFO,LINK,START,AVAIL) dan variabel ITEM menyatakan informasi baru yang akan ditambahkan ke dalam list. Karena semua algoritma penyisipan kita tersebut membutuhkan simpul dari list AVAIL, maka mereka selalu mengandung langkah :

1. Memeriksa ruang bebas dari list AVAIL, kalau ternyata tidak ada lagi, yakni dalam hal ini AVAIL = NULL, algoritma mengirim pesan overflow.

2. Pemindahan simpul pertama dari list AVAIL. Menggunakan variabel NEW kita dapat mengimplementasikan pemindahan ini melalui sepasang statement.


103

NEW := AVAIL

AVAIL := LINK(AVAIL)

3. Menyalin informasi baru tersebut ke dalam simpul baru, atau dengan perkataan lain, kita memakai statement

INFO(NEW) := ITEM

Diagram skematik kedua langkah terakhir di atas terlihat pada Gambar 5.17.

NEW

x

AVAIL

ITEM

Free storage list

Gambar 5.17. Penyisipan simpul yang mengubah penuding AVAIL

5.6.2 PENYISIPAN PADA BAGIAN AWAL LIST

Di sini linked list kita tidak perlu terurut dan penyisipan tidak harus di suatu posisi tertentu. Maka posisi termudah untuk memasukkan simpul baru adalah di bagian awal list.

ALGORITMA : INSFIRST(INFO,LINK,START,AVAIL,ITEM) [Algoritma ini menyisipkan ITEM sebagai simpul pertama dari list.]

1. (Apakah overflow?)

Jika AVAIL = NULL maka tulis OVERFLOW dan exit

2. (Memindahkan simpul pertama dari list AVAIL)


104

NEW := AVAIL dan AVAIL := LINK[AVAIL]

3. INFO[NEW] := ITEM

(menyalin data baru ke dalam simpul baru)

4. LINK[NEW] := START

(Simpul baru sekarang menuding ke simpul awal semula)

5. START := NEW

(Mengubah START agar menuding ke simpul yang baru)

6. Exit.

Langkah 1 sampai 3 telah dibahas sebelum ini, dan diagram skematik langkah 2 dan 3 terlihat pada Gambar 5.17. Sedangkan diagram skematik langkah 4 dan 5 dapat dilihat pada Gambar 5.18.

START

xNEW

Gambar 5.18 Penyisipan di awal list

ITEM

Contoh 5.12

Pandang list pada Gambar 5.10. Misalkan angka 75 akan disisipkan pada awal dari list geometri. Kita akan memakai algoritma di atas. Perhatikan bahwa ITEM = 75, INFO = TEST, dan START = GEOM.

INSFIRST(INFO,LINK,START,AVAIL,ITEM) 1. Karena AVAIL <> NULL, kita pergi ke langkah 2

2. NEW = 9, maka AVAIL := LINK[9) = 10

3. TEST[9] = 75


105

4. LINK[9] = 5

5. GEOM = 9

6. Exit

Gambar 5.19 memperlihatkan keadaan setelah 75 dimasukkan ke dalam list geometri. Perhatikan bahwa hanya 3 penuding yang berubah, yakni AVAIL, GEM, dan LINK[9].

11

9

ALG

GEOM

1

2

3

4

5

6

7

8

9

10

11

12

TEST LINK

13

14

15

16

AVAIL

10

74

82

84

78

74

100

88

62

74

93

16

14

1

0

12

0

8

13

5

3

2

7

6

4

0

15

75

Gambar 5.19. Penyisipan nilai 75 pada awal list GEOM


106

5.6.3 PENYISIPAN PADA BAGIAN DEPAN LIST

Pandang bahwa diberikan nilai dari LOC, yakni lokasi dari simpul A di dalam linked list, atau nilai LOC = NULL. Berikut ini adalah algoritma untuk menyisipkan ITEM ke dalam list, tepat sesudah simpul A, atau jika LOC = NULL, maka ITEM disisipkan sebagai simpul pertama dari list. Misalkan N adalah simpul baru, yang lokasinya adalah NEW. Jika LOC = NULL, maka penyisipan dikerjakan seperti pada algoritma yang lalu. Dalam hal lain, seperti terlihat pada Gambar 5.15, kita jadikan N menuding ke simpul B (simpul yang sebelumnya mengikuti simpul A) dengan menggunakan statement :

LINK[NEW] := LINK[LOC] dan kita jadikan simpul A menuding ke simpul baru N, dengan menggunakan statement:

LINK[LOC] := NEW

Algoritma : INSLOC(INFO,LINK,START,AVAIL,LOC,ITEM) [Algoritma ini dimaksudkan untuk menyisipkan ITEM, sehingga mengikuti simpul dengan lokasi LOC atau menyisipkan ITEM sebagai simpul pertama, bila LOC = NULL].

1. [OVERELOW?] jika AVAIL = NULL, maka tulis: OVERFLOW, dan Exit.

2. [Memindahkan simpul pertama dari List AVAIL]

NEW := AVAIL

AVAIL := LINK[AVAIL]

3. AVAIL-ITEM. [menyalin data baru ke dalam simpul baru]

4. Jika LOC = NULL, maka [sisipkan sebagai simpul pertama]

LINK(NEW) := START dan START := NEW.

dalam hal lain : [sisipkan sesudah simpul dengan lokasi LOC]

LINK[NEW] := LINK[LOC] dan LINK[LOC] := NEW

[Akhir dari struktur jika]

5. Exit

5.6.4 PENYISIPAN KE DALAM LINKED LIST TERURUT

Misalkan ITEM akan disisipkan ke dalam linked list terurut LIST. ITEM harus disisipkan di antara simpul A dan B yang berturutan sedemikian sehingga :


107

INFO(A)< ITEM< INFO(B).

x

START

Gambar 5.20 Penyisipan simpul pada list terurut

SAVE PTR

Berikut ini prosedur untuk mencari lokasi dari simpul A, yakni mencari lokasi dari simpul terakhir dari LIST yang nilainya kurang dari ITEM. Kita lakukan traversal list, pergunakan variabel penuding PTR, dan bandingkan ITEM dengan INFO (PTR) pada masing-masing simpul selama traversal. Kita jaga jejak lokasi simpul sebelumnya, dengan menggunakan variabel penuding SAVE, seperti digambarkan pada Gambar 5.20. Maka SAVE dan PTR terupdate dengan statement :

SAVE := PTR dan PTR :LINK[PTR] Traversal dilanjutkan selama INFO[PTR] < ITEM, atau dengan perkataan lain

traversal berhenti segera saat ITEM <= INFO[PTR]. Kemudian PTR menuding ke simpul B, maka SAVE berisi lokasi dari simpul A. Berikut ini prosedur formal kita. Kasus bahwa list adalah hampa, dan ITEM < INFO[START], sehingga LOC := NULL ditangani tersendiri, karena mereka tak mengandung variabel SAVE.

Prosedur : FINDA(INFO, LINK, START, ITEM, LOC) [Prosedur ini akan menemukan lokasi LOC dari simpul terakhir dalam list terurut, sedemikian sehingga INFO[LOC] < ITEM, atau menjadikan LOC := NULL]

1. (List hampa?] Jika START := NULL, maka LOC := NULL, dan return

2. (Kasus khusus?] Jika ITEM < INFO[START], maka LOC := NULL, dan return

3. SAVE := START dan PTR := LINK[START] [mengawali penuding]

4. Ulangi langkah 5 dan 6 sementara PTR <> NULL

5. Jika ITEM < INFO[PTR], maka :

LOC := SAVE, dan return.



108

6. SAVE := PTR dan PTR := LINK[PTR] [mengupdate penuding]

[Akhir dari loop langkah 4]

7. LOC := SAVE

8. Return.

Sekarang kita mempunyai algoritma untuk menyisipkan ITEM ke dalam linked list terurut LIST, dengan memanfaatkan 2 prosedur terakhir.

Algoritma : INSSRT(INFO, LINK, START, AVAIL, ITEM) [Algoritma ini menyisipkan ITEM ke dalam suatu linked list terurut.

1. [Gunakan Prosedur FINDA untuk mencari lokasi dari simpul sebelum ITEM] Call FINDA(INFO, LINK, START, ITEM, LOC).

2. [Gunakan algoritma INSLOC untuk menyisipkan ITEM sesudah simpul dengan lokasi LOC]

Call INSLOC(INFO,LINK,START,AVAIL,LOC,ITEM)

3. Exit

Contoh 5.13

Perhatikan list yang terurut secara alfabetik dari para pasien pada Gambar 5.9 yang lalu. Pandang bahwa Jones akan disisipkan ke dalam list tersebut. Kita akan menggunakan algoritma INSSRT di atas, yang pada hakikatnya melaksanakan prosedur FINDA, dan kemudian algoritma INSLOC. Perhatikan bahwa ITEM = Jones dan INFO = BED.

a. FINDA(BED,LINK, START,ITEM,LOC)

1. Karena START <> NULL, maka kita melangkah ke langkah 2 2. Karena BED[5] = Adams < Jones, kendali beralih ke langkah 3 3. SAVE = 5 dan PTR LINK[5] = 3 4. Langkah 5 dan 6 diulang, sebagai berikut :

a. BED[3] = Dean < Jones, maka SAVE = 3, dan PTR LINK[3] = 11 b. BED[11] = Fields < Jones, maka SAVE = 11, dan PTR = LINK[11] = 8 c. BED[8] = Green < Jones, maka SAVE = 8, dan PTR = LINK[8] = 1 d. BED[1] = Kirk > Jones, maka LOC = SAVE =8, dan Return


109

b. INSLOC(BED,LINK,START,AVAIL,LOC,ITEM)

1. Karena AVAIL <> NULL, maka kita melangkah ke langkah 2 2. NEW = 10, dan AVAIL = LINK[10] = 2 3. BED[10] = Jones 4. Karena LOC <> NULL, maka LINK[10] = LINK(8] =1, dan LINK[8]= NEW = 10 5. Exit

Gambar 5.21 menunjukkan struktur data kita sesudah Jones disisipkan ke dalam list. Di sini hanya 3 penuding yang berubah, yakni AVAIL, LINK[10], dan LINK[8].

PENYALINAN

Pandang bahwa kita ingin menyalin seluruh bagian dari list, atau akan membentuk sebuah list baru, yang diperoleh dari penyambungan 2 list yang diketahui. Kita dapat melakukannya dengan mendefinisikan sebuah list hampa, dan menambahkan elemen list yang diketahui tersebut, satu persatu menggunakan berbagai macam algoritma penyisipan kita yang lalu.

List hampa didefinisikan dengan cara sederhana, yakni dengan mengambil sebuah nama variabel, atau penuding untuk list, seperti misalnya NAME, dan kemudian memasang NAME := NULL.

5

2

START

AVAIL

Kirk 7

Dean 11

6

Maxwell 12

Adams

Lane

Green

Samuels

Fields

Nelson

3

0

4

0

1

8

9

1

2

3

4

5

6

7

8

9

10

11

12

10

BED LINK

Jones

Gambar 5.21. Penyisipan ‘Jones’ dalam list terurut


110

5.7 PENGHAPUSAN SIMPUL LINKED LIST

Misalkan Simpul N adalah simpul dari LIST yang terletak di antara simpul A dan simpul B, seperti terlihat pada Gambar 5.22a. Simpul N tersebut akan dihapus dari LIST. Diagram skematik dari penghapusan tersebut terlihat pada Gambar 5.22b. Penghapusan terjadi begitu nextpointer dari A berubah menuding ke B. Dalam peng-hapusan ini, kita harus mengingat alamat dari simpul A, simpul pendahulu dari Simpul yang akan kita hapus tersebut.

Pandang linked list kita tersimpan dalam memori dalam bentuk :

LIST(INFO,LINK,START,AVAIL)

Gambar 5.22 tidak memperlihatkan fakta bahwa bila kita melakukan penghapusan simpul N, kita akan segera memulangkan ruang memori kepada list AVAIL. Diagram skematik yang lebih tepat terlihat pada Gambar 5.23. Perhatikan bahwa 3 field penuding berubah, yakni :

1. Nextpointer dari Simpul A sekarang menuding ke B, yang tadinya dituding oleh N.

2. Nextpointer dari Simpul N sekarang menuding ke simpul pertama dari ruang bebas (free pool), yang tadinya dituding oleh AVAIL.

3. AVAIL sekarang menuding ke simpul N

Di sana juga terdapat 2 kasus istimewa. Yang pertama adalah penghapusan simpul N sebagai simpul pertama dalam list. Dalam hal ini, START akan menuding ke simpul B. Dalam kasus kedua, yakni penghapusan simpul N sebagai simpul terakhir dari list, simpul A akan berisi penuding NULL.

Contoh 5.14

a. Perhatikan list pasien pada Gambar 5-21. Misalkan pasien Green sudah diper-bolehkan pulang, maka BED[8] sekarang menjadi kosong Agar linked list kita tersebut tetap terjaga, maka perlu dilakukan perubahan terhadap beberapa field penuding, yakni sebagai berikut :

LINK[11] = 10 LINK[8] = 2 AVAIL = 8


111

x

START

(a) sebelum dihapus

Node A Node B

Gambar 5.22 Penghapusan linked list

Node N

x

START

(b) sesudah dihapus

Node A Node BNode N

Dengan perubahan pertama, Fields yang tadinya mendahului Green, sekarang menuding ke Jones, yang tadinya mengikuti Green. Perubahan kedua dan ketiga akan menambah jumlah ranjang kosong baru pada list AVAIL. Kita tekankan bahwa sebelum membuat penghapusan, kita harus mencari simpul BED[11], yang tadinya menuding ke simpul yang dihapus, BED[8].

Gambar 5.23 Memori kosong setelah penghapusan simpul

x

START

Node A Node BNode N

AVAIL

x


112

b. Perhatikan Gambar 5.12, list para broker dan pelanggannya. Pandang Teller, pelanggan pertama dari Nelson, akan dihapus dari list. Untuk itu dilakukan peru-bahan:

POINT[4] = 10 LINK[9] = 11 AVAIL = 9

Dengan perubahan pertama, Nelson sekarang menuding ke Jones, yang tadinya adalah pelanggan kedua. Perubahan kedua dan ketiga akan menambah simpul baru pada list AVAIL.

c. Misalkan elemen data B dan C akan dihapus satu persatu dari list Gambar 5.16. List yang baru, digambarkan pada Gambar 5.24. Perhatikan bahwa sekarang ketiga simpul pertama yang tersedia adalah :

INFO[3], yang tadinya berisi C

INFO[2], yang tadinya berisi B

INFO[5], yang tadinya berisi E

3

AVAIL

2

1

7

8

10

0

9

LINKINFO

1

2

3

4

5

6

7

8

9

10

0

5

4

Gambar 5.24 Penghapusan 3 simpul dari Gambar 5.16

6

STARTA

D

F

Perhatikan bahwa urutan simpul dalam list AVAIL adalah berkebalikan dengan urutan penghapusan simpul tersebut.


113

5.7.1 ALGORITMA PENGHAPUSAN

Algoritma penghapusan simpul suatu linked list muncul dalam berbagai situasi. Di sini akan kita bahas 2 di antaranya. Yang pertama adalah penghapusan simpul sesudah suatu simpul yang diketahui, dan yang kedua adalah penghapusan simpul yang diketahui mempunyai informasi ITEM. Untuk algoritma kita, selalu diasumsikan, bahwa linked list adalah dalam bentuk :

LIST(INFO,LINK,START,AVAIL).

Semua algoritma penghapusan kita, selalu mengembalikan ruang memori dari simpul yang dihapus, kepada bagian awal dari list AVAIL. Karenanya, semua algoritma kita mengandung pasangan statement berikut ini :

LINK[LOC] := AVAIL

AVAIL := LOC

Di sini LOC adalah lokasi dari simpul N yang kita hapus. Kedua operasi di atas digambarkan pada Gambar 5.25.

Gambar 5.25 Penghapusan simpul yang dicatat oleh AVAIL

x

LOC

Node N

AVAIL

free storage list

Beberapa dari Algoritma kita adalah dimaksudkan untuk menghapus simpul pertama atau simpul terakhir dari list. Algoritma seperti itu harus memeriksa apakah terdapat simpul di dalam List. Jika START = NULL, maka algoritma harus mengeluarkan pesan “underflow.”


114

5.7.2 PENGHAPUSAN SIMPUL SESUDAH SIMPUL YANG DIKETAHUI

Berikut ini algoritmanya :

DEL(INFO, LINKSTART, AVAIL, LOC, LOCP) (Algoritma ini dimaksudkan untuk menghapus simpul N dengan lokasi LOC. LOCP adalah lokasi dari simpul yang mendahului N, atau apabila N adalah simpul pertama, LOCP = NULL

1. Jika LOCP= NULL, maka:

START := LINK[START]. [Menghapus simpul pertama] dalam hal lain : LINK[LOCP] = LINK[LOC] [Menghapus Simpul N]


2. [Mengembalikan simpul terhapus kepada list AVAIL]

3. Exit.

Gambar 5.26 merupakan diagram skematik dari Statement :

START := LINK[START]

START

Node 2Node 1 Node 3

Gambar 5.26. Pengalihan penuding ketika satu simpul dihapus

Gambar 5.27 merupakan diagram skematik dari statements :

LINK[LOCKP] := LINK[LOC]


115

x

START

Node N

LOCP LOC

Gambar 5.27 Skematik dari statements LINK[LOCKP] := LINK[LOC]

5.7.3 PENGHAPUSAN SIMPUL YANG DIKETAHUI INFORMASINYA

Algoritmanya, yakni algoritma DELLOC bekerja dengan memanfaatkan prosedur FINDB.

Procedure : FINDB(INFO,LINK,STARTJTEM,LOC,LOCP) [Prosedur ini dimaksudkan untuk mencari lokasi LOC dari simpul N pertama yang mengandung ITEM dan lokasi LOCP dari simpul pendahulu N. Jika ITEM tidak terdapat pada list, maka prosedur akan menjadikan LOC NULL, dan jika ITEM muncul pada simpul pertama, maka LOCP = NULL.

1. [List hampa?] Jika START := NULL, maka:

LOC := NULL, dan LOCP := NULL, dan return


2. [ITEM, di dalam simpul pertama?] Jika INFO[START] := ITEM, maka : LOC := START dan LOCP := NULL, dan Return.

3. SAVE := START dan PTR := LINK[START] [Inisialisasi Penuding]

4. Ulangi langkah 5 dan 6 sementara PTR <> NULL

5. Jika INFO[PTR] = ITEM, maka

LOC := PTR dan LOCP := SAVE, dan Return


6. SAVE := PTR dan PTR := LINK[PTR] [Mengupdate penuding]


7. LOC := NULL [cari tidak berhasil]


116

8. Return

Berikut ini algoritma lengkapnya

Algoritma : DELLOC(INFO, LINK, START, AVAIL, ITEM) (Algoritma ini dimaksudkan untuk menghapus dari suatu linked list, simpul N pertama yang berisi informasi ITEM)

1. [Gunakan prosedur FINDB di atas, untuk mencari lokasi dari N dan simpul pendahulunya]

Call FINDB(INFO, LINK, START, ITEM, LOC, LOCP)

2. Jika LOC := NULL, maka: tulis: ITEM tidak dalam list, dan Exit.

3. [Hapus simpul.]

Jika LOCP := NULL, maka:

START := LINK[START]. [Hapus simpul pertama]

Jika tidak:

LINK[LOCP] := LINK(LOC]


4. [Mengembalikan simpul terhapus ke list AVAIL]

LINK[LOC] := AVAIL dan AVAIL := LOC.

5. Exit.

Contoh 5.15

Pandang list pasien pada Gambar 5.21. Misalkan pasien Green diperbolehkan pulang. Untuk menghapusnya dari list, kita laksanakan prosedur FINDB dan algoritma DELLOC di atas. Di sini ITEM Green, INFO = BED, START = 5, dan AVAIL = 2.

(a). FINDB(BED,LINK,START,ITEM,LOC,LOCP)

1. Karena START <> NULL, kita lanjutkan ke langkah 2

2. Karena BED[5] = Adams <> Green, kita lanjutkan ke langkah 3


117

3. SAVE = 5 dan PTR = LINK[5] = 3

4. Langkah 5 dan 6 diulangi sebagai berikut :

a. BED[3] = Dean <> Green, maka SAVE = 3, dan PTR LINK[3] =11

b. BED[11] = Fields <> Green, maka SAVE = 11, dan PTR = LINK[11] = 8

c. BED[8] = Green, maka kita peroleh

LOCP = PTR = 8, dan LOCP = SAVE = 11, dan Return

5

8

START

AVAIL

Kirk 7

Dean 11

6

Maxwell 12

Adams

Lane

Samuels

Fields

Nelson

3

0

4

0

1

10

9

1

2

3

4

5

6

7

8

9

10

11

12

2

BED LINK

Gambar 5.28 Penghapusan sebuah simpul

Jones

(b) DELLOC(BED,LINK,START,AVAIL, ITEM)

1. Call FINDB(BED,LINK,START,ITEM,LOC,LOCP), diperoleh LOC = 8, dan LOCP = 11

2. Karena LOC <> NULL, lanjutkan ke langkah 3

3. Karena LOCP <> NULL, kita peroleh

LINK[11] = LINK[8] = 10

4. LINK[8] = 2, dan AVAIL = 8

5. Exit.


118

Gambar 5.28 menunjukkan struktur data setelah Green dihapus dari list. Kita lihat bahwa hanya 3 penuding berubah, yakni LINK[11], LINK[8], dan AVAIL.

5.8 HEADER LINKED LIST

Header linked list adalah suatu linked list yang mengandung suatu simpul khusus yang terletak pada bagian awal dari list, yang disebut simpul header. Berikut ini 2 jenis header linked list yang biasa digunakan, yakni :

1. Grounded Header list, yang adalah header list yang simpul terakhirnya berisi penuding NULL. Kata grounded dipakai karena banyak buku menggunakan simbol listrik grounded (dibumikan) untuk menunjukkan penuding NULL.

2. Circular Header List adalah header list yang simpul terakhimya menuding ke simpul header dari list tersebut.2.

Gambar 5.29 merupakan diagram skematik dari header list tersebut. Biasanya jika tidak disebutkan apa-apa, maka kita maksudkan header list adalah circular. Perhatikan bahwa penuding dari list, yakni START selalu menuding ke simpul header. Karenanya LINK[START] = NULL menunjukkan bahwa grounded header list adalah hampa, dan LINK[START] = START menunjukkan bahwa circular header list adalah hampa.

x

START

(a) Grounded header listSTART

Gambar 5.29 Dua macam header list

Headernode

(b) Circular header list

Headernode


119

Meskipun data kita simpan dalam memori sebagai header list, namun list AVAIL tetap disimpan sebagai linked list biasa.

Contoh 5.16

Perhatikan berkas Personalia pada Gambar 5.11. Data akan kita simpan sebagai header list seperti pada Gambar 5.30. Perhatikan bahwa sekarang LOC = 5 adalah lokasi dari record header. Karenanya, START = 5, dan karena Rubin adalah pegawai terakhir, maka LINK[10] = 5. Header dapat pula dipakai menyimpan informasi tentang isi berkas. Sebagai contoh, misalkan SSN[5] = 9 menunjukkan banyaknya pegawai, dan SALARY[5] = 191.600 menunjukkan total gaji yang dibayarkan kepada pegawai.

5

8

START

AVAIL

0

Kelly 7

12

Green 14

Lewis

Cohen

Evans

6

9

10

2

5

13

4

1

2

3

4

5

6

7

8

9

10

11

12

11

NAMA LINK

Gambar 5.30 Contoh header linked-list

Davis

Brown

Rubin

13

14 Harris

165-64-3351

175-56-2251

181-58-9939

177-44-4557

168-56-8113

SSN

192-38-7282

178-52-1065

135-46-6262

208-56-1654

Female

Male

Male

Male

Female

SEX

Male

Male

Male

Male

19,000

27,200

16,400

19,000

34,200

SALARY

22,800

14,700

15,500

22,800

1

3

009 191,600


120

5.9 ALGORITMA UNTUK HEADER LINKED LIST

Algoritma berikut ini dimaksudkan untuk melakukan kunjungan atau traversing simpul suatu circular header list (traversal dalam circular header list) :

Algoritma (Traversal dalam circular header list)

Misalkan LIST adalah circular header list dalam memori. Algoritma ini akan melakukan traversal LIST. Kita gunakan operasi proses terhadap setiap simpul dari LIST.

1. PTR:=LINK[START] [inisialisasi pnuding PTR)

2. Ulangi langkah 3 dan 4 sementara PTR <> START;

3. Proses INFO[PTR]

4. PTR := LINK[PTR]. [PTR sekarang menuding ke simpul berikutnya]


5. Exit.

Selanjutnya diberikan algoritma untuk mencari lokasi LOC dari simpul yang pertama kali memuat informasi ITEM dalam list, atau menjadikan LOC = NULL, bila tidak ditemukan.

Algoritma : SRCHHL(INFO, LINK, START, ITEM, LOC) LIST adalah circular header list dalam memori. Algoritma ini untuk mencari lokasi LOC dari simpul yang pertama kali memuat informasi ITEM dalam list, atau men-jadikan LOC = NULL, bila tidak ditemukan.

1. PTR := LINK[START]

2. Ulangi sementara INFO[PTR] <> ITEM dan PTR <> START:

PTR := LINK[PTR] [PTR sekarang menuding ke simpul berikutnya [Akhir dari loop]

3. Jika INFO[PTR] := ITEM, maka

LOC := PTR

kalau tidak :

LOC := NULL.


4. Exit.


121

Selanjutnya adalah prosedur untuk mencari lokasi LOC dari simpul N pertama yang mengandung ITEM dan lokasi LOCP dari simpul pendahulu N. Jika ITEM tidak terdapat pada list, maka prosedur akan menjadikan LOC = NULL, dan jika ITEM muncul pada simpul pertama, maka LOCP = NULL. Prosedur ini berfungsi sama seperti Prosedur FINDB(INFO,LINK,START,ITEM,LOC,LOCP) untuk linked list biasa, yang telah dibahas terdahulu.

Prosedur : FINDBHL[INFO, LINK, START, ITEM, LOC, LOCP) 1 . SAVE := START dan PTR := LINK[START]; [inisialisasi penuding]

2. Ulangi sementara INFO[PTR] <> ITEM dan PTR <> START.

SAVE := PTR dan PTR := LINK[PTR]

[Mengupdate penuding]

[Akhir dari loop]

3. Jika INFO[PTR] := ITEM, maka

LOC := PTR dan LOCP := SAVE,

Kalau tidak LOC := NULL dan LOCP := SAVE.


4. Exit.

Berikut, terakhir sekali adalah algoritma yang fungsinya sama seperti algoritma DELLOC(INFO, LINK, START, AVAIL, ITEM) untuk linked list biasa, yakni untuk untuk menghapus, dari suatu circular header linked list, simpul N pertama yang berisi informasi ITEM.

Algoritma : DELLOCHL(INFO, LINK, START, AVAIL, ITEM) 1. [Gunakan Prosedur FINDBHL yang lalu untuk mencari lokasi dari N dan Simpul

pendahulunya]

Call LINDBHL(INFO, LINK, START, ITEM, LOC, LOCP)

2. Jika LOC = NULL, maka: tulis: ITEM tidak dalam list, dan Exit.

3. LINK[LOCP] := LINK[LOC]..[Menghapus Simpul]

4. [Mengembalikan simpul terhapus kepada List AVAIL]

LINK[LOC] := AVAIL dan AVAIL := LOC.

5. Exit.


122

Sebagai catatan, masih terdapat 2 lagi variasi dari linked list yang kadang-kadang muncul dalam literatur, yakni :

1. Linked list yang simpul terakhirnya menuding ke simpul awal. Linked list ini disebut Circular List.

2. Satu jenis lagi adalah linked list yang mempunyai simpul khusus (header) di bagian awal dan di bagian akhir list.

Gambar 5.31 merupakan diagram skematik kedua list tersebut.

START

(b) Linked list with header and trailer nodes

Headernode

(a) Circular linked list

x

Trailer node

START

Gambar 5.31. Dua variasi lain dari linked list

5.10 PENYAJIAN POLINOMIAL

Header linked list acap kali dipergunakan untuk menyimpan polinomial dalam memori. Di sini simpul header selalu merupakan bagian penting dalam penyajian, karena ia dibutuhkan untuk menyajikan polinomial nol.

Contoh 5.17

Pandang polinomial p(x).= 2x8 – 5x7 – 3x2 - 4. Polinomial ini dapat disimpan sebagai header list seperti terlihat pada Gambar 5-32a. Di sini masing-masing simpul berkorespondensi dengan suku tidak nol dari polinomial. Secara khusus, bagian informasi dari simpul dibagi menjadi dua field yang masing-masingnya berturut-turut menyajikan


123

koefisien dan eksponen dari suku yang bersangkutan, dan simpul dikaitkan berdasar atas derajat menurun.

Perhatikan bahwa variabel penuding POLY menuding ke simpul header, yang field eksponennya diberi nilai bilangan negatif, dalam hal ini adalah -1. Di sini penyajian larik dari list membutuhkan 3 larik linier, yang boleh kita sebut COEF, EXP dan LINK. Salah satu penyajian terdapat dalam Gambar 5.32b.

POLY

Gambar 5.32(a) Penyajian polinomial dalam linked list

0 -1 2 8 -5 7 -3 2 4 0

Coefficient of term

Exponent of term

1

2

POLY

AVAIL

-1

87

2

1

2

3

4

5

6

7

8---

EXP

Gambar 5.32(b) Penyajian polinomial dalam memori

n

COEF

3

4

5

6

8

7

1

9

LINK

0

---

---

---

0

2

- 5

- 3

4 0


124

5.11 LINKED-STACK dan LINKED-QUEUE

Bentuk lain dari struktur berkait adalah linked-stack dan linked-queue. Diagram skematik dari linked-stack dan linked-queue dilihat pada Gambar 5.33 dan 5.34.

Gambar 5.34 Linked-queue

TOP

a DATA LINK

Gambar 5.33. Linked stack

FRONT

data link

REAR

Operasi penghapusan dan penyisipan pada linked-stack sama seperti yang dilakukan pada stack biasa, yaitu pada TOP dari stack. Sedangkan operasi penyisipan dan penghapusan pada linked-queue juga sama seperti yang dilakukan pada queue bisa. Operasi penyisipan dilakukan pada REAR dan operasi penghapusan pada FRONT dari queue.

5.12. TWO WAY LIST

Linked list yang kita bicarakan sebelumnya adalah one way list. Selanjutnya, kita bicarakan bentuk lainnya yaitu two way list. Two way list adalah koleksi elemen data secara linear


125

yang disebut dengan nodes, yang setiap nodenya dibagi atas tiga bagian utama, yaitu : (1) nilai data atau informasi (INFO), (2) penuding ke alamat node sebelumnya (BACK), dan (3) penuding ke alamat node berikutnya (FORW).

Bila lokasi (alamat) suatu node dilambangkan dengan LOC, maka berlaku FORW(LOCA) = LOCB jika dan hanya jika, BACK(LOCB) = LOCA, atau “lokasi berikutnya dari node A adalah lokasi node B, jika dan hanya jika, lokasi sebelumnya dari node B adalah lokasi node A.”

Skema dari two way list dapat dilihat di Gambar 5.35. FIRST adalah penunjukkan node awal dan LAST adalah penandaan node terakhir. Skema pemetaan di memori dari two way list dapat dilihat di Gambar 5.36.

LASTFIRST

x x

Node N

INFO (nilai data dari node N)

BACK (penunjuk ke node sebelumnya)

FORW (penunjuk ke node berikutnya)

Gambar 5.35 Skema two way list

IN FOFIRST

4

BA CKFO RW

LA ST

8

7

A V A IL

1

2

3

4

5

6

7

8

9

L isa N .

Conny N .

N ur Lola

N ur Loli

M ardiana

9

3

6

0

5 0

41

58

12

80

8

Gambar 5.36. Contoh pemetaan di memori untuk two way list


126

5.13. TWO WAY HEADER LIST

Two way header list merupakan gabungan dari two way list dan circular header linked list. Intinya, pada two way list, FIRST atau START-nya mengarah ke header node, begitu juga node terakhirnya akan mengarah kembali ke header nodenya.

Node N

HeaderNode

START

Gambar 5.37 Skema two way header list

Berikut, pada Gambar 5.38 merupakan contoh penggunaan two way header list yang merupakan pengembangan dari header linked list yang ada di Gambar 5.30. Silakan Anda telusuri field FORW dan BACK-nya.

Operasi-operasi yang ada, seperti biasa, traversing (penelusuran), searching (pencarian), deleting (penghapusan), dan inserting (penyisipan) item-item data. Gambar 5.39 dan 5.40 memperlihatkan skema penghapusan dan penyisipan item data (simpul/ node). Silakan Anda buat programnya dengan bahasa pemrograman apapun yang Anda kuasai.

Algoritma penghapusan simpul :

DELTWL(INFO, FORW,BACK,START,AVAIL, LOC) 1. [Delete node]

Set FORW[BACK[LOC]] = FORW[LOC] and

BACK[FORW[LOC]] := BACK[LOC]

2. [Remove node to AVAIL list]

Set FORW[LOC] := AVAIL and AVAIL := LOC

3. Exit


127

5

8

START

AVAIL

0

Kelly 7

12

Green 14

Lewis

Cohen

Evans

6

9

10

2

5

13

4

1

2

3

4

5

6

7

8

9

10

11

12

11

NAMA FORW

Gambar 5.38 Contoh two way header linked-list

Davis

Brown

Rubin

13

14 Harris

165-64-3351

175-56-2251

181-58-9939

177-44-4557

168-56-8113

SSN

192-38-7282

178-52-1065

135-46-6262

208-56-1654

Female

Male

Male

Male

Female

SEX

Male

Male

Male

Male

19,000

27,200

16,400

19,000

34,200

SALARY

22,800

14,700

15,500

22,800

1

3

009 191,600

BACK

9

14

12

10

5

3

6

7

3

4

Node N

LOC

Gambar 5.39 Penghapusan node N


128

Algoritma penyisipan simpul :

INSTWL(INFO, FORW,BACK,START,AVAIL, LOCA,LOCB,ITEM) 1. [OVERFLOW ?] IF AVAIL = NULL, then Write : OVERFLOW and Exit

2. [Remove node from AVAIL list and copy new data into node.]

SET NEW := AVAIL, AVAIL = FORW[AVAIL], INFO[NEW] := ITEM

3. [Insert node into list.]

Set FORW[LOCA] := NEW, FORW[NEW] : = LOCB

BACK[LOCB] : = NEW, BACK[NEW] := LOCA

4. Exit

x

Node N

Node A Node B

LOCA LOCB

NEW

Gambar 5.40 Penyisipan node N


129

L A T I H A N 5

1. Jelaskan istilah ‘pointer’ dan link dalam linked list.

2. Bagaimana kunjungan (traversal) terhadap suatu link list ?

3. Buatlah suatu skema linked-list yang menggambarkan 10 buah abjad terurut. Sajikan skema tersebut ke penyajian dalam memori.

4. Lakukan penghapusan dua elemen dari soal nomor 3 di atas, yaitu elemen pertama dan elemen kelima.

5. Lakukan penambahan elemen di urutan elemen pertama dan ketujuh dari soal nomor 4 di atas (jadi tidak urut).

6. Ubah pointer-pointer linknya sehingga data di soal nomor 5 di atas menjadi terurut kembali.

7. Apa yang dimaksud dengan koleksi sampah (garbage collection) di linked-list ?

8. Apa yang dimaksud dengan header linked list dan apa saja jenisnya ?

9. Jelaskan perbedaan cara kerja one way list dan two way list ?

10. Apa yang dimaksud dengan two way header list ?

11. Buat program dengan bahasa pemrograman apapun untuk membuat ‘mesin’ linked list yang bisa dilakukan untuk menyisip dan menghapus elemen data.

linked list - elearning.gunadarma.ac.id · string yang dinyatakan oleh gambar 5.4 tersebut adalah...

Documents