Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

StruktuR DATA LINKED LIST

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

StruktuR DATA LINKED LIST

Standar KompetensiSetelah mengikuti perkuliahan mahasiswa semester 2S1 Teknik Informatika STMIK Widya Cipta Dharma mampumeningkatkan pemahaman struktur data dan penanganandata bagi perencanaan algoritma dan penyusunan program,misalnya sebagai dasar teknik dari sebuah penyusunandatabase.

Kompetensi DasarMahasiswa dapat memahami cara kerja Linked List dan menerapkannya kedalam

aplikasi

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

• Definisi : – struktur data yang terdiri dari rantaian

elemen sejenis yang saling berhubungan. Setiap elemen memiliki pendahulu danpenerusnya (kecuali elemen terakhir)

• Contoh : – Struktur ini mirip kereta api, dimana

kepalanya seperti lokomotif, elemennyaseperti gerbong kereta dan datanya sepertipenumpang/barang

SENARAI / LINK LIST

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

X1 X2 X3 X4S

Item / Data

Penunjuk

Kepala

NIL

p q r s

MODEL SENARAI

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Info Next

Elemen Senarai

Kamus Data :Info : array [1..4] of StringNext : array [1..4] of Integer

A

C

B

D

3

4

2

Nil

Info Next

1

2

3

4

KAMUS DATA SENARAI

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

A

C

B

D

3

4

2

Nil

Info Next

1

2

3

4

A B C DS

1 3 2 4

S

REPRESENTASI SENARAI DENGAN ARRAY _SENARAI BERKAIT

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Dua Notasi :

�INFO (x) : Data yang ada di alamat X�NEXT (x) : Alamat elemen berikutsetelah X

A B C DS

1 3 2 4

Contoh : Next (1) = 3 Info (1) = A

NOTASI Info dan Next

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

X1

X1 X2 X3 X4

Senarai / List KOSONG

Senarai / List dengan 1 elemen

Senarai / List dengan 4 elemen

p q r s

p

Awal

Awal

Awal

KONDISI SENARAI

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

18 3 69 24S

p q r s

1. Cipta_Senarai : membuat senarai kosong

2. Sisip_Awal : menyisipkan elemen di awal

3. Sisip_Akhir : menyisipkan elemen di akhir

4. Hapus_Awal : menghapus elemen di awal

5. Hapus_Akhir : menghapus elemen di akhir

Operasi Dasar Senarai

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Membuat senarai kosong

S S =Nil Info Next

1

2

3

4

S

Cipta Senarai

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Menyisipkan elemen di awal

18 3 69A

p q r

24

x

B

12

Next(B) = Awal(A)Awal(A) = Awal(B)

Sisip Awal

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Menyisipkan elemen di akhir

18 3 69Awal

1 2 3

24

P

B

Akhir = AwalWhile (next(Akhir) <> Nil do

Akhir = Next(Akhir)EnddoNext(Akhir) = P

Akhir

Sisip Akhir

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Menghapus elemen di awal

18S

IF Next (S)) = Nil thenP = SS = Nil

End doP

P : untuk menyimpan alamat elemenyang akan dihapus

Hapus Awal (Kondisi 1 Elemen)

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Menghapus elemen di awal

18 3 69S

1 2 3

IF Next (S) <> Nil thenP = SS = Next(S)

EnddoP

P : untuk menyimpan alamat elemenyang akan dihapus

Hapus Awal (Kondisi N Elemen)

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Senarai / List KOSONG

Head-Tail Link List

Awal Akhir Awal=NIL and Akhir=NIL

Senarai / List dengan N elemenAwal = P Akhir = R

X1 X2 X3

p q r AkhirAwal

KONDISI LIST BERKAIT (KEPALA + EKOR)

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Head-Tail Link List

X1 X2 X3

p q r Akhir

next

Awal

18

HBagaimana jika elemen 18 dengan address H :�SISIP_AWAL / SISIP_AKHIR�Hapus_Awal / Hapus_Akhir

LIST BERKAIT (KEPALA+EKOR)

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Senarai / List KOSONG

Double Link List

AwalAwal = NIL

Senarai / List dengan N elemen

