מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/רשימות מקושרות

דף זה עוסק ברשימה מקושרת. רשימה מקושרת שימושית מאד לשמירת איברים כאשר:

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

כדאי לדעת: #גישה לאיבר בסדר שרירותי נקרא random access. בספר הקורס, הפרק "Elementary Data Structures" מכסה נושא זה. ישנם למעשה סוגים רבים של רשימות מקושרות. באופן מדויק יותר, דף זה עוסק ברשימה מקושרת דו-כיוונית. תוכל לקרוא על רשימה חד-כוונית בספר על שפת C. תוכל לראות את הפסוודו-קוד המלא למבנה זה ברשימות מקושרות - פסוודו-קוד.

מימוש C++ std::list

ממשק

להלן ממשק אפשרי לרשימה מקושרת:

# Creates a list	
Make-List()

# Adds a value (v) to the front of a list (l).
Insert-Front(l, v)

# Adds a value (v) to the back of a list (l).
# Returns the new link.
Insert-Back(l, v)

# Returns the size of a list (l).
Size(l)

# Returns the first element of a list (l).
Front(l)

# Returns the last element of a list (l).
Back(l)

# Removes a value from the front of a list (l).
Delete-Front(l)

# Removes a value from the back of a list (l).
Delete-Back(l)

להלן דוגמה לשימוש בה:

1	lst = Make-List()

	# Prints 0.
2	Print( Size(lst) )

3	Insert-Front(lst, 1)
4	Insert-Front(lst, 2)
5	Insert-Front(lst, 3)

	# Prints 3
6	Print( Front(lst) )

	# Prints 1
7	Print( Back(lst) )

	# Prints 3.
8	Print( Size(lst) )

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

ארגון המידע

ראשית ניצור מבנה המייצג link (חוליה). למבנה זה השדות הבאים:

1. (מצביע ל)חוליה הקודמת
2. ערך החוליה
3. (מצביע ל)חוליה הבאה

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

חוליית רשימה מקושרת (דו-כוונית).

להלן הפסוודו-קוד לחוליה:

# A data structure that describes a link which has a value, and can
#	be connected to a following and previous link.
Link
	# The next Link.
1	next
	# The value at this link.
2	value
	# The previous Link.
3	prev


# Create a link which holds a value (v).	
Make-Link(v)
1	lnk = Link()

2	lnk.prev = lnk.next = Nil
3	lnk.value = v

4	return lnk

כדאי לדעת: #שלא כבשפת C, לא נשתמש בסימונים מיוחדים עבור מצביעים. עליך להבין מההקשר האם משתנה הוא מצביע או לא. ההבדלה בין משתנים "רגילים" לבין מצביעים, היא סימן ההיכר של שפות low-level, כגון C. בשפות עיליות יותר, כגון פייתון, כותבים בצורה כמעט זהה לפסוודו-קוד כאן. איננו עוסקים בקורס זה בניהול זיכרון פרטני, ובפרט לא בדרכים להקצות זיכרון (כמו malloc בC, או new בC++). בMake-Link,‏ 1, "נוצרת" חוליה חדשה.

בנוסף, אנו מייצרים מבנה המתאר את הרשימה עצמה. למבנה זה שדות לחוליות הראש והזנב (front, back), וכן שדה לגודל הרשימה (size).

רשימה מקושרת (דו-כוונית).

להלן הפסוודו-קוד:

# A data structure that describes a (doubly-linked) list of values.
List
	# The leftmost link.
1	front
	# The rightmost link.
2	back
	# The size (number of links).
3	size


# Creates a list	
Make-List()
1	l = List()

2	l.front = l.back = Nil
3	l.size = 0

4	return l

התרשים הקודם מראה את הרשימה במצבה ההתחלתי, לאחר יצירתה.

פעולות Insert

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

1. אם הרשימה ריקה, פשוט יש לקבוע את המצביעים front וback לחוליה החדשה.
2. אם הרשימה אינה ריקה, יש לשרשר את החוליה לחוליה שאליה מצביע front.

(יש לעדכן את גודל הרשימה בכל מקרה, כמובן.)

דוגמה: בדוגמה שלמעלה, דחפנו לראש הרשימה את 1, 2, ו3. לאחר דחיפת 1, הרשימה נראית כך: דחיפת 1 לראש הרשימה. לאחר דחיפת 2, הרשימה נראית כך: דחיפת 3 לראש הרשימה. לאחר דחיפת 3, הרשימה נראית כך: דחיפת 3 לראש הרשימה.

להלן הפסוודו-קוד לדחיפת איבר לראש הרשימה:

# Adds a value (v) to the front of a list (l).
Insert-Front(l, v)
1	new-lnk = Make-Link(v)
	
2	if l.front == Nil
3		l.front = l.back = new-lnk
4	else
5		new-lnk.next = l.front
6		l.front.prev = new-lnk
7		l.front = new-lnk
	
8	++l.size

(הפסוודו-קוד לדחיפת איבר לסוף הרשימה - Insert-Back - דומה מאד.)

הקוד אינו מכיל לולאות או קריאות רקורסיביות, ולכן זמן הפעולה חסום מלמעלה ע"י קבוע שאינו תלוי בגודל הרשימה. הזמן, לכן, הנו $\displaystyle O(1)$.

פעולות Delete

להלן הפסוודו-קוד לשליפת איבר מסוף הרשימה (כלומר, מחיקת חוליית הסוף, והחזרת הערך שהוכל בחוליה לפני שנמחקה):

# Removes a value from the back of a list (l).
Delete-Back(l)
1	value = Back(l)

2	l.back = l.back.prev

3	if l.back == Nil
4		l.front = Nil
5	else
6		l.back.next = Nil
	
7	--l.size

8	return value

דוגמה: נניח שנקרא לDelete-Back, אז האיבר שיוחזר יהיה 1, והרשימה תיראה כך: שליפת 3 מסוף הרשימה.

(הפסוודו-קוד לשליפת איבר מראש הרשימה - Delete-Back - דומה מאד.)

גם פונקציה זו היא $\displaystyle O(1)$.

פעולות פשוטות

הפסוודו-קוד לפעולות Front, Back וSize, פשוט מאד. כ"א מפעולות אלה, גם היא $\displaystyle O(1)$.

הפרק הקודם: מבני נתונים

רשימות מקושרות תרגילים

הפרק הבא: מחסניות