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

# 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