linear doubly linked listlinear doubly linked list 1. operasi menyisip di belakang pada linear...

49
Linear Doubly Linked List

Upload: others

Post on 11-Feb-2021

29 views

Category:

Documents


1 download

TRANSCRIPT

  • Linear Doubly Linked List

  • Doubly Linked List

    Doubly linked list adalah bentuk list dengan ciriutama :

    – Mempunyai dua buah anak panah bolak – balik

    – Mempunyai node/elemen yang terdiri dari tigafield yaitu prev, info dan next

  • Doubly Linked List

    Doubly linked list mempunyai dua varian yaitu :

    – Linear doubly linked list

    – Circular doubly linked list

  • Linear Doubly Linked List

    • Linear doubly linked list sendiri mempunyaibeberapa ciri khusus yaitu :

    – Mempunyai dua anak panah yang mengarah darifield Next ke field Prev dan dari Field Prev ke Field Next

    – Satu node terdiri dari tiga field, Prev, Info, Next

    – Field Next elemen terakhir = NULL

    – Field Prev elemen pertama = NULL

  • Linear Doubly Linked List

    Linear Doubly Linked List mempunyai duapenelusuran, yaitu :

    – Penelusuran Next, diakhiri dengan Next = NULL

    – Penelusuran Prev,diakhiri dengan Prev = NULL

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

    Ilustrasi Linear Doubly Linked List

  • Linear Doubly Linked List

    Berikut ini adalah contoh Linear Singly Linked List dan Penelusurannya :

    Awal = 1

    Prev Info Next

    3 C 4

    NULL A 2

    2 B 3

    4 D NULL

    a.Buat list awalb.Buat penelusuran

  • Linear Doubly Linked Lista.Buat list awal

  • Linear Doubly Linked List

    Penelusuran Next

    Awal = 1, maka info 1 = ‘A’

    Next 1 = 2, maka info 2 = ‘B’

    Next 2 = 3, maka info 3 = ‘C’

    Next 3 = 4, maka info 4 = ‘D’

    Next 4 = Null, akhir list

    List : ‘ABCD

    Penelusuran Prev

    Awal = 1, maka info 1 = ‘D’

    Prev 1 = 4, maka info 4 = ‘C’

    Prev 4 = 3, maka info 3 = ‘B’

    Prev 3 = 2, maka info 2 = ‘A’

    Prev 2 = Null, akhir list

    List : ‘DCBA’

    B. Penelusuran

  • Operasi – Operasi yang ada padaLinear Doubly Linked List

    1. Operasi menyisip di belakang pada Linear Doubly Linked List

    2. Operasi menyisip di tengah pada Linear Doubly Linked List

    3. Operasi menyisip di depan pada Linear Doubly Linked List

    4. Operasi menghapus di belakang pada Linear Doubly Linked List

    5. Operasi menghapus di tengah pada Linear Doubly Linked List

    6. Operasi menghapus di depan pada Linear Doubly Linked List

  • Operasi Menyisip di Belakang

    Operasi menyisip di belakang pada linear doublylinked list adalah menambah elemen baru diposisi paling kanan. Dengan menambahdibelakang maka terjadi perubahan pada satunilai next.

  • Operasi Menyisip di Belakang

    Berikut adalah langkah – langkah dalammenyisip di belakang pada Linear DoublyLinked List

    – Elemen baru menjadi elemen terakhir

    – Field next elemen baru = NULL

    – 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 Menambah di Belakang Pada Linear Doubly Linked List

  • Operasi Menyisip di Belakang

    • Perhatikan table berikut

    Awal = 1

    Prev Info Next

    4 4 NULL

    NULL 3 4

    a.Buat list awalb.Tambahkan dari elemen berikut dari list awal :

    Prev Info Next

    2 5 NULL

  • Operasi Menyisip di Belakanga.Buat list awal

  • Operasi Menyisip di Belakang

    b. Operasi menambah dibelakang

  • Operasi Menyisip di Tengah

    • Operasi menyisip di tengah pada LinearDoubly Linked List membutuhkan elemenbantu. Hampir sama dengan operasi menyisipdi tengah pada linear singly linked list, namunbedanya pada linear doubly operasi menyisipdi tengah akan mengakibatkan satu nilai prevberubah.

  • Operasi Menyisip di Tengah

    Berikut ini adalah langkah – langkah untukmenyisip di tengan pada linear doubly linkedlist :

    – Memerlukan elemen bantu

    – Elemen baru diletakkan di sisi kanan elemenbantu

    – Field prev elemen bantu field next elemen baru

    – Field prev elemen baru field next 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 Menambah di Tengah Pada Linear Doubly Linked List

  • Operasi Menyisip di Tengah

    Contoh :

    • Perhatikan table berikut :

    Awal = 4

    Prev Info Next

    NULL 1 3

    3 3 NULL

    a.Buat list awal

    b.Tambahkan elemen berikut dari list awal :

    Prev Info Next

    3 2 2

  • Operasi Menyisip di Tengah

    a. Buat List Awal

  • Operasi Menyisip di Tengah

    b. Operasi menyisip di tengah

  • Operasi menyisip di depan

    • Operasi menyisip di depan pada linear doublylinked list adalah operasi menambah elemenbaru pada posisi paling kiri. Operasi ini jugaakan mnegakibatkan satu nilai Prev berubah.

  • Operasi menyisip di depan

    Berikut ini adala langkah – langkah untukmenyisip elemen baru pada linear doublylinked list :

    – Memerlukan elemen bantu

    – Elemen baru diletakkan di sisi kiri elemen bantu

    – Elemen baru menjadi elemen pertama

    – Field prev elemen baru = NULL

  • Operasi menyisip di depan

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

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

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

    Ilustrasi Operasi Menambah di Depan Pada Linear Doubly Linked List

  • Operasi menyisip di depan

    Contoh :

    • Perhatikan table berikut :

    Awal =

    1

    Prev Info Next

    NULL 4 3

    3 5 NULL

    a.Buat list awal

    b.Tambahkan elemen berikut dari list awal :

    Prev Info Next

    NULL 3 2

  • Operasi menyisip di depan

    a. Buat List Awal

  • Operasi menyisip di depan

    b. Operasi menyisip di depan

  • Operasi Menghapus di Belakang

    • Operasi menghapus di belakang pada lineardoubly adalah operasi yang membutuhkanelemen bantu. Elemen bantu adalah elemenyang letaknya disisi kiri elemen paling akhir.Setelah operasi menghapus elemen terakhirselesai dilakukan maka elemen bantu menjadielemen terakhir. Operasi ini menyebabkansatu nilai pada field next berubah.

  • Operasi Menghapus di Belakang

    Berikut ini adalah langkah – langkah untukmelakukan operasi menghapus pada LinearDoubly Linked List :

    – Memerlukan elemen bantu

    – Elemen bantu di sisi kiri elemen yang akan dihapus

    – Setelah dihapus, elemen bantu menjadi elementerakhir

    – Setelah dihapus, field next elemen bantu berubahmenjadi NULL

  • Operasi Menghapus di Belakang

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

    'A' 'B' 'C'

    'A' 'B' 'C'

    Ilustrasi Operasi Menghapus di Belakang Pada Linear Doubly Linked List

  • Operasi Menghapus di Belakang

    Contoh :

    • Perhatikan table berikut :

    Awal = 1

    Prev Info Next

    4 B 3

    NULL A 2

    2 X 4

    3 Z NULL

    a.Buat list awal

    b.Hapus elemen terakhir dari list awal

  • Operasi Menghapus di Belakanga. Buat List Awal

  • Operasi Menghapus di Belakangb. Operasi Menghapus di Belakang

  • Operasi Menghapus di Tengah

    Operasi menghapus di tengah pada linear doublylinked list akan menghasilkan perubahan nilaipada satu field prev.

    Berikut ini adalah langkah – langkah untukmenghapus elemen di tengah pada linear doublylinked list :– Memerlukan elemen bantu

    – Elemen bantu di sisi kiri elemen yang akan dihapus

    – Setelah dihapus, field prev elemen bantu = 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 Linear Doubly Linked List

  • Operasi Menghapus di Tengah

    Contoh :

    • Perhatikan table berikut :

    Awal =

    3

    Prev Info Next

    1 L 4

    2 U 1

    NULL J 2

    4 I NULL

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

  • Operasi Menghapus di Tengah

    a. Buat list awal

  • Operasi Menghapus di Tengah

    B. Operasi menghapus di tengah

  • Operasi Menghapus di Depan

    Operasi menghapus pada linear doubly linked list adalahoperasi yang akan mengakibatkan satu nilai prevberubah.

    Berikut adalah langkah – langkah untuk melakukanoperasi menghapus di depan pada linear doubly linkedlist :– Memerlukan elemen bantu

    – Elemen bantu disisi kanan elemen yang akan dihapus

    – Setelah dihapus, elemen bantu menjadi elemen pertama

    – Setelah dihapus, field prev elemen bantu berubah menjadiNULL

  • Operasi Menghapus di Depan

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

    'B' 'C' 'D'

    'B' 'C' 'D'

    Ilustrasi Operasi Menghapus di Depan Pada Linear Doubly Linked List

  • Operasi Menghapus di Depan

    Contoh :

    • Perhatikan table berikut

    Awal = 1

    Prev Info Next

    3 U NULL

    4 L 3

    NULL U 4

    a. Buat list awal

    b. Hapus elemen pertama dari list awal

  • Operasi Menghapus di Depan

    a. Buat list awal

  • Operasi Menghapus di Depan

    b. Operasi Menghapus di Depan

  • Ada Pertanyaan???

  • Latihan Soal 1

    Perhatikan table berikut

    Awal = 4

    Prev Info Next

    NULL 1 3

    3 3 NULL

    1. Buat list awal

    2. Tambahkan elemen berikut dari list awal :

    Prev Info Next

    3 2 2

  • Latihan Soal 2Perhatikan table berikut

    Awal = 2 Prev Info Next

    NULL X NULL

    a. Buat list awal

    b. Tambahkan alemen berikut dari list awal :

    Prev Info Next

    3 Z NULL

    c. Tambahkan elemen berikut dari list b :

    Prev Info Next

    3 Y 4

  • Latihan Soal 3Perhatikan table berikut :

    Awal = 1

    Prev Info Next

    4 B 3

    NULL A 2

    2 X 4

    3 Z NULL

    a. Buat list awal

    b. Hapus elemen ‘A’ dari list awal

    c. Hapus elemen kedua dari list b

    d. Hapus elemen terakhir dari list c

  • Latihan Soal 4

    3. Perhatikan permintaan soal berikut :

    a. Buat list awal dengan hasil : ‘AL’ atau ‘LA’

    b. Operasikan menjadi : ‘ALA’ atau ‘ALA’

    c. Operasikan menjadi : ‘MALA’ atau ‘ALAM’

    d. Operasikan menjadi ; ‘MALAM’ atau ‘MALAM’

  • Tugas

    2. Perhatikan permintaan soal berikut :

    a. Buat list awal dengan hasil : ‘MARAK’ atau‘KARAM’

    b. Operasikan menjadi : ‘MARA’ atau ‘ARAM’

    c. Operasikan menjadi : ‘AMARA’ atau ‘ARAMA’

    d. Operasikan menjadi : ‘AMAR’ atau ‘RAMA’

    e. Operasikan menjadi : ‘AMA’ atau ‘AMA’

    f. Operasikan menjadi : ‘LAMA’ atau ‘AMAL’