Singly Linked Lists (slist)

Definition

An instance L of the parameterized data type slist<E> is a sequence of items (slist_item). Each item in L contains an element of data type E, called the element type of L. The number of items in L is called the length of L. If L has length zero it is called the empty list. In the sequel <x> is used to denote a list item containing the element x and L[i] is used to denote the contents of list item i in L.

Creation

slist<E>	L;	creates an instance L of type slist<E> and initializes it to the empty list.
slist<E>	L(E x);	creates an instance L of type slist<E> and initializes it to the one-element list <x>.

Operations

int	L.length()	returns the length of L.
int	L.size()	returns L.length().
bool	L.empty()	returns true if L is empty, false otherwise.
slist_item	L.first()	returns the first item of L.
slist_item	L.last()	returns the last item of L.
slist_item	L.succ(slist_item it)	returns the successor item of item it, nil if it=L.last(). Precondition: it is an item in L.
slist_item	L.cyclic_succ(slist_item it)
		returns the cyclic successor of item it, i.e., L.first() if it = L.last(), L.succ(it) otherwise.
E	L.contents(slist_item it)	returns the contents L[it] of item it. Precondition: it is an item in L.
E	L.inf(slist_item it)	returns L.contents(it). Precondition: it is an item in L.
E	L.head()	returns the first element of L, i.e. the contents of L.first(). Precondition: L is not empty.
E	L.tail()	returns the last element of L, i.e. the contents of L.last(). Precondition: L is not empty.
slist_item	L.push(E x)	adds a new item <x> at the front of L and returns it.
slist_item	L.append(E x)	appends a new item <x> to L and returns it.
slist_item	L.insert(E x, slist_item pos)
		inserts a new item <x> after item pos into L and returns it. Precondition: it is an item in L.
E	L.pop()	deletes the first item from L and returns its contents. Precondition: L is not empty.
void	L.del_succ_item(slist_item it)
		deletes the successor of item it from L. Precondition: it is an item in L and has a successor.
void	L.conc(slist<E>& L1)	appends list L_1 to list L and makes L_1 the empty list. Precondition: L != L_1.
E&	L[slist_item it]	returns a reference to the contents of it.
slist_item	L += E x	appends a new item <x> to L and returns it.