רשימה מקושרת - הכנסת איבר

כדי להכניס איבר כל שיש לעשות הוא לשנות את המצביע של איבר הדמה head, כך שיצביע עליו, שהוא יצביע על האיבר שעליו הצביע קודם הhead, ולאחר מכן למחוק את המצביע בין הhead, לאיבר שקודם היה הראשון. יש לשים לב לסדר הפעולות, שכן מחיקת המצביע הישן לפני הוספת המצביעים החדשים, תגרום לכך שלא ניתן יהיה להגיע יותר לשאר האיברים ברשימה.

אם נרצה לשמור על רשימה ממוינת, יהיה עלינו למצוא קודם את המקום אליו נרצה להכניס. לאחר מכן נשנה שוב את המצביעים באותה הדרך, כשאת מקום איבר הדמה ימלא האיבר שצריך להיות לפני האיבר החדש.

ההכנסה עצמה עולה (O(1, מכיוון שמדובר בשינוי מספר קבוע של מצביעים, מובן שברשימה ממוינת תעלה ההכנסה (O(N מכיוון שיש לבצע חיפוש שעולה (O(N.

הקש כאן כדי לקבל תצוגה גרפית.

דוגמת קוד

function insert(node, new_data)
  new_node <-- CreateNode()
  new_node.next <-- node.next
  new_node.data <-- new_data
  node.next <-- new_node