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

ישנם פרופסורים בקולג' שעסקו בקריירה שלהם בחקר מבני נתונים ומאות ספרים אודות מבני  נתונים נכתבו.

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

קשר (node) כפי שמתואר בפרק זה, הנו אובייקט בו ניתן להשתמש על מנת לאחסן מידע.

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

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

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

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

רשימות מקושרות מופיעות בוריאציות של קשר יחיד (singly-linked) וקשר כפול (doubly linked).

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

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

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

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

עם זאת, זהו מבנה טוב ליישום מחסניות (stacks) ותורים (queues) כפי שנראה להלן.

בשיעור זה נפתח רשימת קשר יחיד כלל תכליתית, ממנה ניתן להכין תת-מחלקה ממחלקת  מחסנית וממחלקת תור.    

מחסנית נחשבת באופן שכיח כמבנה של נכנס אחרון/ יצא ראשון (LIFO) עבור אחסון מידע. זאת אומרת שכאשר מאחזרים מידע ממחסנית, חבילת (packet) המידע אשר הוכנס אחרון יהיה הראשון אשר יוחזר.
המידע השני בותיקותו יוחזר אחר כך וכ"ו.

הכנסת מידע למחסנית מוגדרת לעיתים קרובות כאל דחיפת מידע על המחסנית. אחזור מידע מתוך  מחסנית מוגדרת כאל הוצאת העליון (popping)  מתוך המחסנית. הוצאת המידע העליון ממחסנית מוציאה אותו פיזית מן המחסנית.

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

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

השימוש ברשימה מקושרת כאל היישום היסודי של המחסנית מעניקה בנוסף הדגמה טובה של יתרונות הטבעיים של תכנות מכוונת אובייקט.

תור נחשב תכופות כאל מבנה של נכנס ראשון. יצא ראשון (FIFO) לאחסון מידע. כלומר,
כאשר מאחזרים מידע מתור, חבילת המידע אשר נמצא בתור הזמן הרב ביותר תהיה החבילה הבאה אשר מוחזרת.

הכנסת מידע לתור מוגדרת enqueuing  מידע ואחזור מידע מתור מוגדר לעיתים כ- dequeuing מידע.

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

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

כמו במחסנית, השימוש ברשימה מקושרת כאל היישום הבסיסי של תור היא הדגמה טובה ליתרונות הטבעיים של תכנות מכוונת אובייקט.

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

רשימה מסודרת היא רשימה בה המידע שומר על סדר מסוים: נומרי, אלפבטי, אלפאנומרי וכ"ו… וניתן לאחסן או לאחזר אותו על בסיס של ערך מרכזי (key) כלשהו.

עקב יכולות הגישה האקראיות הדלות, רשימה מקושרת אינה מבנה בסיסי טוב בהכרח עבור רשימה מסודרת.

אבל, פיתוח רשימה מסודרת תוך שימוש ברשימה מקושרת מעניקה מספר הדגמות טובות של מושגי תכנות חשובים ב- JAVA (לדוגמא שימוש בסוגי ממשקים).

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

בניגוד למחסנית ולתור המתוארים, אין כאן יתרונות רבים (כמו שניים במחיר אחד) מכיוון שהרשימה המקושרת המשודרגת  הנחוצה לתמוך ברשימה מסודרת היא מורכבת יותר מזו הנחוצה לתמוך במחסנית ובתור.

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