Buku Ajar Struktur Data Bagian
3 Tujuan Instruksional Khusus
Mahasiswa mampu menjelaskan struktur data linier List berkait. Mahasiswa mampu menjelaskan operasi-operasi yang dilakukan pada struktur data List berkait.
Pokok Bahasan
Struktur data List secara umum. Representasi List berkait dalam memori. Operasi pada List berkait: traversing, searching, Penyisipan, penghapusan.
stilah list sering digunakan dalam kehidupan sehari-hari dan merujuk pada daftar dari sejumlah item. Gambar 3.1(a) adalah daftar item barang yang akan dibeli, yang berisi elemen pertama, elemen kedua, . . . ., dan elemen terakhir. Sering terjadi, dari daftar tersebut ada yang item data dihapus dan ada item data yang akan ditambahkan. Gambar 3.1(b) adalah daftar item barang yang akan dibeli setelah ada 3 item data yang ditambahkan dan 2 item data yang dihapus.
I
Susu Telur Mentega Tomat Apel Jeruk Roti
(a)
Kadwi Suharsono
Susu Telur Mentega Tomat Apel Jeruk Roti Jagung buncis
(b) Gambar 3.1. Daftar belanja harian
50
Buku Ajar Struktur Data Pemrosesan data sering melakukan penyimpanan dan pemrosesan yang diorganisasikan ke dalam list. Salah satu cara untuk menyimpan data tersebut adalah dengan menggunakan array, seperti yang telah dibahas di bagian 2. Hubungan linier antara elemen data suatu array linier merefleksikan hubungan fisik data yang tersimpan dalam memori. Hal ini memudahkan dalam menghitung alamat elemen data array. Sebaliknya Array mempunyai kelemahan, misalnya, relatif terlalu mahal untuk menyisipkan dan mengahapus elemen dari suatu array. Karena array biasanya menempati suatu blok memori, sangat sulit untuk melipat gandakan atau menjadikan 3 kali lipat ukuran array pada waktu diperlukan. Oleh karena itu array disebut juga dengan struktur data statis. Cara lain untuk menyimpan list dalam memori adalah dengan menambah field ke dalam list sebagai pointer, yang berisi alamat dari elemen berikut dalam list. Elemen berikutnya dari suatu elemen tidak harus menempati lokasi memori yang berdekatan. Cara ini memudahkan dalam proses penyisipan dan penghapusan elemen dari list. Oleh karena itu jika diperlukan suatu aplikasi yang sering melakukan proses searching pada seluruh data agar dapat dilakukan proses penyisisipan dan penghapusan data ke dalam list, seperti pengolah kata, data sebaiknya tidak disimpan dalam array tetapi disimpan dalam list yang menggunakan pointer. Jenis struktur data berikut ini adalah list berkait (linked list). Suatu list berkait, atau list satu-arah adalah sekumpulan elemen data linier, yang disebut dengan simpul (node), urutan liniernya ditentukan oleh pointernya. Oleh karena itu setiap simpul dibagi menjadi 2 bagian, yaitu pertama berisi informasinya, dan bagian kedua yang berisi adalah field penghubung atau field pointer berikut, yang berisi alamat dari simpul berikutnya. Gambar 3.2 adalah diagram skematik dari suatu list berkait dengan 6 simpul, setiap simpul digambarkan memiliki 2 bagian. Sebelah kiri adalah adalah representasi dari bagian informasi dari simpul, yang dapat berupa keseluruhan record suatu item data, misalnya berisi data Nama, Alamat dan seterusnya. Bagian kanannya representasi dari field berikutnya simpul, yang digambarkan adanya anak panah yang menuju ke simpul berikutnya dalam list. Pointer dari simpul terakhir berisi nilai khusus, yang disebut dengan pointer null, yang merupakan alamat yang salah. Nama atau Start
field pointer berikut dari simpul 3 x
bagian informasi dari simpul 3
Gambar 3.2. list berkait dengan 6 simpul Dalam penggunaan praktis, angka 0 atau bilangan negatif digunakan untuk pointer null. Pointer null, dalam diagram disimbolkan dengan x, merupakan tanda akhir dari list. Suatu list berkait juga mempunyai variabel Kadwi Suharsono
51
Buku Ajar Struktur Data pointer, yang sering disebut dengan NAMA atau START, yang berisi alamat simpul pertama dari list; oleh karena itu dalam diagram terdapat panah dari Nama ke simpul pertama dari list. Pada kondisi tertentu, yaitu list tidak mempunyai simpul, atau listnya kosong, maka pointer NAMA atau START akan berisi pointer null. Contoh 3.1. Sebuah kamar rumah sakit berisi 12 tempat tidur, yang terisi 9 pasien, seperti yang tertera dalam gambar 3.3. Daftar pasien disusun berdasarkan nama secara alfabetis. Untuk itu diperlukan field pointer, NEXT. Di sini variabel START berisi 5, karena Arjuno adalah pasien menempati tempat tidur no 5. Arjuno memiliki pointer NEXT yang berisi 3. Karena Durno menempati tempat tidur no 3, maka Durno adalah pasien berikutnya Arjuno. Pointer NEXT-nya Durno berisi 11. Karena Fetruk menempati tempat tidur no 11, maka Fetruk adalah pasien berikutnya Durno. Dan seterusnya. Pointer simpul terakhir dalam list, Semar, berisi pointer Null, dengan simbol 0. Beberapa tanda panah diberikan untuk menunjukkan hubungan di antara simpul dalam list. START
5
Nobed
Pasien
Next
1 2 3 4 5 6 7 8 9 10 11 12
Kresno
7
Durno Mbilung Arjuno
11 12 3
Limbuk Gareng Semar
4 1 0
Fetruk Narodo
8 9
Gambar 3.3. List Berkait Pasien
Representasi List Berkait dalam Memori Jika LIST adalah sebuah list berkait, maka LIST tersebut akan disimpan di memori seperti berikut ini. Pertama, LIST memerlukan 2 array linier, misalnya INFO dan LINK. Isi dari INFO[K] adalah bagian informasi dan isi LINK[K] adalah pointer ke simpul berikut dalam LIST. LIST juga memerlukan variabel START, yang berisi alamat dari simpul pertama dari LIST, dan jika INFO[K] berisi null, menunjukkan akhir dari list. Contoh berikut adalah list berkait yang menunjukkan bahwa simpul-simpul dari list tersebut tidak harus berada pada lokasi memori yang berdekatan, tetapi tetap dapat dikelola layaknya array linier.
Kadwi Suharsono
52
Buku Ajar Struktur Data Contoh 3.2. Gambar 3.4 menggambarkan list berkait dalam memori, masing-masing simpul berisi karakter tunggal. Urutan list tersebut dapat ditelusuri sebagai berikut: START = 9, dan INFO[9] = N, merupakan karakter pertama LINK[9] = 3, dan INFO[3] = O, merupakan karakter kedua LINK[3] = 6, dan INFO[6] = □ (blank), merupakan karakter ketiga LINK[6] = 11, dan INFO[11] = E, merupakan karakter keempat LINK[11] = 7, dan INFO[7] = X, merupakan karakter kelima LINK[7] = 10, dan INFO[10]= I,merupakan karakter keenam LINK[10] = 4, dan INFO[4] = T,merupakan karakter ketujuh LINK[4] = 0, pointer null, merupakan simpul terakhir dari list. Jadi string karakternya adalah : NO EXIT
START 9
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
INFO
LINK
O T
6 0
X
11 10
N I E
3 4 7
Gambar 3.4. List Berkait di memori Contoh 3.3. Gambar 3.5 menggambarkan 2 nilai matakuliah Algoritma, ALG, dan Geometri, GEOM disimpan di memori dalam 1 array linier TEST dan LINK. Nama matakuliah juga dijadikan variabel pointer. Pada gambar tersebut, ALG berisi 11, merupakan simpul pertama dari list ALG, dan GEOM berisi 5, merupakan simpul pertama dalam list GEOM. Dengan mengikuti pointernya dapat diketahui isi nilai dari matakuliah ALG adalah: 88,74, 93, 82 dan isi nilai dari matakuliah GEOM adalah: 84,62, 74, 100, 74, 78
Kadwi Suharsono
53
Buku Ajar Struktur Data
ALG 11
GEOM
5
TEST 1. 2. 74 3. 4. 82 5. 84 6. 78 7. 74 8. 100 9. 10. 11. 88 12. 62 13. 74 14. 93 15. 16.
LINK 14
Simpul 2 dari ALG
0 12 0 8 13
Simpul 4 dari ALG Simpul 1 dari GEOM
2 7 6 4
Simpul 1 dari ALG Simpul 2 dari GEOM
Simpul 3 dari GEOM
Simpul 3 dari ALG
Gambar 3.5. Dua List Berkait Contoh 3.4. Sebuah perusahaan mempunyai 4 broker, dan masing-masing broker mempunyai daftar pelanggannya. Data tersebut diorganisasikan seperti yang terlihat pada gambar 3.6. Dalam hal ini daftar nama pelanggan dari keempat broker disimpan dalam array Pelanggan yang sama, dan array LINK berisi pointer dari simpul berikutnya dalam list. Terdapat juga array Broker, yang berisi list broker dan array pointer POINT, POINT[K] menunjuk awal dari list Pelanggan dari Broker[K]. Oleh karena itu, daftar Pelanggan Bimo adalah Gatotkoco, Srikandi, Vibisana, Kunti. Daftar pelanggan Kresno adalah Hanoman, Madri, Emban dan daftar nama Pelanggan Narodo adalah Togog, Janoko, Arimbi, Rahwana, Widura sedangkan Hanggodo tidak mempunyai daftar Pelanggan, karena isi POINT-nya adalah pointer null atau 0.
Kadwi Suharsono
54
Buku Ajar Struktur Data
1. 2. 3. 4.
Broker Bimo Kresno Hanggodo Narodo
Point 12 3 0 9
Pelanggan 1. Vibisana 2. 3. Hanoman 4. Kunti 5. 6. Emban 7. 8. Rahwana 9. Togog 10. Janoko 11. 12. Gatotkoco 13. 14. Madri 15. Widura 16. 17. Srikandi 18. 19. Arimbi 20.
LINK 4 14 0 0 15 10 19 17 6 0 1 8
Gambar 3.6. List Berkait dengan Pointer Bagian informasi dari suatu simpul mungkin berupa record. Dalam hal ini, maka data harus disimpan dalam record, seperti contoh berikut: Contoh 3.5. Data karyawan dari sebuah perusahaan terdiri dari 9 orang yang berisi data: Nama, NIP, Jenis Kelamin, Gaji bulanan Secara umum, diperlukan 4 array linier, yaitu: Nama, NIP, Kelamin, Gaji untuk dapat menyimpan data pegawai tersebut. Gambar 3.7 menunjukkan bagaimana data tersebut disimpan di memori dalam struktur list berkait dengan diurutkan berdasarkan nama secara alfabetis, dengan menggunakan array tambahan LINK. LINK digunakan untuk menghubungkan antar simpul dalam list. Variabel START digunakan untuk menunjuk ke record pertama dari list.
Kadwi Suharsono
55
Buku Ajar Struktur Data
START 6
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Nama
NIP
Kelamin
Gaji
LINK
Durno Kresno Gatotkoco
192-38-7282 165-64-3351 175-56-2251
Pria Pria Pria
22800 19000 27200
12 7 14
Bismo Limbuk
178-52-1065 181-58-9939
Pria Wanita
14700 16400
9 10
Cakil Rahwono
177-44-4557 135-46-6262
Pria Pria
19000 15500
2 0
Emban
168-56-8113
Wanita
34200
4
Hanoman
208-56-1654
Pria
22800
3
Gambar 3.7. List Berkait dengan Record
Traversing Sebuah List Berkait. List berkait LIST disimpan di memori dalam array linier INFO dan LINK dengan variabel START, yang menunjuk simpul pertama dalam list, dan NULL mengindikasikan akhir dari list. Akan dilakukan operasi Traversing pada list agar setiap simpul dapat diproses. Algoritma traversing berikut menggunakan variabel PTR yang menunjuk simpul yang sedang diproses. Oleh karena itu, LINK[PTR] menunjuk pada simpul yang sedang diproses. Jadi, perintah PTR := LINK[PTR] adalah memindahkan pointer ke simpul berikutnya dalam list, seperti yang tergambar dalam gambar 3.8. PTR
Gambar 3.8. Proses memindahkan Pointer Algoritma detilnya adalah sebagai berikut. Inisialisasi nilai PTR dengan nilai START. Kemudian proses INFO[PTR], yaitu informasi dari simpul yang pertama dalam list. Mutakhirkan nilai PTR dengan perintah PTR := LINK[PTR] agar PTR pindah ke simpul kedua. Kemudian proses INFO [PTR] yang merupakan informasi dari simpul kedua dalam list. Mutakhirkan lagi nilai PTR dengan perintah PTR := LINK[PTR], dan proses INFO[PTR], yang merupakan informasi dari simpul ketiga. Dan seterusnya. Lanjutkan sampai PTR = NULL, yang merupakan tanda akhir list. Algortima lengkapnya adalah sebagai berikut. Kadwi Suharsono
56
Buku Ajar Struktur Data
Algoritma 3.1. (Traversing List Berkait) LIST adalah list berkait yang disimpan di memori. Algoritma ini adalah operasi traversing pada LIST, melakukan operasi PROSES untuk setiap elemen dalam LIST. Variabel PTR menunjuk simpul yang sedang diproses. 1. PTR := START [Inisialisasi pointer PTR]. 2. Ulangi langkah 3 dan 4 selama PTR ≠ NULL. 3. Lakukan PROSES pada INFO[PTR]. 4. PTR := LINK[PTR] [PTR berpindah ke simpul berikut.] [Akhir dari perulangan.] 5. Selesai. Perhatikan persamaan antara algoritma 3.1 dengan 2.1, yang melakukan operasi traversing pada array linier. Persamaannya adalah karena keduanya merupakan struktur data linier, di mana berisi elemen yang mempunyai urutan. Contoh 3.6 Procedure berikut mencetak informasi setiap simpul dari list berkait. Karena melakukan operasi traversing, maka mirip dengan algoritma 3.1. PRINT(INFO, LINK, START) Procedure berikut mencetak informasi setiap simpul dalam list 1. PTR := START. 2. Ulangi langkah 3 dan 4 selama PTR NULL. 3. Cetak: INFO[PTR]. 4. PTR := LINK[PTR] [Mutakhirkan pointer.] [Akhir dari Perulangan.] 5. Selesai. Contoh 3.7. Procedure berikut menghitung nilai NUM, yang merupakan jumlah elemen dalam list. COUNT(INFO, LINK, START, NUM) 1. NUM := 0. [Inisialisasi pencacah.] 2. PTR := START. [Inisialisasi Pointer.] 3. Ulangi langkah 4 dan 5 selama PTR ≠ NULL. 4. NUM := NUM + 1. 5. PTR := LINK[PTR] [Mutakhirkan pointer.] [Akhir dari Perulangan.] 6. Selesai. Procedure untuk menghitung jumlah elemen dalam list tersebut juga mirip dengan algoritma 3.1. Perbedaannya adalah ada diperlukan proses inisialisasi untuk variabel NUM sebelum melakukan operasi traversing.
Kadwi Suharsono
57
Buku Ajar Struktur Data Searching Sebuah List Berkait Sebuah list berkait LIST disimpan di memori seperti yang telah dibahas di bagian sebelumnya, yaitu Representasi list di memori dan traversing sebuah list berkait. Suatu ITEM tertentu akan dicari dalam list. Terdapat 2 algoritma untuk menemukan lokasi simpul, LOC dalam list, yang pertama kali ditemukan. Algoritma pertama mengasumsikan data dalam list tidak terurut, sedangkan yang algortima kedua data dalam list sudah terurut. Jika ITEM adalah nilai kunci, dan dicari dalam file untuk mendapatkan record yang berisi ITEM, maka ITEM akan muncul hanya 1 kali. List yang Tidak Terurut. Data yang tersimpan dalam LIST adalah tidak terurut. Akan dicari ITEM dalam LIST dengan menggunakan operasi traversing dengan menggunakan variabel pointer PTR dan membandingkan ITEM dengan isi dari INFO [PTR] atau setiap simpul, satu per satu. Sebelum memutakhirkan isi variabel pointer PTR dengan PTR := LINK[PTR] diperlukan 2 pengujian. Pertama adalah menguji apakah sudah di akhir list, dengan kondisi PTR = NULL, kemudian diuji juga apakah INFO[PTR] = ITEM Kedua pengujian tersebut tidak dapat dilakukan secara bersamaan, karena INFO[PTR] tidak dapat didefinisikan jika PTR = NULL. Oleh karena itu digunakan pengujian pertama untuk mengendalikan pelaksanaan perulangan, dan pengujian kedua diletakkan di dalam perulangan. Algoritma lengkapnya sebagai berikut: Algoritma 3.2. SEARCH(INFO, LINK, START, ITEM, LOC) LIST adalah list berkait yang disimpan di memori. Algoritma ini adalah mencari lokasi LOC suatu simpul, di mana ITEM muncul pertama kali dalam LIST, atau LOC = NULL 1. PTR := START. 2. Ulangi langkah 3 selama PTR ≠ NULL: 3. Jika ITEM = INFO[PTR], maka: LOC := PTR, dan Selesai. Lainnya: PTR:=LINK[PTR]. [PTR berpindah ke simpul berikut] [Akhir dari struktur Jika] [Akhir dari perulangan] 4. LOC := NULL. [Search tidak berhasil] 5. Selesai. Kompleksitas algoritma search list sama dengan algoritma search pada array linier. Waktu pelaksanaan untuk kondisi terjelek adalah sama deKadwi Suharsono
58
Buku Ajar Struktur Data ngan jumlah elemen dalam listnya, dan rata-rata waktu search-nya adalah n/2. Contoh 3.8. Perhatikan file personal seperti yang terlihat dalam gambar 3.7. modul berikut membaca NIP: NNN dari seorang karyawan, dan mengubah Gajinya dengan penambahan 5%. 1. Baca: NNN. 2. Panggil SEARCH(NIP, LINK, START, NNN, LOC). 3. Jika LOC ≠ NULL, maka: Gaji[LOC] := Gaji[LOC] + Gaji[LOC] * 0.05. Lainnya: Cetak: NNN tidak terdapat dalam file. [Akhir dari struktur Jika.] 4. Selesai. List Sudah Terurut Data yang tersimpan dalam LIST sudah terurut. Akan dicari ITEM dalam LIST dengan traversing list menggunakan variabel pointer PTR dan membandingkan ITEM dengan isi INFO[PTR] pada setiap simpul dalam LIST. Kompleksitas dari algoritma ini tetap sama dengan algoritma pencarian linier; kondisi terjelek adalah setara dengan jumlah elemen dalam LIST dan rata-rata pencariannya kira-kira n/2. Perlu diingat bahwa pencarian linier dapat menggunakan pencarian biner yang memerlukan log2 n. Algoritma pencarian biner tidak dapat diaplikasikan pada list berkait yang terurut, karena tidak tersedia indeks untuk elemen tengah dari list. Algoritma 3.3. SEARCHSL(INFO, LINK, START, ITEM, LOC) LIST adalah list terurut yang disimpan di memori. Algoritma ini adalah mencari lokasi LOC suatu simpul, di mana ITEM muncul pertama kali dalam LIST, atau LOC = NULL 1. PTR := START. 2. Ulangi langkah 3 selama PTR ≠ NULL: 3. Jika ITEM < INFO[PTR], maka: PTR := LINK[PTR]. [PTR sekarang menunjuk ke simpul berikutnya] Lainnya Jika ITEM = INFO[PTR], maka: LOC := PTR, dan Selesai. [Pencarian berhasil] Lainnya: LOC := NULL, dan Selesai. [ITEM sudah melebihi INFO[PTR].] [Akhir dari struktur Jika] [Akhir dari perulangan] 4. LOC := NULL. [Search tidak berhasil] 5. Selesai.
Kadwi Suharsono
59
Buku Ajar Struktur Data Contoh 3.9. Perhatikan lagi file personal pada gambar 3.7. Modul berikut membaca nama PEG dari pegawai dan memberikan tambahan 5% untuk gajinya. (Bandingkan dengan contoh 3.8) 1. Baca: PEG. 2. Panggil SEARCHSL(NAMA, LINK, START, PEG, LOC). 3. Jika LOC ≠ NULL, maka: Gaji[LOC] := Gaji[LOC] + Gaji[LOC] * 0.05. Lainnya: Cetak: PEG tidak terdapat dalam list. [Akhir dari struktur Jika.] 4. Selesai .
Alokasi Memori dan Koleksi Memori Sisa Pengelolaan list berkait di memori akan terjadi penyisipan simpul baru ke dalam list, sehingga diperlukan beberapa mekanisme untuk menyediakan memori yang sedang tidak terpakai, dapat digunakan untuk simpul baru. Beberapa mekanisme diperlukan agar lokasi memori yang sudah dihapus menjadi memori yang tersedia untuk penggunaan berikutnya. Bersamaan dengan adanya list berkait di memori, suatu list khusus dibuat, yang berisi lokasi memori yang sudah tidak terpakai. List ini mempunyai pointer sendiri, yang disebut dengan list dari ruang yang kosong. List berkait yang digunakan, akan berhubungan dengan list dari memori yang kosong, sehingga setiap kali terjadi penyisipan simpul baru ke dalam list atau penghapusan suatu simpul dari list akan melibatkan list dari memori yang kosong ini. Memori yang kosong ini membentuki list berkait dengan menggunakan variabel pointer AVAIL. Contoh 3.10 Data List pasien yang terdapat dalam contoh 3.1 disimpan dalam array linier NOBED dan NEXT. Memori yang kosong dalam array linier NOBED dikaitkan seperti yang tertera dalam gambar 3.9. Perhatikan bahwa NOBED[10] adalah no bed yang pertama kali tersedia, NOBED[2] adalah no bed yang kedua tersedia, dan NOBED[6] adalah no bed terakhir yang tersedia, karena NOBED[6] berisi pointer null pada field NEXT-nya, NEXT[6] = 0.
Kadwi Suharsono
60
Buku Ajar Struktur Data START
AVAIL
5
10
Nobed
Pasien
Next
1 2 3 4 5 6 7 8 9 10 11 12
Kresno
7 6
Durno Mbilung Arjuno
11 12 3 0 4 1 0 2 8 9
Limbuk Gareng Semar Fetruk Narodo
Gambar 3.9. List dari Memori Sisa Contoh 3.11 (a) Memori yang tersedia pada array linier TEST pada gambar 3.5 dapat dikaitkan seperti tertera pada gambar 3.10. masing-masing list, yaitu ALG dan GEOM menggunakan list AVAIL. Karena AVAIL = 9, maka TEST[9] adalah simpul bebas pertama dalam list AVAIL. Karena LINK[AVAIL] = LINK[9] = 10, maka TEST[10] adalah simpul bebas kedua dalam list AVAIL. Dan seterusnya. (b) Perhatikan file karyawan pada gambar 3.7. Memori yang tersedia pada array linier NAMA dapat dikaitkan seperti yang tertera pada gambar 3.11. perhatikan bahwa list memori bebasnya adalah NAMA[8], NAMA[11], NAMA[13], NAMA[5] dan NAMA[1]. TEST
ALG
11
GEOM
5
AVAIL
9
1. 2. 74 3. 4. 82 5. 84 6. 78 7. 74 8. 100 9. 10. 11. 88 12. 62 13. 74 14. 93 15. 16.
LINK 16 14 1 0 12 0 8 13 10 3 2 7 6 4 0 15
Gambar 3.10. List Memori Sisa.
Kadwi Suharsono
61
Buku Ajar Struktur Data (c) Memori yang tersedia dalam array linier PELANGGAN pada gambar 3.6 dapat dikaitkan seperti yang tertera pada gambar 3.12. Perlu ditegaskan di sini bahwa 4 list yang ada menggunakan list AVAIL untuk penambahan PELANGGAN baru. START
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
6
AVAIL 8
Nama
NIP
Kelamin
Gaji
Durno Kresno Gatotkoco
192-38-7282 165-64-3351 175-56-2251
Pria Pria Pria
22800 19000 27200
Bismo Limbuk
178-52-1065 181-58-9939
Pria Wanita
14700 16400
Cakil Rahwono
177-44-4557 135-46-6262
Pria Pria
19000 15500
Emban
168-56-8113
Wanita
34200
Hanoman
208-56-1654
Pria
22800
LINK 0 12 7 14 1 9 10 11 2 0 13 4 5 3
Gambar 3.11. List Memori Sisa
1. 2. 3. 4.
Broker Bimo Kresno Hanggodo Narodo
Avail 11
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.
Pelanggan Vibisana
LINK 4 16
Hanoman Kunti
14 0 20 0 13 15 10 19 18 17 0 6 0 5 1 5 8 7
Emban Rahwana Togog Janoko Gatotkoco Madri Widura Srikandi Arimbi
Gambar 3.12. List Memori Sisa dari List Pointer Contoh 3.12. Kadwi Suharsono
62
Buku Ajar Struktur Data Misalnya LIST(INFO, LINK, START,AVAIL) mempunyai lokasi memori sebanyak 10, n = 10 simpul. Jika LIST diinisialisasi, artinya LIST kosong, maka isi dari list AVAIL adalah seperti yang terlihat pada gambar 3.12. Perhatikan bahwa START = 0, karena LIST-nya kosong. INFO START
0
AVAIL
1
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
LINK 2 3 4 5 6 7 8 9 10 0
Gambar 3.13. List Memori Sisa pada Inisialisasi List
Operasi Penyisipan ke dalam suatu List Berkait LIST merupakan list berkait yang mempunyai simpul berurutan A dan B, seperti yang tertera dalam gambar 3.14(a). misalkan akan disisipkan simpul N yang akan diletakkan di antara simpul A dengan simpul B. Diagram skematik proses penyisipan tersebut tertera pada gambar 3.14(b). Dalam hal ini simpul A menunjuk ke SImpul N, dan Simpul N menunjuk ke simpul B, yang sebelumnya ditunjuk oleh simpul A. Pada gambar 3.14 tersebut tidak terlihat munculnya simpul baru tersebut berasal dari list AVAIL. Untuk memudahkan operasi, simpul pertama dari list AVAIL akan digunakan untuk simpul baru, N. Diagram skematik yang lebih detil dari operasi penyisipan tersebut adalah seperti yang tertera pada gambar 3.15. terdapat 3 pointer yang berubah: (1) Field pointer dari simpul A sekarang menunjuk ke simpul baru N, yang sebelumnya ditunjuk oleh pointer AVAIL (2) AVAIL sekarang menunjuk simpul kedua dalam list AVAIL, yang sebelumnya ditunjuk oleh simpul N (3) Field pointer dari simpul N sekarang menunjuk ke simpul B, yang sebelumnya ditunjuk oleh simpul A.
Kadwi Suharsono
63
Buku Ajar Struktur Data START Simpul A
Simpul B x
(a) Sebelum penyisipan START Simpul A
Simpul B x
Simpul N (b) Setelah penyisipan
Gambar 3.14. Penyisipan sebuah Simpul pada List Terdapat 2 hal yang bersifat khusus. Jika simpul baru N adalah simpul pertama dalam LIST, maka START akan menunjuk ke N, dan jika simpul baru N adalah simpul terakhir dari LIST, maka N akan mempunyai pointer Null. List Data
START
Simpul A
Simpul B x
AVAIL Simpul N x List memori kosong
Gambar 3.15. Penggunaan AVAIL untuk penyisipan List.
Contoh 3.13 (a) Perhatikan gambar 3.9, List Pasien yang urut berdasarkan nama. Jika terdapat pasien baru, Hanoman, maka Hanoman akan diletakkan pada no bed 10, bed yang pertama tersedia Hanoman akan diletakkan dalam list di antara Gareng dan Kresno Terdapat perubahan 3 pointer, yaitu: 1. NEXT[8] := 10 [Sekarang Gareng menunjuk Hanoman] 2. NEXT[10] := 1. [Sekarang Hanoman menunjuk Kresno] 3. AVAIL := 2.
Kadwi Suharsono
64
Buku Ajar Struktur Data (b) Perhatikan gambar 3.12, list broker dan Pelanggan. Karena list PELANGGAN tidak diurutkan, dapat diasumsikan bahwa PELANGGAN baru akan ditambahkan di awal list. Jika terdapat penambahan PELANGGAN baru Gareng, dari broker Kresno, maka: Gareng diletakkan pada array linier PELANGGAN[11], simpul pertama yang tersedia Gareng disisipkan sebelum Hanoman, yang sebelumnya adalah pelanggan pertama dari broker Kresno Terdapat perubahan 3 pointer, yaitu: 1. POINT[2] = 11. [Sekarang list Kresno diawalidengan Gareng] 2. LINK[11] = 3. [Sekarang Gareng menunjuk Hanoman] 3. AVAIL = 18. [Sekarang AVAIL menunjuk ke simpul tersedia, kedua] (c) Elemen data A, B,C, D, E, dan F disisipkan ke dalam list kosong, seperti yang terlihat pada gambar 3.13. Jika diasumsikan bahwa simpul baru selalu diletakkan di awal list, maka setelah penyisipan, F akan menunjuk ke E, D menunjuk ke D, D menunjuk ke C, C menunjuk ke B dan B menunjuk ke A. A akan berisi pointer null. AVAIL akan berisi 7, yaitu simpul pertama yang tersedia setelah terjadi 6 penyisipan. START = 6, lokasi dari simpul pertama dalam list, F. Gambar 3.16 adalah list baru tersebut. INFO START 6
AVAIL
7
1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
A B C D E F
LINK 0 1 2 3 4 5 8 9 10 0
Gambar 3.16. Penyisipan Elemen ke dalam List Kosong Algoritma Penyisipan Algoritma penyisipan simpul ke dalam list berkait bisa terjadi dalam beberapa situasi. Hanya 3 saja yang akan dibahas. Pertama adalah penyisipan terjadi di awal list, kedua adalah penyisipan setelah simpul tertentu, ketiga adalah penyisipan simpul ke dalam list yang terurut. Semua algoritma diasumsikan bahwa list berkait di memori membentuk LIST(INFO, LINK, START, AVAIL) dan variabel ITEM berisi informasi yang akan disisipkan ke dalam list.
Kadwi Suharsono
65
Buku Ajar Struktur Data Karena algoritma penyisipan ini akan menggunakan simpul yang ada di AVAIL, semua algoritma akan meliputi langkah-langkah berikut: 1. Memeriksa apakah tersedia ruang di list AVAIL. Jika tidak, kondisinya adalah AVAIL = NULL, maka algoritma akan mencetak pesan: OVERFLOW 2. Menghapus simpul pertama dari list AVAIL. Menggunakan variabel BARU untuk mencatat alamat simpul baru, langkah ini dapat dilakukan dengan menggunakan pasangan perintah berikut: BARU := AVAIL, AVAIL := LINK[AVAIL] 3. Mengisikan informasi baru ke dalam simpul baru atau dengan INFO[BARU] := ITEM Diagram skematik dari perintah tersebut tertera pada gambar 3.17 BARU List memori kosong
ITEM
x
AVAIL
3.17. Diagram Skematik Penggunaan List AVAIL Penyisipan di awal List Jika list berkait yang digunakan adalah tidak terurut, dan tidak ada alasan untuk menyisipkan simpul baru di mana saja dalam list, maka cara paling mudah adalah menyisipkan simpul baru tersebut di awal list, seperti yang terlihat pada algoritma berikut ini: Algoritma 3.4: INSFIRST(INFO, LINK, START, AVAIL, ITEM) Algoritma ini menyisipkan ITEM sebagai simpul pertama dari list. 1. [OVERFLOW?] Jika AVAIL = NULL, maka: Cetak:OVERFLOW, dan Selesai. 2. [Hapus elemen pertama dari list AVAIL] BARU := AVAIL dan AVAIL := LINK[AVAIL]. 3. INFO[BARU] := ITEM. [Salin data baru ke dalam simpul baru.] 4. LINK[BARU] := START. [Simpul baru sekarang menunjuk ke list awal] 5. START := BARU. [Ubah START agar menunjuk ke simpul baru.] 6. Selesai. Langkah 1 sampai 3 telah dibahas sebelumnya, dan diagram skematik dari langkah 2 dan 3 tertera pada gambar 3.17, sedangkan diagram skematik langkah 4 dan 5 tertera pada gambar 3.18.
Kadwi Suharsono
66
