Linked lists · Daftar terhubung (Linked lists)
Nodes joined by pointers
- A linked list is a chain of small structs called nodes, scattered around the heap.
- Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
- Unlike an array, a list can grow one node at a time without moving the others.
Node yang terhubung oleh pointer
- Daftar terikat adalah rantai dari struktur kecil yang disebut node, tersebar di area heap.
- Setiap node menyimpan nilai dan pointer ke node berikutnya. Ikuti pointer untuk menjelajahi daftar.
- Berbeda dengan array, daftar dapat bertambah satu node pada satu waktu tanpa memindahkan node lainnya.
A self-referential struct
- A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; };—datais the value,nextpoints to the following node.- This is given for you as
Nodein each starter. The last node'snextisNULL.
Struktur self-referensial
- Node adalah struktur yang berisi pointer ke tipe dirinya sendiri:
struct Node { int data; struct Node *next; };—dataadalah nilainya,nextmenunjuk ke node berikutnya.- Ini disediakan untuk Anda sebagai
Nodedalam setiap starter.nextdari node terakhir adalahNULL.
head and the NULL end
- A single pointer, the head, points to the first node. From there you reach the rest.
- The very last node points to
NULL, which marks the end of the list. - An empty list is just
head == NULL— there are no nodes at all.
head dan akhir NULL
- Satu pointer tunggal, head, menunjuk ke node pertama. Dari sana Anda dapat menjangkau sisanya.
- Node paling akhir menunjuk ke
NULL, yang menandai akhir dari daftar. - Daftar kosong hanyalah
head == NULL— sama sekali tidak ada node.
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
Adding a node at the front
- To add to the front, make a new node, point its
nextat the old head, and return the new node as the new head. - This is fast — it does not touch any other node.
- Because the head changes, the function returns the new head, and the caller saves it.
Menambahkan node di bagian depan
- Untuk menambahkan di bagian depan, buatlah node baru, arahkan
next-nya ke head lama, dan kembalikan node baru tersebut sebagai head baru. - Ini cepat — tidak menyentuh node lain apa pun.
- Karena head berubah, fungsi mengembalikan head baru, dan pemanggil menyimpannya.
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - Free every node; the last node points to
NULL.
Kesalahan umum
- Jangan pernah kehilangan pointer
head, atau seluruh daftar tidak akan bisa dijangkau. - Bebaskan setiap node; node terakhir menunjuk ke
NULL.
Now you try
- Walk a list with a
curpointer andcur = cur->next, stopping atNULL. - New nodes come from
malloc(sizeof(Node)); the checker frees the list. Do not write amain.
Sekarang Anda coba
- Jelajahi daftar dengan pointer
curdancur = cur->next, berhenti saat bertemuNULL. - Node baru berasal dari
malloc(sizeof(Node)); pengecek akan membebaskan daftar. Jangan tulismain.
Nodes and pointers · Node dan pointer
Each node points to the next; insert/delete by re-linking. · Setiap node menunjuk ke node berikutnya; sisipkan/hapus dengan menghubungkan ulang.
Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do not write a main. · Lengkapi int length(const Node *head) agar menghitung jumlah node dalam daftar (0 untuk daftar kosong). Jelajahi dengan ->next sampai NULL. Tipe Node telah disediakan. Jangan tulis kode main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do not write a main. · Lengkapi int sum_list(const Node *head) agar mengembalikan total dari setiap nilai data node (0 untuk daftar kosong). Tipe Node telah disediakan. Jangan tulis kode main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.
Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do not write a main. · Lengkapi Node *push_front(Node *head, int value) agar membuat node baru (dengan malloc), mengarahkan next-nya ke node lama head, dan mengembalikannya sebagai head baru. Pengecek akan membebaskan seluruh daftar. Jangan tulis fungsi main.
Click Run to see the output here. · Klik Jalankan untuk melihat output di sini.