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.
צמתים המחוברים באמצעות נורמלים
- רשימה מקושרת היא שרשרת של מבני נתונים קטנים הנקראים צמתים, מפוזרים בכל הזיכרון.
- כל צומח מחזיק ערך ו-נורמל לצומח הבא. עקוב אחרי הנורמלים כדי לעבור על הרשימה.
- בניגוד למערך, רשימה יכולה להתרחב צומח אחד בכל פעם ללא העברת האחרים.
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.
מבנה נתונים המתייחס לעצמו
- צומח הוא מבנה נתונים המכיל נורמל ל-סוג שלו:
struct Node { int data; struct Node *next; };—dataהוא הערך,nextמצביע לצומח הבא.- זה נתון לך כ-
Nodeבכל קובץ התחלתי. ה-nextשל הצומת האחרון הוא ⟨NULL⟩.
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.
ראש הסוף NULL
- נורמל אחד, ה-ראש, מצביע לצומח הראשון. ממנו מגיעים לשאר.
- הצומח האחרון מצביע ל-
NULL, שמסמן את סוף הרשימה. - רשימה ריקה היא פשוט ⟨
head == NULL⟩ — אין כלל צומתים.
#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.
הוספת צומח בהתחלה
- להוספה בראש, צור נוד (צומת) חדש, נקד את
nextשלו לראש הקיים, והחזר את הנוד החדש כראש החדש. - פעולה זו מהירה — היא אינה פוגעת בשום נוד אחר.
- מכיוון שהראש משתנה, הפונקציה מחזירה את הראש החדש, והקורא שומר אותו.
Common mistakes
- Never lose the
headpointer, or the whole list is unreachable. - Free every node; the last node points to
NULL.
טעויות נפוצות
- לעולם לא לאבד את רמז ה-
head,否则 כל הרשימה תהיה בלתי נגישה. - שחרר כל נוד; הנוד האחרון מצביע על
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.
כעת תנסו בעצמכם
- עבור ברשימה עם מייצג ⟨
cur⟩ ונכונה ⟨cur = cur->next⟩, ועצור בNULL. - נודים חדשים מגיעים מ
malloc(sizeof(Node)); הבוחן משחרר את הרשימה. אל תכתובmain.
Nodes and pointers · נודים ומצביעים
Each node points to the next; insert/delete by re-linking. · כל נוד מופנה לנוד הבא; הוספה/מחיקה מתבצעת על ידי שינוי הקישורים.
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. · השלם את int length(const Node *head) כדי לספור את הנודים ברשימה (0 עבור רשימה ריקה). צלול עם ->next עד ש-NULL. סוג ה-Node נתון. אל תכתוב פונקציית main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
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. · השלם את int sum_list(const Node *head) כדי להחזיר את הסך הכל של כל ה-data של כל נוד (0 עבור רשימה ריקה). סוג ה-Node נתון. אל תכתוב פונקציית main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
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. · השלם את Node *push_front(Node *head, int value) כדי ליצור נוד חדש (עם malloc), להפנות את ה-next שלו ל-head הישן, ולהחזירו כראש חדש. הבוקר ישחרר את הרשימה. אל תכתוב פונקציית main.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.