Linked lists · Daftar terhubung (Linked lists)
Nodes joined by links
- A linked list is a chain of nodes.
- Each node holds a piece of data and a link to the next node.
- The last node links to
None, which marks the end.
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.
A node is a small record
- We can store one node in a dictionary:
{"data": ..., "next": ...}. "data"holds the value;"next"holds the next node (orNone).- The first node is called the head of the list.
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
- Start at the head and follow each
"next"link. - Stop when you reach
None. - This visiting of every node is called traversal.
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"]
Why a linked list?
- You can insert or remove a node by changing links — no shifting of items.
- An array would have to move every item after the change.
- But a linked list has no index: to reach item 5 you must walk from the head.
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.
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
Dalam pseudocode Cambridge
- Ujian menyimpan node dalam array;
Nextadalah indeks node berikutnya, danNULLmenandai akhir.
TYPE Node
DECLARE Data : INTEGER
DECLARE Next : INTEGER // index of the next node, or NULL
ENDTYPE
current ← head
WHILE current <> NULL
OUTPUT list[current].Data
current ← list[current].Next
ENDWHILE
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - The last node points to
None.
Kesalahan umum
- Jangan pernah kehilangan pointer
head, atau seluruh daftar tidak akan bisa dijangkau. - Node terakhir menunjuk ke
None.
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
Sekarang Anda coba
- Node adalah dict
{"data": ..., "next": ...}. Ikuti"next"untuk menelusuri rantai. - Tekan Periksa jawaban untuk menguji kode Anda.
Nodes linked by pointers · Node yang dihubungkan oleh pointer
Each node points to the next; you insert/delete by re-linking. · Setiap node menunjuk ke node berikutnya; Anda menyisipkan/menghapus dengan menghubungkan ulang.
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. · Bangun linked list 1 → 2 → 3 menggunakan dictionary. Buat tiga node, hubungkan masing-masing ke berikutnya, dan tunjuk head ke node pertama. Nilai "next" pada node terakhir harus None.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · Jelajahi linked list dimulai dari head dan jumlahkan nilai "data" dari setiap node. Simpan totalnya dalam total (jawabannya adalah 60).
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Write length(head) that returns how many nodes are in the linked list. An empty list (head is None) has length 0. · Tulis length(head) yang mengembalikan berapa banyak simpul dalam daftar terhubung. Daftar kosong (head adalah None) memiliki panjang 0.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.