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

# 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)
 
6	Prints 3
7	Print( Front(lst) )
 
8	Prints 1
9	Print( Back(lst) )
 
	# Prints 3.
10	Print( Size(lst) )

# 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

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

# 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