מבני נתונים - רשימה מקושרת

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

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

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

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

נהוג גם לסמן את האיבר האחרון ברשימה כ-Tail, למרות שזה לא הכרחי.

Search

כדי לבצע לחפש איבר ברשימה מקושרת, יש להתחיל מה-Head ולהמשיך משם לאיבר הבא (Next) ומשם לאיבר הבא וכן הלאה עד לקבלת Null בפוינטר של Next. החיפוש מתבצע ביעילות של O(n).

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

Insert

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

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

מהרגע שהגענו למקום הדרוש, ההכנסה מתבצעת בעלות של O(1).

Remove

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

רשימות דו-כיווניות ומעגליות

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

המחשה יפה לדרך בה רשימה מקושרת עובדת - ניתן למצוא בלינק הבא: https://visualgo.net/en/list

במידה והנושא עדיין לא ברור, אני ממליץ להיעזר בסרטונים הבאים: