מערך - הכנסה ומחיקה

מכיוון שמערך מחזיק את כל איבריו ברצף, בכל פעם שנרצה למחוק איבר, נצטרך לאחר מציאת האיבר, "לדחוף" את כל האיברים שאחריו, מקום אחד אחורה. דבר שיעלה כמובן (O(N מכיוון שבמקרה הגרוע ביותר נצטרך למחוק את הראשון, ואז להזיז את כל שאר האיברים. עם זאת, במימוש כזה של מחיקה, עבור מערך לא ממוין נוכל לממש הכנסת איבר בצורה מיידית: פשוט לשמור את כמות האיברים במערך, לגשת למקום הבא ולהכניס לשם את האיבר.

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

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

דוגמאות קוד

דוגמאות אלה מניחות שהמערך לא ממוין. הוספה לוקחת (O(1 ומחיקה לוקחת (O(n.

function add(Ar, x)
  Ar[length(Ar)+1] <-- x
  length(Ar) <-- length(Ar)+1

function delete(Ar, x)
  for i=1 to length(Ar)
    if Ar[i]==x
       for j=i to length(Ar)-1
         Ar[j] <-- Ar[j+1]
       length(Ar) <-- length(Ar)-1
       return