ברוכים הבאים ליחידת הלימוד "מבני נתונים בסיסיים", המהווה אבן יסוד בקורס "מבני נתונים ומבוא לאלגוריתמים" (20407). יחידה זו תציג בפניכם את מבני הנתונים הלינאריים הנפוצים ביותר, עקרונות פעולתם, שימושיהם, והכי חשוב – כיצד לבחור את המבנה המתאים ביותר לבעיה נתונה תוך התחשבות בסיבוכיות זמן וזיכרון. הבנה מעמיקה של נושאים אלו חיונית להצלחה בקורס ובפיתוח תוכנה בכלל, והיא מהווה בסיס לשאלות רבות במבחן.
מבוא למבני נתונים לינאריים
מבני נתונים הם דרכים לארגון נתונים בזיכרון המחשב, באופן המאפשר גישה יעילה וביצוע פעולות שונות עליהם. מבני נתונים לינאריים מאופיינים בכך שהאיברים מסודרים ברצף, כאשר לכל איבר (למעט הראשון והאחרון) יש "קודם" ו"עוקב" יחידים. הבנת מבנים אלו היא קריטית ליכולתכם לכתוב קוד יעיל ואופטימלי.
מערכים (Arrays)
מערך הוא מבנה הנתונים הלינארי הבסיסי ביותר. הוא מאפשר אחסון אוסף של איברים מאותו טיפוס בזיכרון רציף. גישה לאיבר במערך מתבצעת באמצעות אינדקס (מיקום), והיא מהירה ויעילה במיוחד.
מאפיינים ופעולות
- אחסון רציף: האיברים מאוחסנים בבלוק זיכרון אחד ורציף.
- גישה ישירה (Random Access): גישה לאיבר לפי אינדקס היא בסיבוכיות זמן O(1).
- גודל קבוע: ברוב השפות, גודל המערך נקבע בזמן יצירתו ואינו ניתן לשינוי בקלות.
- הכנסה/מחיקה: הכנסה או מחיקה של איבר באמצע המערך דורשת הזזה של כל האיברים שאחריו, ולכן היא בסיבוכיות זמן O(N). הכנסה/מחיקה בסוף (אם יש מקום) היא O(1).
רשימות מקושרות (Linked Lists)
רשימה מקושרת היא מבנה נתונים לינארי גמיש יותר ממערך, שבו האיברים אינם מאוחסנים בזיכרון רציף. במקום זאת, כל איבר (צומת) מכיל את הנתון עצמו ומצביע (reference) לאיבר הבא ברשימה.
סוגי רשימות מקושרות
- רשימה מקושרת חד-כיוונית (Singly Linked List): כל צומת מצביע רק לצומת הבא.
- רשימה מקושרת דו-כיוונית (Doubly Linked List): כל צומת מצביע גם לצומת הבא וגם לצומת הקודם, מה שמאפשר תנועה בשני הכיוונים.
מאפיינים ופעולות
- אחסון לא רציף: האיברים מפוזרים בזיכרון, מקושרים באמצעות מצביעים.
- גודל דינמי: ניתן להגדיל או להקטין את הרשימה בקלות.
- גישה סדרתית (Sequential Access): גישה לאיבר דורשת מעבר על הרשימה מההתחלה, ולכן היא בסיבוכיות זמן O(N).
- הכנסה/מחיקה: הכנסה או מחיקה של איבר (בהינתן מצביע לצומת הקודם) היא בסיבוכיות זמן O(1).
מערך
יתרונות: גישה ישירה O(1), ניצול זיכרון טוב יותר (ללא תקורה של מצביעים).
חסרונות: גודל קבוע, הכנסה/מחיקה באמצע O(N), דורש זיכרון רציף.
שימושים: אחסון נתונים בגודל ידוע מראש, גישה מהירה לפי אינדקס.
רשימה מקושרת
יתרונות: גודל דינמי, הכנסה/מחיקה מהירה O(1) (בהינתן מצביע), לא דורש זיכרון רציף.
חסרונות: גישה סדרתית O(N), תקורה של זיכרון עבור מצביעים.
שימושים: תורים, מחסניות, כאשר יש צורך בהכנסה/מחיקה תכופה.
מחסניות ותורים (Stacks and Queues)
מחסניות ותורים הם מבני נתונים לינאריים מופשטים (Abstract Data Types - ADT) המגדירים ממשק פעולות ספציפי, ללא התייחסות לאופן המימוש הפנימי. ניתן לממש אותם באמצעות מערכים או רשימות מקושרות, כאשר לכל מימוש יש יתרונות וחסרונות מבחינת סיבוכיות.
מחסנית (Stack)
מחסנית פועלת על פי העיקרון LIFO (Last-In, First-Out) – האחרון שנכנס הוא הראשון שיוצא. דמיינו ערימת צלחות: תמיד לוקחים את העליונה, ותמיד מניחים צלחת חדשה על העליונה.
- Push: הוספת איבר לראש המחסנית (O(1)).
- Pop: הסרת איבר מראש המחסנית והחזרתו (O(1)).
- Peek/Top: הצגת האיבר בראש המחסנית מבלי להסירו (O(1)).
- IsEmpty: בדיקה האם המחסנית ריקה (O(1)).
תור (Queue)
תור פועל על פי העיקרון FIFO (First-In, First-Out) – הראשון שנכנס הוא הראשון שיוצא. דמיינו תור לקופה בסופר: הראשון שהגיע הוא הראשון שמקבל שירות.
- Enqueue: הוספת איבר לסוף התור (O(1)).
- Dequeue: הסרת איבר מתחילת התור והחזרתו (O(1)).
- Peek/Front: הצגת האיבר בתחילת התור מבלי להסירו (O(1)).
- IsEmpty: בדיקה האם התור ריק (O(1)).
מחסנית
עקרון: LIFO (Last-In, First-Out).
פעולות עיקריות: Push (הכנסה), Pop (הוצאה).
שימושים: ניהול קריאות לפונקציות (Call Stack), ביטול פעולות (Undo), הערכת ביטויים חשבוניים.
תור
עקרון: FIFO (First-In, First-Out).
פעולות עיקריות: Enqueue (הכנסה), Dequeue (הוצאה).
שימושים: ניהול משימות במערכת הפעלה, הדפסה, BFS (חיפוש לרוחב) בגרפים.
שאלות לדיון
- כיצד ניתן לממש מחסנית באמצעות מערך? מהם היתרונות והחסרונות של מימוש כזה לעומת מימוש באמצעות רשימה מקושרת?
- תארו מצב שבו רשימה מקושרת דו-כיוונית תהיה עדיפה על רשימה מקושרת חד-כיוונית, ונמקו.
- כיצד הייתם בוחרים בין מערך לרשימה מקושרת אם הייתם צריכים לאחסן רשימת לקוחות, כאשר ידוע שיהיו הרבה פעולות של הוספה ומחיקה של לקוחות, אך מעט חיפושים ספציפיים?
- הסבירו את חשיבות עקרונות LIFO ו-FIFO בפתרון בעיות תכנותיות יומיומיות, ותנו דוגמה לכל אחד.
נקודות לתשובת מודל
- מימוש מחסנית:
- מערך: איבר חדש מוכנס לסוף המערך, ראש המחסנית הוא האיבר האחרון. דורש מעקב אחר "ראש" המחסנית (אינדקס). יתרון: גישה מהירה. חיסרון: גודל קבוע, דורש שינוי גודל מערך (O(N)) אם מתמלא.
- רשימה מקושרת: איבר חדש מוכנס לתחילת הרשימה (ראש המחסנית הוא ראש הרשימה). יתרון: גודל דינמי, O(1) לכל פעולה. חיסרון: תקורה של זיכרון עבור מצביעים.
- רשימה דו-כיוונית: עדיפה כאשר יש צורך לנוע אחורה ברשימה (למשל, במערכת Undo/Redo, או כאשר יש צורך למחוק צומת בהינתן רק המצביע אליו). החיסרון הוא תקורה נוספת של זיכרון עבור המצביע הנוסף.
- בחירת מבנה ללקוחות: רשימה מקושרת תהיה עדיפה. הוספה ומחיקה של לקוחות (בהינתן מצביע ללקוח הקודם/הבא) הן פעולות O(1) ברשימה מקושרת, לעומת O(N) במערך. למרות שחיפוש ספציפי הוא O(N) בשניהם, תדירות פעולות ההוספה/מחיקה הגבוהה מצדיקה את הבחירה ברשימה מקושרת.
- חשיבות LIFO/FIFO:
- LIFO (מחסנית): חשוב במצבים שבהם סדר הפעולות ההפוך הוא הרצוי. דוגמה: ניהול קריאות לפונקציות (הפונקציה האחרונה שנקראה היא הראשונה שמסתיימת), ביטול פעולות (Undo) בעורך טקסט.
- FIFO (תור): חשוב במצבים שבהם סדר הפעולות המקורי חייב להישמר. דוגמה: ניהול משימות במערכת הפעלה (המשימה הראשונה שהוגשה היא הראשונה שתבוצע), תור הדפסה.