רשימה מקושרת - מחיקת איבר

ברשימה מקושרת כדי למחוק איבר יש:

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

הקש כאן כדי לראות תצוגה ויזואלית של מחיקת איבר

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

סיבוכיות

הסיבוכיות של שלב 1 היא (O(N (ראה סיבוכיות מציאת איבר). ושל שלב 2 היא קבועה, ולכן סך-כל הסיבוכיות של מחיקת איבר ברשימה מקושרת היא (O(N.

אם הרשימה היא דו-כיוונית, ניתן לצמוא את האיבר הקודם בזמן (O(1 ע"י המצביע אליו, ולכן זמן המחיקה הוא (O(1.

דוגמת קוד

function ll_delete(node)
  node.prev.next <-- node.next
  node.next.prev <-- node.prev
  FreeMemory(node)