Daftar terhubung (Linked lists)
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.
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 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;
}
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.
Kesalahan umum
- Jangan pernah kehilangan pointer
head, atau seluruh daftar tidak akan bisa dijangkau. - Bebaskan setiap node; node terakhir menunjuk ke
NULL.
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
Each node points to the next; insert/delete by re-linking.
Kesulitan 5/5 · 400 koin + bonus kecil pada penyelesaian pertama hari ini
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 tidak write a main.
Klik Jalankan untuk melihat output di sini.
Kesulitan 5/5 · 400 koin + bonus kecil pada penyelesaian pertama hari ini
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 tidak write a main.
Klik Jalankan untuk melihat output di sini.
Kesulitan 5/5 · 400 koin + bonus kecil pada penyelesaian pertama hari ini
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 tidak write a main.
Klik Jalankan untuk melihat output di sini.