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

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

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

ממשק

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

# 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

בנוסף, אנו מייצרים מבנה המתאר את הרשימה עצמה. למבנה זה שדות לחוליות הראש והזנב (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

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

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

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

תבנית:מבנה תבנית

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

# 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

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

הקוד אינו מכיל לולאות או קריאות רקורסיביות, ולכן זמן הפעולה חסום מלמעלה ע"י קבוע שאינו תלוי בגודל הרשימה. הזמן, לכן, הנו $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

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

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

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

הפסוודו-קוד לפעולות תבנית:קוד בשורה, תבנית:קוד בשורה ותבנית:קוד בשורה, פשוט מאד. כ"א מפעולות אלה, גם היא $O(1)$.