Linked List

Linked list menyimpan data dalam node-node yang tersebar di memori. Setiap node berisi data (info/val) dan pointer ke node berikutnya (next). Kita hanya perlu memegang pointer ke node pertama, yaitu head. Node terakhir menunjuk ke null (atau Nil di notasi algoritmik).

Singly linked list

nilaiposisiinsertFirst(5)insertLast(5)insertAt(1, 5)deleteFirst()deleteAt(1)search(5)

head →

3next

[0]

→

7next

[1]

→

1next

[2]

→ null

Coba klik operasi di atas.

Array vs linked list

	Array	Linked list
Akses elemen ke-i	$O(1)$, langsung dihitung dari alamat	$O(n)$, harus berjalan dari head
Sisip/hapus di depan	$O(n)$, geser semua	$O(1)$, ubah head
Sisip/hapus di tengah (posisi diketahui)	$O(n)$	$O(1)$ setelah sampai di posisinya
Ukuran	tetap (atau realokasi)	dinamis, tumbuh per node
Memori tambahan	tidak ada	1 pointer per node

Operasi dasar

Kunci memahami linked list: gambar kotak dan panahnya, lalu tentukan urutan perubahan pointer yang benar.

Singly linked list▶ Jalankan

Varian

• Doubly linked list: tiap node punya prev dan next. Hapus node yang sudah dipegang jadi $O(1)$ tanpa mencari node sebelumnya, dengan biaya satu pointer tambahan per node.
• Circular linked list: node terakhir menunjuk kembali ke head. Cocok untuk round-robin.
• Dengan dummy/sentinel head: node palsu di depan supaya insert/delete di awal tidak perlu kasus khusus.

Teknik dua pointer

Banyak soal linked list diselesaikan dengan dua pointer yang bergerak dengan kecepatan berbeda:

• Tengah list: slow maju 1, fast maju 2. Saat fast sampai ujung, slow ada di tengah.
• Deteksi siklus (Floyd): jika ada siklus, fast pasti akan “menyusul” slow.

Flashcard0/4 dikuasai

PertanyaanKompleksitas akses elemen ke-i pada linked list?

Lihat jawaban

Latihan: Reverse Linked List, Middle of Linked List, Gabung Dua List Terurut.