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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש


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

# 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 v


# 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


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



# 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



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


# Returns the first element of a list (l).
Front(l)
1	return l.front.value


# Returns the last element of a list (l).
Back(l)
1	return l.back.value


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

2	l.front = l.front.next

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

8	return value


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

2	l.back = l.back.next

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

8	return value