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.
צמתים מחוברים בקישורים
- רשימה מקושרת היא שרשרת של צמתים.
- כל צומח מחזיק חלקי נתונים וקישור לצומח הבא.
- הצומח האחרון מצביע על
None, המסמן את הסוף.
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.
צומח הוא רשומה קטנה
- ניתן לאחסן צומח אחד במילון:
{"data": ..., "next": ...}. "data"מכיל את הערך;"next"מכיל את הצומח הבא (אוNone).- הצומח הראשון נקרא ראש הרשימה.
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.
הליכה ברשימה
- מתחילים בראש ועוקבים אחר כל קישור
"next". - עצרים כאשר מגיעים ל-
None. - הביקור בכל צומח נקרא מעבר (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.
מדוע רשימה מקושרת?
- ניתן להכניס או להסיר צומח על ידי שינוי קישורים — ללא הזזת פריטים.
- מערך היה צריך להזיז כל פריט לאחר השינוי.
- אך לרשימה מקושרת אין אינדקס: כדי להגיע לפריט 5 יש לעבור מהראש.
In Cambridge pseudocode
- The exam stores nodes in an array;
Nextis the index of the next node, andNULLmarks the end.
בפסאודוקוד קמברידג'
- במבחן הצמתים מאוחסנים במערך;
Nextהוא האינדקס של הצומח הבא, ו-NULLמסמן את הסוף.
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.
טעויות נפוצות
- לעולם לא לאבד את רמז ה-
head,否则 כל הרשימה תהיה בלתי נגישה. - הצומח האחרון מצביע על
None.
Now you try
- A node is a dict
{"data": ..., "next": ...}. Follow"next"to walk the chain. - Press Check answer to test your code.
כעת תנסו בעצמכם
- צומח הוא dict
{"data": ..., "next": ...}. עקבו אחרי"next"כדי לעבור בשרשרת. - לחץ על בדוק תשובה כדי לבדוק את הקוד שלך.
Nodes linked by pointers · צמתים מקושרים על ידי מצביעים
Each node points to the next; you insert/delete by re-linking. · כל צומת מצביע על הבא; מציאים/מוחקים על ידי קישור מחדש.
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. · בנה רשימה מקשרת 1 → 2 → 3 באמצעות מילונים. צור שלושת הצמתים, קשר כל אחד לבא, והצבע head על הראשון. ה-"next" של הצומת האחרון חייב להיות None.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Walk the linked list starting at head and add up every node's "data". Store the total in total (the answer is 60). · הלך ברשימה המקשרת החל מ-head וחבר את כל ה-"data" של כל צומת. שמור את הסכום ב-total (התשובה היא 60).
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.
Write length(head) that returns how many nodes are in the linked list. An empty list (head is None) has length 0. · כתוב פונקציה length(head) שמחזירה כמה צמתים יש ברשימה המקשרת. רשימה ריקה (head היא None) אורך שלה 0.
Click Run to see the output here. · לחץ על הרץ כדי לראות את התוצא כאן.