BAB VII SENARAI BERANTAI (List)

BAB VII SENARAI BERANTAI (List) Dalam kehidupan sehari-hari, senarai (List ) adalah kumpulan linear sejumlah data. Gambar dibawah ini menunjukkan senarai yang berisi daftar belanjaan, yang berupa barang pertama, kedua, ketiga dan seterusnya (gambar a). Untuk hari berikutnya, maka gambar tersebut bisa berubah sesuai dengan barang yang harus dibeli atau yang tidak perlu dibeli lagi. (Gambar b). Pepsodent Kain Pel Rinso Sabun

Pepsodent Kain Pel Rinso Sabun Sikat Gigi Garam Ember

(a)

(b)

Gambar. Daftar barang belanjaan (List) Pengolahan data yang kita lakukan menggunakan komputer seringkali mirip dengan ilustrasi di atas, yang antara lain berupa penyimpanan data dan pengolahan lain dari sekelompok data yang telah terorganisir dalam sebuah urutan tertentu. Dalam pemakaian sehari-hari istilah senarai (list) adalah kumpulan linier sejumlah data yang saling berkait. Kaitan itu dilakukan oleh pengait (pointers). Setiap Node/Simpul Universitas Bina Darma

Praktikum Struktur Data 45

terdiri dari dua bagian, yaitu : nilai data (info) dan pengait (link/link field/next ponter) yang berisi alamat elemen berikutnya dalam daftar. Node terakhir berisi pengait dengan nilai spesial yang disebut dengan null pointer. 7.1 Deklarasi Simpul dengan Pointer Type Simpul Data

= ^Data; = Record Info : char; Berikut : Simpul;

End; Var Elemen Awal, Akhir, Baru

: char; : Simpul;

7.2 Menambah Simpul Operasi penambahan simpul dibedakan berdasarkan posisi simpul baru yang akan disisipkan, yaitu : 7.2.1

Penambahan simpul di Belakang

Secara garis besar, operasi penambahan di akhir list dijelaskan sebagai berikut : •

Pointer Awal adalah pointer yang menunjuk ke simpul pertama, pointer Akhir menunjuk ke simpul terakhir dan simpul yang ditunjuk oleh pointer Baru adalah simpul yang akan ditambahkan.

Universitas Bina Darma


•

Untuk menyambung simpul yang ditunjuk oleh Akhir dan Baru, pointer pada simpul yang ditunjuk oleh simpul Akhir dibuat sama dengan Baru, kemudian pointer Akhir dibuat sama dengan pointer Baru.

(* prosedure menambah simpul simpul baru diletakkan di akhir list Cara memanggil : Tambah_Belakang(Awal, Akhir, Elemen) *) Procedure Tambah_Belakang(Var Awal, Akhir : Simpul; Elemen : char); Var Baru : Simpul; Begin New(Baru);Baru^.Info :=Elemen; If Awal = Nil Then (* list masih kosong *) Awal:=Baru Else Akhir^.Berikut := Baru; Akhir :=Baru; Akhir^.Berikut :=Nil; End;



7.2.2

Penambahan simpul di Depan

Secara garis besar, operasi penambahan di awal list dijelaskan sebagai berikut : 1. Pertama kali pointer pada simpul yang ditunjuk oleh pointer baru dibuat sama dengan Awal. 2. Kemudian Awal dibuat sama dengan Baru. Dengan cara sperti ini sinpul baru akan selalu diperlakukan sebagai simpul pertama dari dalam linked list (*

Prosedur untuk menambah simpul Simpul Baru diletakkan di awal list berantai Cara memanggil : Tambah_Depan(Awal, Akhir, Elemen)

*) Procdure Tambah_Depan(Var Awal, Akhir : Simpul; Elemen : Char); Var Baru : Simpul; Begin New(Baru);Baru^.Info := Elemen; If Awal = Nil Then (* List masih kosong *) Akhir := Baru Else Baru^.Berikut := Awal; Awal := Baru; End;

7.2.3

Penambahan simpul di antara dua simpul yang sudah ada (Menambah di Tengah)

Secara garis besar, operasi penambahan di awal list dijelaskan sebagai berikut : 1. Pertama kali ditentukan dimana simpul baru akan ditambahkan, yaitu dengan menempatkan pointer Bantu pada suatu tempat.



2. Kemudian pointer pada simpul yang ditunjuk oleh Baru dibuat sama dengan pointer pada simpul yang ditunjuk oleh Bantu. 3. Selanjutnya pointer pada simpul yang ditunjuk oleh simpul simpul Bantu dibuat sama dengan Baru. Prosedurnya sebagai berikut : (*

Prosedur untuk menambah simpul Simpul Baru diletakkan di tengah list berantai Cara memanggil : Tambah_Tengah(Awal, Akhir, Elemen)

*) Procedure Tambah_Tengah(Var Awal, Akhir : Simpul; Elemen : Char); Var Baru, Bantu : Simpul; Begin New(Baru);Baru^.Info := Elemen; If Awal = Nil Then (* List masih kosong *) Begin Awal := Baru; Akhir := Baru; End Else Begin (* mencari lokasi yang sesuai *) Bantu := Awal; While Elemen > Baru^.Berikut^.Info Do Bantu := Bantu^.Berikut; (*Menyisipkan simpul baru *) Baru^.Berikut := Bantu^.Berikut; Bantu^.Berikut : Baru; End; End;



