Pertemuan Ke - 5

Linked List

• Linked list atau biasa disebut senarai berantaiadalah suatu kumpulan data yang salingterhubung antar 1 data dengan databerikutnya. Suatu element (disebut dengannode) dalam linked list selalu mempunyaihubungan dengan data berikutnya. Agar lebihjelas perhatikan contoh di bawah ini :

Linked List

Dalam gambar1 di atas, terlihat bahwa ada 4 buah data. Setiapdata mempunyai anggota yang menunjuk ke data berikutnya,kecuali elemen terakhir yang berisi NULL. NULL berarti bahwaelemen tersebut tidak menunjuk ke posisi apapun. Selain ituelemen pertama ditunjuk oleh variable Awal dan elementerakhir ditunjuk oleh variable Akhir.

Linked List

• Setiap elemen dari linked list mempunyai 2bagian yaitu bagian data (info) yang bernilaidengan angka, dan sebagian lagi adalahpenunjuk ke data berikutnya (pointer).

• Linked list merupakan suatu penyimpanandata yang dinamis.

Linked ListStruktur data linier, dengan alokasi dinamis. Linked list mempunyai komponennode dan link.

Representasi linked list adalah struktur data record yang terdiri daribeberapa field informasi yang terhubung dengan link.

Sedangkan linked adalah data dengan tipe data pointer.

Jenis – jenis linked list :

1. LINEAR SINGLY LINKED LIST2. CIRCULAR SINGLY LINKED LIST3. LINEAR DOUBLY LINKED LIST4. CIRCULAR DOUBLY LINKED LIST

Linked List mempunyai beberapa operasi, yaitu :1. Menyisip di belakang2. Menyisip di tengah3. Menyisip di depan4. Menghapus di belakang5. Menghapus di tengah6. Menghapus di depan

Jenis-Jenis Senarai (List)

• Singly Linked List

– Linear Singly Linked List

– Circular Singly Linked List

• Double Linked List

– Linear Doubly Linked List

– Circular Doubly Linked List

Singly Linked List

• List tunggal adalah list yang elemennya hanyamenyimpan informasi elemen stelahnya(next), sehingga jalannya pengaksesan listhanya dapat dilakukan secara maju. Listtunggal terbagi menjadi 3 jenis yaitu listtunggal dengan kepala (first), list tunggaldengan kepala(first) dan ekor (tail), serta listtunggal yang berputar

Singly Linked List• Representasi dari ketiga list tersebut dapat

dilihat pada gambar berikut:

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

Ciri – Cir Linear Singly Linked List :

1. Mempunyai satu anak panah yang mengarah dari field Next ke field Info

2. Satu node terdiri dari dua field, info dan next

3. Mempunyai elemen terakhir

4. Elemen terakhir adalah elemen yang field next bernilai NULL

PENELUSURAN PADALINEAR SINGLY LINKED LIST

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

ff00 'C'

ff01 ff0e

ff04 'A'

ff05 ff08

ff08 'B'

ff09 ff00

ff0e 'D'

ff0f NULL

Data

Next

Data

Next

Data

Next

Data

Next

ff04 Headff3f

Penelusuran :

Awal = ff04, maka info dari ff04 = ‘A’

Next ff04 = ff08, maka info dari ff08 = ‘B’

Next ff08= ff00, maka info dari ff00 = ‘C’

Next ff00= ff0e, maka info dari ff0e = ‘D’

Next ff0e = NULL, akhir list

List = ‘ABCD’

Operasi Menyisip di Belakang pada Linear Singly Linked List

1. Operasi menyisip di belakang adalah operasimenambah data dibelakang linear singly linked list.

2. Berikut ini adalah langkah – langkah untukmenyisip dibelakang:a. Elemen baru akan menjadi elemen terakhir

b. Field next elemen baru = NULL

c. Field next elemen terakhir dari list awal berubah= Predeseseor elemen baru

PENYISIPAN NODELINEAR SINGLY LINKED LIST

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

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

?

ff00 'C'

ff01 ff0e

ff04 'A'

ff05 ff08

ff08 'B'

ff09 ff00

ff0e 'D'

ff0f NULL ff0b

Data

Next

Data

Next

Data

Next

Data

Next

ff04 Headff3f

NULL

ff0e

Node Baru

ff0b

ff0c

ff0b

Penunjuk

Menyisip di belakang :

1. Elemen baru akan menjadi elemen terakhir

2. Field next elemen baru = NULL

3. Field next elemen terakhir dari list awal berubah =

Predeseseor elemen baru

Operasi Menyisip di Tengah pada Linear Singly Linked List

