שיעור 0: למה בחירת מבנה הנתונים בכלל משנה?

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

לבחור מבנה נתונים זה כמו לבחור בין לחפש שם בספר טלפונים מבולגן לבין לחפש אותו בספר מסודר לפי א'-ב' — אותו מידע בדיוק, מהירות שונה בתכלית.

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