DOUBLE LINKED LIST

Oleh:Tim struktur data IF

UNIKOM

Double Linked List

Linked list dengan simpul berisi satu link / pointer yang mengacu ke simpul berikutnya dan satu link/pointer yang mengacu ke simpul sebelumnya.Simpul Double Linked List :       

Medan Data(Info)

Medan Sambungan Kanan(Next)

Medan Sambungan Kiri(Prev)

Deklarasi Double Linked ListType

Nama_Pointer = ↑SimpulSimpul = Record

medan_data : tipedata, prev, next : Nama_PointerEndRecord

nama_var_pointer : Nama_Pointer 

Contoh Deklarasi Double Linked ListType

Point = ↑DataData = Record

info : integer, next, prev : Point Endrecordawal, akhir : Point

Operasi – operasi Double Linked List

1. Penciptaan (Create)2. Penyisipan3. Penghapusan4. Traversal5. Pencarian (Searching)6. Pengurutan (Sorting)7. Penghancuran (Destroy)

Penciptaan

Sama seperti pada Single Linked List.

awal akhir

Penyisipan di Depan

- List kosong {awal = nil}

awal akhir

baru 1

Penyisipan di Depan (lanjutan)- List tidak kosong {awal ≠ Nil}

Mula-mula keadaan list:awal

2 3

akhir

baru

1

Penyisipan di Depan (lanjutan)

awal

2 3

akhir

1

Keadaan list setelah terjadi penyisipan di depan/awal pada kondisi list tidak kosong:

baru

Penyisipan di Belakang

- List kosong {awal = nil}

{sama seperti pada penyisipan di depan}

- List tidak kosong {awal ≠ Nil}awal

2 3

akhir

baru

1

Penyisipan di Belakang (lanjutan)

awal

2 3

akhir

1

Keadaan list setelah terjadi penyisipan di belakang/akhir pada list tidak kosong

baru

Awal5 97

Akhir

10

Awal

5 97

Akhir

10

bantu

Penyisipan di Tengah

Misalkan akan menyisipkan angka 4 sebelum angka 9

Mula-mula keadaan list sebagai berikut:

Penyisipan di Tengah (lanjutan)

awal

9 107

akhir

5

bantu

baru

4

Penghapusan di depan

Awal

Akhir2

- Satu Simpul

menjadiAwal

Akhir2

Awal

Akhir

Penghapusan di depan (lanjutan)

- Lebih dari Satu Simpul

awalphapus

5

akhir

1 42

Elemen

Penghapusan di belakang

- Satu Simpul {sama seperti penghapusan di depan}

awal phapus

akhir

4

Elemen

5 12

- Lebih dari Satu Simpul

Penghapusan di Tengah

awal phapus

5 7 9 10

akhir

Elemen

awal

5 9 10

akhir

- Satu Simpul {sama seperti penghapusan di depan}- Lebih dari Satu SimpulMisalkan data yang akan dihapus angka 7

Buatlah subrutin untuk menghapus satu simpul di tengah!

Operasi-operasi lainnya

Operasi-operasi lainnya seperti traversal, searching, sorting dan destroy diperlakukan sama seperti pada single linked list

Tugas

Ubah tugas yang menggunakan single linked list menjadi double linked list, dengan Menu sbb:MENU UTAMA1. Sisip Data2. Hapus Data3. Cari Data4. Tampil Data5. Keluar

MENU SISIP1. Sisip Depan2. Sisip Tengah3. Sisip Belakang4. Kembali ke Menu

Utama

MENU HAPUS1. Hapus Depan2. Hapus Tengah3. Hapus Belakang4. Kembali ke Menu

Utama

MENU CARI1. Cari Kode2. Cari

Nama/Harga/Stok3. Kembali ke Menu

Utama

Data harus sudah tersusundan memanggil satu subrutin traversal lainnya

Memanggil subrutin penghancuran

TERIMA KASIH