ลิงค์ลิสต์ (Linked lists)
โหนดที่เชื่อมต่อกันด้วย pointer
- ลิงค์ลิสต์คือโซ่ของ struct เล็กๆ ที่เรียกว่า โหนด, กระจายอยู่ในฮีป
- แต่ละ node มีค่าและ pointer ไปยัง node ถัดไป ตาม pointer เพื่อเดินผ่าน list
- ต่างจาก array, list สามารถขยายได้ทีละ node โดยไม่ต้องย้ายตัวอื่น
Struct ที่อ้างอิงถึงตัวเอง
- Node คือ struct ที่มีพอยเตอร์ไปยัง ประเภทของตัวเอง:
struct Node { int data; struct Node *next; };—dataคือค่า,nextชี้ไปยัง node ถัดไป- นี่คือสิ่งที่ให้ไว้สำหรับคุณใน
Nodeในแต่ละ starter Nodeสุดท้ายมีnextเป็นNULL
head และจุดสิ้นสุด NULL
- Pointer เดียว, head, ชี้ไปยัง node แรก จากนั้นคุณสามารถเข้าถึงส่วนที่เหลือ
- Nodeสุดท้ายชี้ไปยัง
NULLซึ่งแสดงถึงจุดสิ้นสุดของ list - Listว่างคือแค่
head == NULL— ไม่มี 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;
}
การเพิ่ม node ที่ด้านหน้า
- เพื่อเพิ่มที่ด้านหน้า ให้สร้าง nodeใหม่ ชี้
nextของมันไปที่ headเก่า, และคืนค่า nodeใหม่เป็น headใหม่ - สิ่งนี้รวดเร็ว — ไม่สัมผัส node อื่นเลย
- เนื่องจาก head เปลี่ยน, ฟังก์ชัน คืนค่า headใหม่, และผู้เรียกบันทึกมัน
ข้อผิดพลาดที่พบบ่อย
- อย่าลืมชี้ที่
headเพราะถ้าจะหาทั้งลิงค์ลิสต์ไม่เจอเลย - Free ทุก node; nodeสุดท้ายชี้ไปยัง
NULL
ลองดูเลย
- เดินผ่านลิสต์ด้วยชี้ชี้
curและcur = cur->next, หยุดที่NULL - Nodeใหม่มาจาก
malloc(sizeof(Node)); ตัวตรวจสอบจะ free list. อย่า เขียนmain
Nodes และ pointers
แต่ละ node ชี้ไปยังตัวถัดไป Insert/delete โดยการเชื่อมใหม่
ความยาก 5/5 · 400 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม int length(const Node *head) นับจำนวน node ใน list (0 สำหรับ list ว่าง) Walk ด้วย ->next จนกว่าจะเจอ NULL Node type ให้มา ห้าม เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 5/5 · 400 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม int sum_list(const Node *head) เพื่อคืนผลรวมของ data ในทุกโหนด (0 สำหรับรายการว่าง). Node type ถูกกำหนดให้แล้ว. ห้าม เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 5/5 · 400 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม Node *push_front(Node *head, int value) เพื่อสร้างโหนดใหม่ (ด้วย malloc), ชี้ next ของมันไปยัง head เก่า, และคืนมันในฐานะหัวใหม่. ตัวตรวจสอบจะปล่อยรายการ. ห้าม เขียน main
คลิก Run เพื่อดูผลลัพธ์ที่นี่