1. Operasi menyisip dibelakang adalah operasi menambahelemen baru pada linear singly linked list.

2. Untuk dapat menyisip ditengah linear singly linked list,operasi ini memerlukan elemen bantu sebagai penunjukposisi elemen baru, karena setelah diketahui elemen apayang jadi bantu, elemen baru akan disisipkan disisi kananelemen bantu.

3. Berikut ini adalah langkah – langkah untuk menyisip ditengah pada linear singly linked list :a. Memerlukan elemen bantub. Elemen baru akan diletakan di sisi kanan elemen bantuc. Field next elemen bantu field info elemen barud. Field next elemen baru field info elemen berikutnya

PENYISIPAN NODELINEAR SINGLY LINKED LISTff00 'C'

ff01 ff0e

ff04 'A'

ff05 ff08

ff08 'B'

ff09 ff00

ff0e 'D'

ff0f NULL

Data

Next

Data

Next

Data

Next

Data

Next

ff04 Headff3f

Node Baru

ff0b

ff0c

ff0b

Penunjuk

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

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

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

?Menyisip di tengah

1. Memerlukan elemen bantu

2. Elemen baru akan diletakan di sisi kanan elemen bantu

3. Field next elemen bantu field info elemen baru

4. Field next elemen baru field info elemen berikutnya

Operasi Menyisip di Depan pada Linear Singly Linked List

1. Operasi menyisip di depan adalah operasimenambah elemen baru dengan menggeserelemen paling kiri. Untuk menambah didepanmaka nilai predesesor elemen baru sama dengannilai awal list.

2. Berikut ini adalah langkah – langkah untukmenyisip di depan pada linear singly linked list :a. Predesesor elemen baru = nilai awal listb. Elemen baru akan jadi elemen pertamac. Field next elemen baru field info elemen

berikutnya

PENYISIPAN NODELINEAR SINGLY LINKED LIST

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

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

ff00 'C'

ff01 ff0e

ff04 'A'

ff05 ff08

ff08 'B'

ff09 ff00

ff0e 'D'

ff0f NULL

Data

Next

Data

Next

Data

Next

Data

Next

ff04 Headff3f

Node Baru

ff0b

ff0c

ff0b

Penunjuk

Menyisip di depan

1. Predesesor elemen baru = nilai awal list

2. Elemen baru akan jadi elemen pertama

3. Field next elemen baru field info elemen berikutnya

Operasi Menghapus di Belakang pada Linear Singly Linked List

1. Operasi menghapus di belakang pada linear singly linked listadalah operasi yang menghilangkan elemen paling kanan.

2. Berikut ini adalah langkah – langkah untuk menghapuselemen terakhir pada linear singly linked list :a. Memerlukan elemen bantub. Elemen bantu di sisi kiri elemen yang akan dihapusc. Setelah dihapus, elemen bantu jadi elemen terakhird. Field next elemen bantu berubah menjadi NULL

PENGHAPUSAN NODELINEAR SINGLY LINKED LIST

ff00 'C'

ff01 ff0e NULL

ff04 'A'

ff05 ff08

ff08 'B'

ff09 ff00

ff0e 'D'

ff0f NULL

Data

Next

Data

Next

Data

Next

Data

Next

ff04 Headff3f

ff00 Penunjuk

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

'A' 'B' 'C'

'A' 'B' 'C'

Menghapus di belakang :

1. Memerlukan elemen bantu

2. Elemen bantu di sisi kiri elemen yang akan dihapus

3. Setelah dihapus, elemen bantu jadi elemen terakhir

4. Field next elemen bantu berubah menjadi NULL

Operasi Menghapus di Tengah pada Linear Singly Linked List

1. Operasi menghapus di tengah pada linear singly linked listhamper sama dengan operasi menyisip di tengah pada linearsingly linked list, yaitu untuk memerlukan elemen bantu.

2. Berikut ini adalah langkah – langkah untuk menghapuselemen di tengah linear singly linked list :a. Memerlukan elemen bantub. Elemen bantu di sisi kiri elemen yang akan di hapusc. Setelah dihapus, field next elemen bantu field info

Elemen berikutnya

PENGHAPUSAN NODELINEAR SINGLY LINKED LIST

ff00 'C'

ff01 ff0e

ff04 'A'

ff05 ff08

ff08 'B'

ff09 ff00 ff0e

ff0e 'D'

ff0f NULL

Data

Next

Data

Next

Data

Next

Data

Next

ff04 Headff3f

ff08 Penunjuk

ff00 Node hapus

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

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

'A' 'B' 'D'

Menghapus di tengah :

1. Memerlukan elemen bantu

2. Elemen bantu di sisi kiri elemen yang akan di hapus

