circular doubly linked listcircular doubly linked list berikut ini adalah ciri –ciri khusus yang...

48
Circular Doubly Linked List

Upload: others

Post on 11-Feb-2021

30 views

Category:

Documents


0 download

TRANSCRIPT

  • Circular Doubly Linked List

  • Circular Doubly Linked List

    Circular doubly linked list adalah variasi terakhirdari linked list.

  • Circular Doubly Linked List

    Berikut ini adalah ciri – ciri khusus yang dimiliki olehcircular doubly linked list :– Mempunyai dua anak panah bolak – balik– Anak panah mengarah dari field next ke prev dan dari

    field prev ke field next– Field prev elemen pertama = nilai awal list– Field next elemen terakhir = nilai awal list– Anak panah dari field next elemen terakhir mengarah

    ke field prev elemen pertama– Anak panah dari field prev elemen pertama mengarah

    ke field next elemen terakhir

  • Circular Doubly Linked List

    'A' 'B' 'C' 'D'

    Ilustrasi Circular Doubly Linked List

  • Circular Doubly Linked List

    • Circular Doubly Linked List mempunyai Duapenelusuran, yaitu :

    • Penelusuran Next, ‘diakhiri’ dengan Next = nilai awal list

    • Penelusuran Prev,‘diakhiri’ dengan Prev = nilai awal list

  • Circular Doubly Linked List

    Contoh :

    • Perhatikan table berikut :

    Awal = 4

    Prev Info Next

    2 I 3

    4 N 2

    3 I 4

    a. Buat list awal

    b. Buat penelusuran

  • Circular Doubly Linked List

    a. Buat list awal

  • Circular Doubly Linked List

    B. Buat penelusuranPenelusuran Next

    Awal = 4, maka info 4 = ‘N’Next 4 = 2, maka info 2 = ‘I’Next 2 = 3, maka info 3 = ‘I’Next 3 = 4, maka info 4 = ‘N’Dan seterusnya …List : ‘NIIN…’

    Penelusuran PrevAwal = 4, maka info 4 = ‘I’Prev 4 = 3, maka info 3 = ‘I’Prev 3 = 2, maka info 2 = ‘N’Prev 2 = 4, maka info 4 = ‘I’Dan seterusnya …List : ‘IINI…’

  • Operasi menyisip di belakang

    Berikut ini adalah langkah – langkah untukoperasi menyisip dibelakang pada CircularDoubly Linked List

    – Elemen baru menjadi elemen terakhir

    – Field next elemen baru = nilai awal list

    – Field next elemen terakhir pada list awal = field prev elemen baru

  • Operasi menyisip di belakang

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    Ilustrasi Operasi Menyisip di Belakang Pada Circular Doubly Linked List

  • Operasi menyisip di belakang

    Contoh :

    • Perhatikan table berikut :

    Awal = 2

    Prev Info Next

    1 0 2

    2 2 1

    a. Buat list awal

    b. Tambahkan elemen berikut dari list awal :

    Prev Info Next

    3 1 2

  • Operasi menyisip di belakang

    a. Buat list awal

  • Operasi menyisip di belakang

    b. Tambahkan elemen berikut di belakangi list awal :

  • Operasi menyisip di tengah

    Operasi menyisip di tengah pada circular doublylinked list membutuhkan elemen bantu untukdapat menentukan dimana elemen baru akandiletakkan. Operasi ini akan mengakibatkansebuah nilai prev berubah.

  • Operasi menyisip di tengah

    Berikut ini adalah langkah –langkah untuk operasimenyisip di tengah pada circular doubly linkedlist :

    – Memerlukan elemen bantu

    – Elemen baru diletakkan di kanan elemen bantu

    – Field next elemen bantu = field prev elemen baru

    – Field next elemen baru = field prev elemenberikutnya

  • Operasi menyisip di tengah

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    Ilustrasi Operasi Menambah di tengah pada Circular Doubly Linked List

  • Operasi menyisip di tengah

    Contoh :

    • Perhatikan table berikut :

    Awal =

    5

    Prev Info Next

    2 N 3

    5 I 2

    3 O 5

    a. Buat list awal

    b. Tambahkan elemen berikut dari list awal :

    Prev Info Next

    3 F 4

  • Operasi menyisip di tengah

    a. Buat list awal

  • Operasi menyisip di tengah

    b. Tambahkan elemen berikut dari list awal :

  • Operasi menyisip di depan

    Operasi menyisip di depan pada circular doublylinked list juga memerlukan elemen bantu.Operasi ini akan menyebabkan satu nilai prevberubah.

  • Operasi menyisip di depan

    Berikut ini adalah langkah – langkah untukmelakukan operasi menyisip di depan padacircular doubly linked list .

    – Memerlukan elemen bantu

    – Elemen baru diletakkan di kiri elemen bantu

    – Elemen baru menjadi elemen pertama

    – Field prev elemen baru = nilai awal list

  • Operasi menyisip di depan

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    Ilustrasi Operasi Menambah di Depan Pada Circular Doubly Linked List

  • Operasi menyisip di depan

    Contoh :

    • Perhatikan table berikut :

    Awal = 9

    Prev Info Next

    7 A 9

    9 A 7

    a. Buat list awal

    b. Tambahkan elemen berikut dari list b :

    Prev Info Next

    9 D 5

  • Operasi menyisip di depan

    a. Buat list awal

  • Operasi menyisip di depan

    b. Tambahkan elemen berikut dari list awal :

  • Operasi menghapus di belakang

    Operasi menghapus di belakang pada circulardoubly linked list juga membutuhkan elemenbantu. Elemen bantu ini akan menjadi elementerakhir setelah operasi selesai dilakukan.Operasi ini menyebabkan satu nilai nextberubah.

  • Operasi menghapus di belakang

    Berikut ini adalah langkah – langkah untukmelakukan operasi menghapus di belakangpada circular doubly linked list :

    – Memerlukan elemen bantu

    – Elemen bantu disisi kiri elemen yang akan dihapus

    – Setelah dihapus, elemen bantu jadi elementerakhir

    – Setelah di hapus, field next elemen bantu = nilaiawal list

  • Operasi menghapus di belakang

    'A' 'B' 'C' 'D'

    'A' 'B' C

    Ilustrasi Operasi Menghapus di Belakang Pada Circular Doubly Linked List

  • Operasi menghapus di belakang

    Contoh :

    • Perhatikan table berikut :

    Awal = 1

    Prev Info Next

    5 U 4

    1 S 5

    4 S 3

    3 A 2

    2 H 1

    a. Buat list awal

    b. Hapus elemen terakhir dari list awal

  • Operasi menghapus di belakangJawab :a. Buat list awal

  • Operasi menghapus di belakangb. Hapus elemen terakhir dari list awal

  • Operasi menghapus di tengah

    • Operasi menghapus di tengah pada circulardoubly linked list adalah operasi yangmembutuhkan elemen bantu dan akanmenyebabkan satu nilai prev akan berubah.

  • Operasi menghapus di tengah

    Berikut ini adalah langkah – langkah untukmelakukan operasi menghapus pada circulardoubly linked list :

    – Memerlukan elemen bantu

    – Elemen bantu disisi kiri elemen yang akan dihapus

    – Setelah dihapus, field prev elemen namtu = field next elemen berikutnya

  • Operasi menghapus di tengah

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    'A' 'B' 'C' 'D'

    'A' 'B' 'D'

    Ilustrasi Operasi Menghapus di Tengah Pada Circular Doubly Linked List

  • Operasi menghapus di tengah

    Contoh :

    • Perhatikan table berikut :

    Awal = 9

    Prev Info Next

    9 A 2

    4 A 3

    2 S 4

    3 L 9

    a. Buat list awalb. Hapus elemen ‘S’ dari list awal

  • Operasi menghapus di tengah

    Jawab :

    a. Buat list awal

  • Operasi menghapus di tengah

    b. Hapus ‘S’ dari list awal

  • Operasi menghapus di depan

    • Operasi terakhir pada linked list adalahoperasi menghapus di depan pada circulardoubly linked list. Pada operasi ini satu nilaiprev akan berubah.

  • Operasi menghapus di depan

    Berikut ini adalah langkah – langkah untukmelakukan operasi menghapus di depan padacircular doubly linked list :– Memerlukan elemen bantu

    – Elemen bantu disisi kanan elemen yang akandihapus

    – Setelah dihapus, elemen bantu menjadi elemenpertama

    – Setelah dihapus, field next elemen bantu = nilaiawal list

  • Operasi menghapus di depan

    'A' 'B' 'C' 'D'

    'B' 'C' 'D'

    Ilustrasi Operasi Menghapus di Depan Pada Circular Doubly Linked List

  • Operasi menghapus di depanContoh :

    • Perhatikan table berikut

    Awal = 7

    Prev Info Next

    2 N 1

    1 T 3

    3 R 4

    7 A 2

    4 I 7

    a.Buat list awalb.Hapus elemen ‘A’ dari list awal

  • Operasi menghapus di depan

    Jawab :

    a. Buat list awal

  • Operasi menghapus di depan

    b. Hapus elemen ‘A’ dari list awal

  • Latihan Soal1. Perhatikan table berikut :

    Awal = 2

    Prev Info Next

    1 0 2

    2 2 1

    a. Buat list awal

    b. Tambahkan elemen berikut dari list awal :

    Prev Info Next

    2 1 3

    c. Tambahkan elemen berikut dari list b :

    Prev Info Next

    4 0 2

  • Latihan Soal2. Perhatikan table berikut :

    Awal = 9

    Prev Info Next

    7 A 8

    8 A 7

    a. Buat list awal

    b. Tambahkan elemen berikut dari list awal :

    Prev Info Next

    8 T 6

    c. Tambahkan elemen berikut dari list b :

    Prev Info Next

    9 D 5

  • Latihan Soal

    3. Perhatikan table berikut :

    Awal = 4

    Prev Info Next

    1 N 3

    4 D 2

    2 U 1

    3 I 5

    5 A 4

    a. Buat list awal

    b. Hapus elemen ‘N’ dari list awal

    c. Hapus elemen ‘I’ dari list b

  • Tugas

    1. Perhatikan permintaan soal berikut : – Buat list awal dengan hasil : ‘TURUT…’ atau

    ‘URUTU…’

    – Operasikan menjadi : ‘TRUT…’ atau ‘URTU…’

    – Operasikan menjadi : ‘TRT…’ atau ‘RTR…’

    – Operasikan menjadi : ‘TT…’ atau ‘TT…’

    – Operasikan menjadi : ‘TAT…’ atau ‘ATA’

    – Operasikan menjadi : ‘TAMT…’ atau ‘MATM…’

    – Operasikan menjadi : ‘TAMAT…’ atau ‘AMATA…’