Kelas Node dan Pembuatan List
Definisikan dataclass Node, bangun list dengan menghubungkan node secara manual, lalu tulis fungsi pembantu insert/delete/print untuk memvisualisasikan perubahan pointer.
Kelas Node dan Pembuatan List adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa Itu Daftar Tertaut
Daftar tertaut adalah urutan simpul yang setiap simpulnya menyimpan nilai dan penunjuk ke simpul berikutnya. Berbeda dengan larik, simpul tersebar di memori—tidak ada akses O(1) berbasis indeks. Sebagai gantinya, Anda memperoleh penyisipan dan penghapusan O(1) pada posisi mana pun yang diketahui tanpa menggeser elemen.
Dalam Python, setiap simpul direpresentasikan dengan kelas kecil yang menyimpan val dan next. Menghubungkan simpul-simpul tersebut membentuk daftar; next pada simpul terakhir adalah None untuk menandai akhir.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')Membangun Daftar dari Larik
Dalam wawancara, Anda akan sering diberi sebuah daftar dan diminta membuat padanan daftar tertautnya, atau sebaliknya. Fungsi pembantu build dan to_list layak dihafalkan: build menghubungkan simpul-simpul dari sebuah larik, sedangkan to_list menelusuri daftar untuk mengumpulkan nilai agar mudah diverifikasi.
Membangun daftar tertaut dari n elemen memerlukan waktu O(n) dan ruang O(n). Menggunakan simpul kepala semu menyederhanakan kasus batas ketika simpul pertama dapat berubah.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]Menyisipkan di Kepala dan Ekor
Menyisipkan simpul baru di kepala memerlukan O(1): buat simpul tersebut, arahkan next-nya ke kepala lama, lalu kembalikan simpul baru sebagai kepala. Menyisipkan di tail memerlukan penelusuran ke simpul terakhir (O(n)), lalu menghubungkan simpul baru.
Menggunakan simpul kepala semu menghilangkan kasus khusus daftar kosong untuk kedua penyisipan, karena dummy.next selalu menunjuk ke kepala sebenarnya.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> NoneMenghapus Simpul Berdasarkan Nilai
Untuk menghapus simpul pertama dengan nilai tertentu, pertahankan penunjuk prev satu langkah di belakang curr. Ketika curr.val == target, tetapkan prev.next = curr.next untuk melewati simpul tersebut. Kepala semu sangat membantu di sini karena menghilangkan kasus khusus saat menghapus simpul kepala sebenarnya—prev selalu dapat dimulai dari simpul semu.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))Memvisualisasikan Perubahan Penunjuk
Kesalahan umum adalah kehilangan jejak sebuah simpul saat memperbarui penunjuk. Selalu simpan next sebelum menimpanya: saved = curr.next, lalu tetapkan ulang. Gambarkan daftar sebagai kotak-kotak yang dihubungkan oleh panah dan simulasikan setiap pembaruan penunjuk di atas kertas sebelum menulis kode. Pendekatan visual ini mencegah kesalahan penunjuk kosong yang tidak disengaja selama wawancara.
Ingat: dalam Python, menetapkan ulang curr.next tidak memengaruhi curr itu sendiri, tetapi kehilangan referensi ke curr.next sebelum menyimpannya berarti Anda tidak dapat lagi menelusuri daftar ke depan.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4Daftar Tertaut Tunggal vs Ganda
Daftar tertaut tunggal hanya menyimpan penunjuk next; penelusurannya berlangsung satu arah. Daftar tertaut ganda menyimpan prev dan next, sehingga memungkinkan penelusuran mundur O(1) dan penghapusan O(1) jika referensi langsung ke simpul tersedia (tidak perlu melakukan perulangan sambil melacak prev).
collections.deque milik Python diimplementasikan sebagai daftar tertaut ganda, sehingga mendukung appendleft dan popleft dalam O(1). Dalam wawancara, Anda akan mengimplementasikan daftar tertaut tunggal; daftar tertaut ganda muncul dalam perancangan tembolok LRU.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')Panjang, Ekor, dan Fungsi Pembantu Pencetakan
Tiga fungsi utilitas yang sebaiknya Anda siapkan untuk setiap wawancara tentang daftar tertaut: length(head) menghitung simpul dalam O(n), tail(head) mengembalikan simpul terakhir dalam O(n), dan print_list(head) memformat daftar untuk penelusuran kesalahan. Dengan fungsi-fungsi ini, Anda dapat berfokus pada algoritme inti, bukan menulis ulang logika pembantu.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)Menyiapkan Dua Penunjuk pada Daftar Tertaut
Teknik dua penunjuk sama pentingnya untuk daftar tertaut seperti untuk larik, tetapi penunjuknya berupa simpul daftar tertaut, bukan indeks. Pengaturan yang umum mencakup penunjuk lambat dan cepat (penunjuk cepat bergerak 2x lebih cepat) untuk menemukan titik tengah dan mendeteksi siklus, serta pasangan pendahulu dan saat ini untuk penghapusan dan pembalikan.
Selalu inisialisasikan kedua penunjuk secara eksplisit dan tangani pemeriksaan penghentian kosong dengan hati-hati—fast and fast.next mencegah kesalahan penunjuk kosong ketika penunjuk cepat mendekati akhir.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)Pola Kepala Semu
Pola kepala semu (simpul penjaga) adalah salah satu trik yang paling berguna dalam masalah daftar tertaut. Dengan menambahkan simpul semu bernilai 0 di depan, Anda tidak perlu lagi menangani kasus khusus untuk daftar kosong atau perubahan pada kepala sebenarnya. Hasil Anda selalu berupa dummy.next. Pola ini muncul dalam penggabungan daftar terurut, penghapusan elemen ke-n dari akhir, pemartisian daftar, dan banyak masalah lainnya.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]Kompleksitas Waktu dan Ruang
Sebagian besar operasi daftar tertaut memiliki kompleksitas berikut. Akses berdasarkan indeks: O(n)—harus menelusuri dari kepala. Penyisipan/penghapusan pada simpul yang diketahui: O(1)—cukup menyambungkan ulang penunjuk. Penyisipan/penghapusan pada posisi k: O(k)—lakukan penelusuran terlebih dahulu. Pencarian: O(n)—dalam kasus terburuk, seluruh daftar harus ditelusuri. Ruangnya adalah O(1) untuk semua operasi langsung di tempat (tidak termasuk struktur data tambahan).
Bandingkan dengan larik: larik menyediakan akses O(1), tetapi penyisipan/penghapusan O(n) karena elemen harus digeser. Daftar tertaut lebih baik jika penyisipan dan penghapusan pada posisi sembarang sering dilakukan.
Kiat Wawancara tentang Daftar Tertaut
Sebelum menulis kode daftar tertaut, gambarkan daftar secara visual dengan kotak dan panah. Sampaikan dan pastikan kasus batas: daftar kosong, satu simpul, serta panjang genap dan ganjil. Gunakan kepala semu untuk menyederhanakan kondisi batas. Selalu periksa if not head di awal. Setelah menulis kode, telusuri solusi Anda pada daftar tiga simpul untuk menemukan kesalahan penunjuk sebelum pewawancara menemukannya.
Sebagian besar kesalahan daftar tertaut berasal dari salah satu dari tiga sumber: lupa menyimpan next sebelum menimpanya, kesalahan satu langkah pada kondisi penghentian, atau tidak menangani kasus batas perubahan kepala—simpul semu menghilangkan sumber kesalahan ketiga sepenuhnya.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari: daftar tertaut dibangun dari objek simpul dengan kolom nilai dan penunjuk berikutnya, pola kepala semu menghilangkan kasus batas perubahan kepala, serta pengaturan dua penunjuk lambat-cepat menjadi dasar untuk menemukan titik tengah dan mendeteksi siklus. Selanjutnya kita akan membahas pembalikan daftar tertaut—salah satu masalah penunjuk yang paling sering ditanyakan.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Kelas Node dan Pembuatan List” gratis?
Ya — teks lengkap “Kelas Node dan Pembuatan List” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Kelas Node dan Pembuatan List”?
Definisikan dataclass Node, bangun list dengan menghubungkan node secara manual, lalu tulis fungsi pembantu insert/delete/print untuk memvisualisasikan perubahan pointer. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Kelas Node dan Pembuatan List” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Kelas Node dan Pembuatan List
- Membalik Linked List
- Deteksi Siklus dengan Algoritma Floyd
- Menggabungkan, Memisahkan, dan Menemukan Elemen ke-N dari Akhir