3. Setelah dihapus, field next elemen bantu field info

Elemen berikutnya

Operasi Menghapus di Depan pada Linear Singly Linked List

1. Operasi menghapus di depan pada linear singly linked listadalah operasi menghilangkan elemen paling kiri.

2. Berikut ini adalah langkah – langkah untuk menghapuselemen didepan pada linear singly linked list :a. Memerlukan elemen bantub. Elemen bantu di sisi kanan elemen yang akan di hapusc. Setelah dihapus, awal list field info elemen bantud. Setelah di hapus, elemen bantu jadi elemen pertama

PENGHAPUSAN NODELINEAR SINGLY LINKED LISTff00 'C'

ff01 ff0e

ff04 'A'

ff05 ff08

ff08 'B'

ff09 ff00 ff0e

ff0e 'D'

ff0f NULL

Data

Next

Data

Next

Data

Next

Data

Next

ff04 Headff3f

ff08 Penunjuk

ff00 Node hapus

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

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

'B' 'D''C'

Menghapus di depan :

1. Memerlukan elemen bantu

2. Elemen bantu di sisi kanan elemen yang akan di hapus

3. Setelah dihapus, awal list field info elemen bantu

4. Setelah di hapus, elemen bantu jadi elemen pertama

Contoh Soal1. Perhatikan table berikut :

Predesesor Info Next

Awal = 1 3 2

3 1 NULL

2 2 3

a. Gambarkan list awal

b. Buat penelusuran

c. Tambahkan elemen berikut dari list awal :

Predesesor Info Next

4 4 NULL

Contoh Soal2. Perhatikan table berikut :

Predesesor Info Next3 1 NULL

Awal = 4 2 3

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

Predesesor Info Next3 1 5

Contoh Soal3. Perhatikan table berikut :

Predesesor Info NextAwal = 2 X NULL

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

Predesesor Info Next2 Y 1

Contoh Soal4. Perhatikan table berikut :

Predesesor Info Next 2 O NULL

Awal = 3 L 11 M 2

a. Gambarkan list awalb. Hapus elemen O dari list awal

Contoh Soal5. Perhatikan table berikut :

Predesesor Info Next3 2 4

Awal = 2 4 11 3 34 1 NULL

a. Gambarkan list awalb. Hapus elemen ‘3’ dari list awalc. Hapus elemen pertama dari list bd. Hapus elemen terakhir dari list c

Contoh Soal6. Perhatikan table berikut :

Predesesor Info NextAwal = 5 2 7

9 5 NULL7 3 9

a. Gambarkan list awalb. Hapus elemen pertama dari list awal

Latihan SoalPredesesor Info Next

4 C 1

Awal = 3 A 2

1 D 6

6 E NULL

2 B 4

Perhatikan table berikut :

1. Gambarkan list awa

2. Buat penelusuran

Latihan Soal

Predesesor Info Next

Awal = 1 A 2

3 M NULL

2 T 3

Perhatikan table berikut :

1.Gambarkan list awal

2.Buat penelusuran

3.Tambahkan elemen berikut dari list awal :

Predesesor Info Next

4 A NULL

Latihan Soal

Predesesor Info Next

3 1 NULL

Awal = 4 2 3

Perhatikan table berikut :

1. Gambarkan list awal

2. Tambahkan elemen berikut dari list awal :

Predesesor Info Next

3 1 5

Predesesor Info Next

7 2 NULL

3. Tambahkan elemen berikut dari list b :

Predesesor Info Next

4 1 6

4. Tambahkan elemen berikut dari list c :

Latihan Soal

Predesesor Info Next

3 2 4

Awal = 2 4 1

1 3 3

4 1 NULL

Perhatikan table berikut :

1.Gambarkan list awal

2.Hapus elemen ‘3’ dari list awal

3.Hapus elemen ‘2’ dari list b

Latihan Soal

Perhatikan permintaan soal berikut :

1.Buat list awal dengan hasil : ‘UDANG’

2.Operasikan menjadi : ‘BUDANG’

3.Operasikan menjadi : ‘BDANG’

4.Operasikan menjadi : ‘BADANG’

5.Operasikan menjadi : ‘BADNG’

6.Operasikan menjadi : ‘BADUNG’

Latihan Soal

Perhatikan permintaan soal berikut :

1.Buat list awal dengan hasil : ‘SISTEM’

2.Operasikan menjadi : ‘ISTEM’

3.Operasikan menjadi : ‘HISTEM’

4.Operasikan menjadi : ‘HITEM’

5.Operasikan menjadi : ‘HITM’

6.Operasikan menjadi : ‘HITAM’

• Ada pertanyaan ???