Daftar terhubung (Linked lists)
Node terhubung oleh link
- Linked list adalah rantai node.
- Setiap node menyimpan sepotong data dan link ke node berikutnya.
- Node terakhir linking ke
None, yang menandai akhir.
Node adalah record kecil
- Kita dapat menyimpan satu node dalam dictionary:
{"data": ..., "next": ...}. "data"menyimpan nilainya;"next"menyimpan node berikutnya (atauNone).- Node pertama disebut head dari list.
second = {"data": "b", "next": None}
first = {"data": "a", "next": second}
print(first["data"])
print(first["next"]["data"])
Walk the list
- Mulai dari head dan ikuti setiap link
"next". - Berhenti ketika Anda mencapai
None. - Pengunjung setiap node ini disebut traversal.
head = {"data": 1, "next": {"data": 2, "next": None}}
node = head
while node is not None:
print(node["data"])
node = node["next"]
Mengapa linked list?
- Anda dapat menyisipkan atau menghapus node dengan mengubah link — tanpa menggeser item.
- Array harus memindahkan setiap item setelah perubahan.
- Namun linked list tidak memiliki indeks: untuk mencapai item ke-5, Anda harus berjalan dari kepala.
Dalam pseudocode Cambridge
- Ujian menyimpan node dalam array;
NextIndexadalah indeks node berikutnya, danNULLmenandai akhir.
TYPE Node
DECLARE Data : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].NextIndex
ENDWHILE
Kesalahan umum
- Jangan pernah kehilangan pointer
head, atau seluruh daftar tidak akan bisa dijangkau. - Node terakhir menunjuk ke
None.
Sekarang Anda coba
- Node adalah dict
{"data": ..., "next": ...}. Ikuti"next"untuk menelusuri rantai. - Tekan Periksa jawaban untuk menguji kode Anda.
Nodes linked by pointers
Each node points to the next; you insert/delete by re-linking.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Build a linked list 1 → 2 → 3 using dictionaries. Make the three nodes, link each to the next, and point head at the first one. The last node's "next" must be None.
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60).
Klik Jalankan untuk melihat output di sini.
Kesulitan 4/5 · 280 koin + bonus kecil pada penyelesaian pertama hari ini
Write length(head) that returns how many nodes are in the linked list. An empty list (head adalah None) has length 0.
Klik Jalankan untuk melihat output di sini.