Prev (P) = NILNext (R) = NIL

X1 X2 X3

p q rAwal

KONDISI LIST BERKAIT (PENUNJUK GANDA)

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

X1 X2 X3

p q r

prev next

Awal

Bagaimana jika elemen 18 dengan address H :�SISIP_AWAL�SISIP_AKHIR

18

H

LIST BERKAIT (PENUNJUK GANDA)

Double Link List

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Senarai / List KOSONG

Awal AkhirAwal=NIL and Akhir=NIL

Senarai / List dengan N elemen

X1 X2 X3

p q r AkhirAwal

LIST BERKAIT (KEPALA+EKOR dan PENUNJUK GANDA)

Head-Tail Double Link List

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

X1 X2 X3

p q r Akhir

prev next

Awal

Bagaimana jika elemen 18 denganaddress H :�SISIP_AWAL�SISIP_AKHIR

18

H

LIST BERKAIT (KEPALA+EKOR dan PENUNJUK GANDA)

Head-Tail Double Link List

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Senarai / List KOSONG

Awal Awal=NIL

Senarai / List dengan N elemen Awal = P Next (R) = P

X1 X2 X3

p q rAwal

KONDISI LIST BERKAIT SIRKULER

Circle Link List

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Linked List

• Salah satu bentuk struktur data fundamental.– Dapat digunakan untuk membentuk struktur data yang

lebih kompleks.• Serangkaian simpul/node yang berisi data dan saling

terkait.• Memanfaatkan kombinasi dari tipe data pointer dan

tipe data record/structure (pointer to records).• Setara dengan array of record,

tetapi dengan kelebihan :– Alokasi memori lebih fleksibel (dinamis), karena :

• Tidak perlu memindah-mindahkan data.• Tidak perlu menempatkan data secara berurut dalam ruang

memori.

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Linked List• Prinsip linked list dapat kita bandingkan

seperti suatu rantai yang matanyadihubungkan satu sama lain. Mata rantaitersebut dapat kita asosiasikan denganrecord atau node.

• Ciri khas suatu node dalam linked list adalahharus selalu terdapat field, paling sedikit duabagian, yaitu :– Data– Pointer.

• Secara umum linked list dibedakan atas 2 macam, yaitu :– Single Linked List– Double Linked List

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Bentuk-bentuk Linked List

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Single-linked list

• Satu simpul/node memiliki sebuahvariabel pointer yang digunakan untukmenunjuk pada simpul/node berikutnya.

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Double-linked list

• Satu simpul/node menyimpan dua variabelbertipe 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.

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Circular linked list

• Pointer pada simpul/node terakhirmenunjuk pada simpul/node pertama.

• Varian :– Circular single linked list.– Circular double linked list.

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Headed linked list

• Simpul pertama tidak diisi dengandata, tetapi diisi dengan informasiyang berhubungan dengan metadata linked list

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

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

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

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 ukuranalokasi memorinya �

Ukuran alokasi memori dapatdiubah sesuai dengan kebutuhan

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Apa yang Dimaksud dengan Linked List

Ask 1

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

• Apa yang dimaksud dengan Double Linked List

Ask 2

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Jelaskan Operasi Dasar Senarai

Ask 3

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

• Gambarkan proses sisip awal pada senarai

Ask 4

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

• Jelaskan perbedaan Array dan Linked List

Ask 5

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Referensi

Materi Ini Bisa Anda Download Di :http://henypratiwi.com/

Zakaria, Teddy Marcus dan Agus Prijono. 2006. Konsep dan Implementasi Struktur Data. Bandung: Informatika.

Hariyanto, Bambang. 2008. Struktur Data : PondasiMembuat Program Yang Elegan. Bandung: Informatika.

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan

Penyusun :Heny Pratiwi, S.Kom., M.Pd.

STMIK Widya Cipta Dharma

SAMARINDA - KALTIMEmail : ayokitakuliah@gmail.comFanspage : ayokitakuliahTwitter : @ayokitakuliahWebsite : www.henypratiwi.com

Home

SK/KD

Materi

Evaluasi

Indikator

Referensi

Keluar

Latihan