7.3 Menghapus Simpul Dalam menghapus simpul ada satu hal yang perlu diperhatikan, yaitu bahwa simpul yang bisa dihapus adalah simpul yang berada sesudah simpul yang ditunjuk oleh suatu pointer, kecuali untuk simpul pertama. 7.3.1

Menghapus Simpul Pertama

Untuk menghapus simpul pertama, maka : •

Pointer Bantu kita buat sama dengan pointer Awal.

•

Kemuadian pointer Awal kita pindah ke simpul yang ditunjuk oleh pointer pada simpul yang ditunjuk oleh pointer Bantu.

• 7.3.2

Selanjutnya simpul yang ditunjuk oleh pointer Bantu kita Dispose.

Menghapus Simpul di Tengah atau Terakhir

Untuk menghapus simpul yang ada di tengah list, maka : •

Pertama kali kita letakkan pointer Bantu pada simpul disebelah kiri simpul yang akan dihapus.

•

Simpul yang akan dihapus kita tunjuk dengan pointer lain, misalnya Hapus.

•

Kemudian pointer pada simpul yang ditunjuk oleh Bantu kita tunjukkan pada simpul yang ditunjuk oleh pointer pada simpul yang akan dihapus.

•

Selanjutnya simpul yang ditunjuk oleh Pointer Hapus kita Dispose.



Prosedur selengkapnya sebagai berikut : (*

Prosedur untuk menghapus simpul Cara memanggil : Hapus_Simpul(Awal, Akhir, Elemen)

*) Procedure Hapus_Simpul(Var Awal, Akhir : Simpul; Elemen : Char) Var Bantu, Hapus : Simpul; Begin

If Awal = nil Then (* list masih kosong *) Writeln(‘List masih kosong…’) Else If Awal^.Info = Elemen Then Begin (* simpul pertama yang dihapus *) Hapus := Awal; Awal := Hapus^.Berikut; Dispose(Hapus); End Else Begin (* hapus simpul tengah atau terakhir *) Bantu := Awal; (* mencari simpul yg akan dihapus *) While (Elemen<>Bantu^.Info) AND (Bantu^.Berikut <> nil) Do

Bantu := Bantu^.Berikut; Hapus := Bantu^.Berikut; If Hapus <> nil Then Begin (* Simpul yang akan dihapus ketemu *) If Hapus <> Akhir Then (* Simpul tengah dihapus *) Bantu^.Berikut := Hapus^.Berikut Else Begin (* simpul terakhir dihapus *) Akhir := bantu; Akhir^.Berikut := nil; End; Dispose(Hapus); Universitas Bina Darma


End Else

End;

End;

(* simpul yang akan dihapus tidak ketemu *) Writeln(‘simpul yang akan dihapus tidak ketemu…’)

7.4 Membaca Isi Linked List 7.4.1 Membaca Maju Pembacaan Linked List secara maju bisa dijelaskan sebagai berikut : •

Pertama kali kita atur supaya pointer Bantu menunjuk ke simpul yang ditunjuk oleh pointer Awal.

•

Setelah isi simpul tersebut dibaca, maka pointer Bantu kita gerakkan ke kanan untuk membaca simpul berikutnya. Proses ini kita ulang sampai pointer Bantu sama dengan pointer Akhir.

Procedure untuk membaca Linked List tersebut sebagai berikut : (*

Procedure untuk membaca Linked List Membaca dari Kiri ke Kanan Cara memanggil : Baca_Maju(Awal, Akhir)

*) Procedure Baca_Maju(Awal, Akhir : Simpul); Var Bantu : Simpul; Begin Bantu := Awal; Repeat Write(Bantu^.Info:2); Bantu := Bantu^.Berikut ; Until Bantu = nil; Writeln; End; Universitas Bina Darma


7.4.2 Membaca Mundur Pembacaan Linked List secara mundur bisa dijelaskan sebagai berikut : •

Pertama kali kita atur pointer Bantu sama dengan pointer Awal.

•

Berikutnya, pointer Awal kita kita arahkan ke simpul terakhir, dan kita pakai pointer lain

Procedure untuk membaca Linked List tersebut sebagai berikut : (*

Procedure untuk membaca Linked List Membaca dari Kanan ke Kiri (Mundur secara Rekursif) Cara memanggil : Mundur(Awal)

*) Procedure Mundur(Bantu : Simpul); Begin If Bantu <> Nil Then Begin Mundur(Bantu^.Berikut); Write(Bantu^.Info); End; End;

Tugas 12 : Buat Program aplikasi Linked List dari procedure-procedure yang telah tersedia di atas!



BAB VII SENARAI BERANTAI (List)

Recommend Documents