BAB V LINKED LIST STRUKTUR BERKAIT. Struktur berkait adalah bentuk khusus dari list linier yang cara melinierkan urutannya dengan mengkaitkan setiap elemen datanya.
A 100
50
Pointer B 50 Alamat Memori
Gambar 5-1 : Logika Linked List Istilah yang digunakan dalam linked list. 1. SIMPUL / NODE / INFO Koleksi linier dari elemen data 2. PENUDING / POINTER / NEXT / LINK Yang menghubungkan satu elemen data ke elemen data lainnya 3. START Variabel penuding list yang berisi alamat dari simpul pertama dalam list 4. LIST NOL List yang disajikan dengan menempatkan pada penuding nol. Biasanya menunjukan akhir dari linked list. 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 bagian akhir dari LIST, NextPointer bernilai NULL. Apabila tidak disebutkan, nilai NULL adalah 0 dan nilai dari subskrip larik INFO serta LINK selalu diambil positif. Elemen linked list 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 diatas.
32
By : Anie
Co 5-1 : START 9
INFO
LINK
O T
6 0
X
11 10
N I E
3 4 7
1 2 3 4 5 6 7 8 9 10 11 12
Gambar 5-2 : Linked list dlm 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 merupakan sebuah string atau untai.
START = 9 LINK(9) = 3 LINK(3) = 6 LINK(6) = 11 LINK(11) = 7 LINK(7) = 10 LINK(10) = 4 LINK (4) = 0
Output INFO (9) N INFO (3) O INFO (6) INFO (11) E INFO (7) X INFO (10) I INFO (4) T LIST TERAKHIR
Co 5–2 : Pada bangsal sebuah rumah sakit terdapat 12 tempat tidur, sembilan diantaranya telah ditempati pasien. Kita hendak membuat list nama para pasien tersebut secara alfabetik.
33
By : Anie
BED NUMBER 1 2 3 4 5 6 7 8 9 10 11 12
START 5
PATIENT Kirk
NEXT 7
Dean Maxwell Adams
11 12 3
Lane Green Samuels
4 1 0
Fields Nelson
8 9
Gambar 5-3 : Linked list rumah sakit Lat 5 – 1 : 1. Buatlah output dari Co 5 – 2. 2. Suatu agen penjualan yang mempunyai 4 orang broker (perantara). Setiap broker mempunyai list customer (pelanggan) masing – masing. Data diorganisir dalam bentuk linked list. Tentukan pelanggan dari setiap perantara ! 1 2 3 4
BROKER BOND KELLY HALL NELSON
POINT 12 3 0 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
CUSTOMER VITO
LINK 4
HUNTER KATZ
14 0
EVANS
0
ROGERS TELLER JONES
15 10 19
GRANT
17
MCBRIDE WESTON
6 0
SCOTT
1
ADAMS
8
Gambar 5-4 : Double Linked list 34
By : Anie
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 berupa ini acap kali ditulis sebagai : LIST(INFO, LINK, START, AVAIL) Co 5-3 : Pandang daftar pasien yang lalu, kali ini daftar kita simpan dalam larik BED dan LINK. Disini pasien tempat tidur K dinyatakan sebagai BED(K). Maka ruang yang tersedia dalam larik BED tersebut dapat dikaitkan.
35
By : Anie
START 5
AVAIL 10
BED 1 2 3 4 5 6 7 8 9 10 11 12
PATIENT Kirk Dean Maxwell Adams Lane Green Samuels Fields Nelson
NEXT 7 6 11 12 3 0 4 1 0 2 8 9
Gambar 5-5 : Koleksi Sampah PENYISIPAN SIMPUL KE DALAM LINKED LIST Misalkan LIST adalah Linked List, dengan A dan B adalah dua simpul yang berurutan. Kemudian sebuah simpul baru N akan disisipkan ke dalam LIST antara simpul A dan simpul B. Simpul A sekarang menuding ke simpul baru N dan simpul N menuding ke simpul B yang tadinya dituding oleh A. START
NODE A
NODE B
X
START
NODE A
NODE B
X NODE N
Gambar 5-6 : Skematik penyisipan linked list Pandang bahwa linked list kita tersimpan di dalam memori dalam bentuk LIST(INFO, LINK, START, AVAIL)
36
By : Anie
Gambar 5-6 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. Perhatikan bahwa field penuding berubah sebagai berikut : 1. Field nextpointer dari simpul A, sekarang menuding ke simpul baru N, terhadap mana, sebelum 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. Disini 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. START
NODE A
NODE B
X
AVAIL
NODE N
X
Gambar 5-7 : Skematik penyisipan dgn avail Lat 5 – 2 : 1. Pada daftar alfabetik pasien, seorang pasien baru bernama Hughes masuk : a. Hughes ditempatkan di ranjang 10 b. Hughes disisipkan dalam list antara Green dan Kirk Jelaskan perubahan dalam field penudingnya ! 2. Pada daftar broker dan pelanggannya ditambahkan pelanggan baru bernama Gordan sebagai pelanggan Kelly : a. Gordan dimasukkan sebagai Customer(11) b. Gordan disisipkan di muka Hunter yang tadinya adalah pelanggan pertama kelly Jelaskan perubahan dalam field penudingnya ! 37
By : Anie
PENGHAPUSAN SIMPUL LINKED LIST Misalkan simpul N adalah simpul dari LIST yang terletak diantara simpul A dan simpul B. simpul N tersebut akan dihapus dari LIST. Penghapusan terjadi begitu nextpointer dari A berubah menuding ke B. Dalam penghapusan 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) Fakta menyatakan bahwa bila kita melakukan penghapusan simpul N, kita akan memulangkan ruang memori kepada list AVAIL. 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
START
NODE A
NODE N
NODE B
X
START
NODE A
NODE N
NODE B
X Gambar 5-8 : Skematik Penghapusan Linked List 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.
38
By : Anie
START
NODE A
NODE N
NODE B
X
AVAIL
X
Gambar 5-7 : Skematik penghapusan dgn avail Lat 5 – 3 : 1. Pada List pasien, pasien Green sudah diperbolehkan pulang, maka BED(8) sekarang menjadi kosong, agar linked list tetap terjaga, jelaskan perubahan penudingnya ! 2. Pada list broker dan pelanggannya, pelanggan bernama Teller dihapus dari list. Jelaskan perubahan linkednya !
39
By : Anie
