struktur data – fd – [page 1 of 7]
SENARAI BERANTAI Dalam pemakaian sehari-hari istilah senarai berantai (list) adalah kumpulan linier sejumlah data. Contohnya seperti daftar belanja harian, dimana setiap harinya daftar belanjaan tersebut dapat berubah-ubah. Ada yang dihapus jika barang telah dibeli atau ditambahkan barang baru yang akan dibeli. Telah kita ketahui bahwa penggunaan pointer sangat mendukung dalam pembentukan struktur data dinamis. Salah satu struktur data dinamis yang paling sederhana adalah senarai berantia (linked list), atau senari satu arah (one-way list). Dengan demikian senarai berantai adalah kumpulan komponen yang disusun secara berurutan dengan bantuan pointer. Masing-masing komponen dinamakan dengan simpul (node). Sehingga setiap simpul dalam senarai berantai teragi menjadi dua bagian. Bagian pertama disebut medan informasi, berisi informasi yang akan disimpan dan diolah. Bagian kedua disenut penghubung (link field), berisi alamat simpul berikutnya. Gambar dibawah ini menunjukkan diagram skematis dari senarai berantai dengan 6 simpul.
A
B
C
Awal
D
E
F
Medan penghubung simpul Medan informasi Gambar 1. Senarai berantai dengan 6 simpul
Setiap simpul digambarkan dalam 2 bagian. Bagian kiri adalah medan informasi dan bagian kanan adalah medan penghubung, sehingga dalam diagram digambarkan sebagai anak panah. Perlu diingat bahwa medan penghubung adalah sebuah pointer yang menunjukan ke simpul berikutnya, sehingga nilai dari medan ini adalah alamat sebuah lokasi tertentu dalam memori. Pada gambar diatas, pointer Awal, yang bukan merupakan bagian dari senarai, menunjukkan ke simpul pertama dari senarai tersebut. Medan penghubung (pointer) dari suatu simpul yang tidak menunjukkan simpul lain disebut dengan pointer kosong, yang nilainya dinyatakan sebagai nil (nil adalah reserved word Pascal yang berarti bahwa pointer tidak menunjukkan ke suatu simpul, dan nilainya sama dengan 0 atau bilangan negatif). Dengan memperhatikan gambar diatas, kita bisa melihat bahwa hanya dengan sebuah pointer Awal saja maka kita bisa membaca semua informasi yang tersimpan dalam senarai. Senarai berantai sangat berguna dalam terapan-terapan sehari-hari dimana komponen-komponen dalam jumlah sangat besar harus dijaga supaya selalu dalam keadaan terurutkan menurut kriteria tertentu, misalnya secara alphabetis, dan dimana komponen-komponennya sering dihapus atau ditambahkan.
Penyajian Senarai Berantai Sebelum kita mempelajari beberapa operasi dasar yang biasa dilakukan pada sebuah senarai berantai, ada baiknya jika kita lihat bagaimana sesungguhnya suatu senarai berantai disimpan dalam memori. Misalnya senarai berantai pada Gambar 1 diatas kita namakan Daftar. Senarai berantai Daftar dalam memori akan disajikan dengan cara sebagai berikut : Pertama-tama Daftar memerlukan dua larik linier (vektor), kita namakan vektor Info dan Sambungan sedemikian rupa sehingga vektor Info berisi komponen yang tersimpan dalam medan informasi dan vektor Sambungan berisi medan pointer (alamat) ke simpul berikutnya. Disamping itu, Daftar juga memerlukan suatu variabel, misalnya Awal, yang berisi alamat simpul pertama dari senarai berantai, dan pointer sentinel, yang bernama Kosong, yang menunjukkan akhir sebuah senarai berantai. Karena subskrib untuk vektor Info dan Sambungan selalu positif dan lebih besar dari 0, maka untuk pointer sentinel bisa kita tulis sebagai kosong = 0. Gambar dibawah ini menunjukkan bagaimana penyajian senarai berantai Daftar disajikan memori.
struktur data – fd – [page 2 of 7]
INFO
SAMBUNGAN
1
C
5
Awal
2
A
6
2
3 4
D
10
5
B
1
F
0
E
8
6 7
Akhir
8 9 10
Gambar 2. Contoh penyajian senarai berantai dalam memori
Dari Gambar 2 diatas dapat kita lihat bahwa : Awal Sambungan[ 2] Sambungan[ 6] Sambungan[ 1] Sambungan[ 5] Sambungan[10] Sambungan[ 8]
= = = = = = =
2, 6, 1, 5, 10, 8, 0,
maka Info[ 2] maka Info[ 6] maka Info[ 1] maka Info[ 5] maka Info[10] maka Info[ 8] akhir senarai berantai
= = = = = =
“A” “B” “C” “D” “E” “F”
sehingga kita dapat memperoleh rangkaian “ABCDEF”.
Operasi pada Senarai Berantai Unutk menjelaskan operasi pada senarai, kita gunakan deklarasi pointer dan simpul sebagai berikut : type
Simpul Data
= ^Data; = record Info : char; Berikut : Simpul; end;
var
Elemen Awal, Akhir, Baru, Hapus, Bantu
: char; : Simpul;
1. Menambah Simpul Operasi menambah simpul bisa dipecah menjadi 3 bagian berdasarkan posisi simpul baru yang akan disisipkan, yaitu : -. simpul baru yang selalu ditambahkan dibelakang simpul terakhir -. simpul baru yang diletakkan sebagai simpul pertama -. simpul baru yang diletakkan diantara 2 simpul yang lain. Menambah di belakang : Awal
Akhir
A
B
C
Baru
D
F
........(1)
struktur data – fd – [page 3 of 7]
Awal
Akhir
A
B
C
Baru
D
F
........(2)
F
........(3)
Baru Awal
Akhir
A
B
C
D
Gambar 3. Penambahan simpul di akhir senarai
Prosedur untuk menambah simpul di belakang : procedure Tambah_Belakang(var Awal, Akhir : Simpul; Elemen : char); var Baru : Simpul; begin new(Baru); Baru^.Info := Elemen; if Awal = nil then { jika senarai masih kosong } Awal := Baru else Akhir^.Berikut := Baru; { Gambar 3 – (2) } Akhir := Baru; { Ganbar 3 – (3) } Akhir^.Berikut := nil; end;
Menambah di depan : Baru
Awal
A
Baru
Akhir
B
C
D
Awal
A
F
........(1)
F
........(2)
F
........(3)
Akhir
B
C
D
Awal Baru
Akhir
A
B
C
D
Gambar 4. Penambahan simpul di awal senarai procedure Tambah_Depan(var Awal, Akhir : Simpul; Elemen : char); var Baru : Simpul; begin new(Baru); Baru^.Info := Elemen; if Awal = nil then { jika senarai masih kosong } Awal := Baru else Baru^.Berikut := Awal; { Gambar 4 – (2) } Awal := Baru; { Ganbar 4 – (3) } end;
struktur data – fd – [page 4 of 7]
Menambah di tengah : Awal
Bantu
A
Akhir
B
D
F
........(1)
F
........(2)
F
........(3)
Baru
C
Awal
Bantu
A
Akhir
B
D
Baru
C
Awal
Bantu
A
Akhir
B
D
Baru
C Gambar 5. Penambahan simpul di tengah senarai
procedure Tambah_Tengah(var Awal, Akhir : Simpul; Elemen : char); var Baru, Bantu : Simpul; begin new(Baru); Baru^.Info := Elemen; if Awal = nil then { jika senarai masih kosong } Awal := Baru; Akhir := Baru else { mencari lokasi yang sesuai } begin Bantu := Awal; while Elemen > Baru^.Berikut^.Info do Bantu := Bantu^.Berikut; { menyisipkan simpul baru } Baru^.Berikut := Bantu^.Berikut; Bantu^.Berikut := Baru; end; end;
{ Ganbar 5 – (2) } { Ganbar 5 – (3) }
struktur data – fd – [page 5 of 7]
2. Menghapus Simpul Menghapus simpul pertama : Awal Hapus
Akhir
A
Hapus
B
C
D
Awal
A
F
........(1)
F
........(2)
F
........(3)
F
........(1)
Akhir
B
C
D
Awal
Akhir
B
C
D
Gambar 6. Penghapusan simpul di awal senarai
Menghapus simpul di tengah : Awal
Bantu
A
Awal
Hapus
B
Bantu
A
Awal
Akhir
C
Akhir
Hapus
B
C
D
F
........(2)
Akhir
Bantu
A
D
B
D
........(2)
F
Gambar 7. Penghapusan simpul di tengah senarai
Menghapus simpul terakhir : Awal
Bantu
A
B
C
Awal
Akhir
D
Bantu
A
B
C
Hapus
F
Akhir
D
F
........(1)
Hapus
........(2)
struktur data – fd – [page 6 of 7]
Awal
Bantu
A
B
Akhir
C
........(3)
D
Gambar 8. Penghapusan simpul di akhir senarai procedure Hapus(var Awal, Akhir : Simpul; Elemen : char); var Hapus, Bantu : Simpul; begin if Awal = nil then { jika senarai masih kosong } writeln(‘Senarai masih kosong’) else if Awal^.Info = Elemen then { simpul pertama yang dihapus } begin Hapus := Awal; { Ganbar 6 – (1) } Awal := Hapus^.Berikut; { Ganbar 6 – (2) } Hapus^.Berikut := 0; dispose(Hapus); end else { menghapus simpul di tengah atau terakhir } begin Bantu := Awal; { mencari simpul yang akan dihapus } while (Elemen <> Bantu^.Info) and (Bantu^.Berikut <> nil) do Bantu := Bantu^.Berikut; Hapus := Bantu^.Berikut; if Hapus <> nil then { simpul yang akan dihapus ketemu } begin if Hapus <> Akhir then { simpul di tengah dihapus } { Ganbar 7 – (2) } Bantu^.Berikut := Hapus^.Berikut; else { simpul terakhir dihapus } begin { Ganbar 8 – (2) } Akhir := Bantu; { Ganbar 8 – (3) } Akhir^.Berikut := nil; end; Hapus^.Berikut := 0; dispose(Hapus); end else { simpul yang akah dihapus tidak ketemu } wtiteln(‘Simpul yang akan dihapus tidak ketemu !’); end; end;
3. Membaca isi Senarai Untuk pembacaan isi senarai maka dapat dilakukan mulai dari simpul Awal menuju ke simpul Akhir. Awal
Akhir
A
B
C
D
procedure Baca(var Awal, Akhir : Simpul; Elemen : char); var Bantu : Simpul; begin Bantu := Awal; repeat
struktur data – fd – [page 7 of 7]
write(Bantu^.Info); Bantu := Bantu^.Berikut; until Bantu = nil; writeln; end;
4. Mencari Data Secara garis besar, proses untuk mencari data dalam senarai hampir sama dengan proses untuk membaca senarai, hanya perlu menambahkan pengujian apakah data yang dicari ada atau tidak. Pencarian akan dilakukan mulai dari simpul Awal sampai Akhir. function Ada_Data(Awal : Simpul; Elemen : char):boolean; var Ketemu : boolean; begin Ketemu := false; repeat if Awal^.Info = Elemen then Ketemu := true; else Awal := Awal^.Berikut; until Ketemu or (Awal = nil); Ada_Data := Ketemu; end;
