BAB Vii

list

Pendahuluan

LIST adlah kumpulan objek data yg tipenya sama, tersusun dlm bentuk barisan linier berurutan, dan elemen2xnya dapat dihapus atau ditambahkan secara dinamis.

Merupakan bentuk struktur data yang terdiri dari serangkaian simpul/node yang berisi data dan saling terkait.

Memanfaatkan kombinasi dari tipe data pointer dan tipe data

record/structure (pointer to records).

Kesimpulan: 1. elemen2x list hrs tersusun secara berurutan {seperti

elemen array} 2. List dapat tidak mempunyai elemen (kosong) dan

kedalamnya dpt ditambah elemen baru 3. Jika list tidak kosong, maka elemen2x list dpt jg diambil

dari list (hapus)

Prinsip linked list dapat kita bandingkan seperti suatu rantai yang matanya dihubungkan satu sama lain. Mata rantai tersebut dapat kita asosiasikan dengan record atau node. 1. Ciri khas suatu node dalam linked list adalah harus selalu

terdapat field, paling sedikit dua bagian, yaitu : Data Pointer.

2. Secara umum linked list dibedakan atas 2 macam, yaitu : 1. Single Linked List 2. Double Linked List

Bentuk-bentuk linked list

Single-linked list

• Satu simpul/node memiliki sebuah variabel pointer yang digunakan untuk menunjuk pada simpul/node berikutnya.

Double-linked list • Satu simpul/node menyimpan dua variabel bertipe

pointer.

– Satu pointer menunjuk ke simpul/node berikutnya.

– Pointer yang lain menunjuk ke simpul/node sebelumnya.

• Varian : Multiple-Linked List

– Jumlah variabel pointer yang dimiliki masing-masing simpul lebih dari dua.

Circular linked list Pointer pada simpul/node terakhir menunjuk pada

simpul/node pertama.

Varian :

Circular single linked list.

Circular double linked list.

Pointer awal merupakan penunjuk simpul pertama dan bukan bagian dari list. Medan penyambung yg tidak menunjuk simpul lain disebut pointer kosong dengan kata baku nil (nilainya sama dg 0 atau bilangan negatif). Dari gambar terlihat bahwa dengan sebuah pointer awal saja maka bisa membaca semua data/informasi yg tersimpan dalam senarai (list).

A B C E D

KONSEP LIST

F

awal

Gambar list DAFTAR dg 6 simpul

Operasi-operasi terhadap linked list Menambah Simpul/Node Baru

Menambah di depan.

Menambah di tengah.

Menambah di belakang.

Menghapus Simpul/Node Menghapus di depan.

Menghapus di tengah.

Menghapus di belakang.

Membaca isi simpul/node. Membaca maju

Membaca mundur

Menambah (simpul) di depan

awal

50 next 80 Ø

40 Ø

baru

next

akhir

Menambah (simpul) di tengah

60 49

awal

bantu

50 next 80 Ø

70 Ø

baru

next

next

akhir

Menambah (simpul) di belakang

60 49

awal

bantu

50 next 70 Ø

80 Ø

baru

next

akhir

next

Menghapus (simpul) di depan

60 next

awal

50 20 80 Ø

20

hapus

next

50

60 next

awal

50 20 80 Ø

20

hapus

next

60 20

hapus

80

Menghapus (simpul) di tengah dan akhir

Linked Lists vs Arrays Arrays Linked Lists

Memperbolehkan melakukan pengaksesan secara random

Hanya memperbolehkan pengaksesan secara sekuensial terhadap elemen

Tidak memerlukan ruang penyimpanan ekstra untuk menyimpan alamat memori

Memerlukan ruang penyimpanan ekstra untuk reference (penyimpan alamat memori)

Tidak bisa dirubah ukuran alokasi memorinya

Ukuran alokasi memori dapat diubah sesuai dengan kebutuhan