next up previous contents index
Next: Sets ( set ) Up: Basic Data Types Previous: Linear Lists ( list   Contents   Index


Singly Linked Lists ( slist )

Definition

An instance L of the parameterized data type slist<E> is a sequence of items (slist<E>::item). Each item in L contains an element of data type E, called the element or value 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.

#include < LEDA/core/slist.h >

Types

slist<E>::item the item type.

slist<E>::value_type the value type.

Creation

slist<E> L creates an instance L of type slist<E> and initializes it to the empty list.

slist<E> L(const 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.

item L.first() returns the first item of L.

item L.last() returns the last item of L.

item L.succ(item it) returns the successor item of item it, nil if it = L.last().
Precondition it is an item in L.

item L.cyclic_succ(item l) returns the cyclic successor of item it, i.e., L.first() if it = L.last(), L.succ(it) otherwise.

const E& L.contents(item it) returns the contents L[it] of item it.
Precondition it is an item in L.

const E& L.inf(item it) returns L.contents(it).
Precondition it is an item in L.

const E& L.head() returns the first element of L, i.e. the contents of L.first().
Precondition L is not empty.

const E& L.tail() returns the last element of L, i.e. the contents of L.last().
Precondition L is not empty.

item L.push(const E& x) adds a new item < x > at the front of L and returns it.

item L.append(const E& x) appends a new item < x > to L and returns it.

item L.insert(const E& x, 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(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>& L) appends list L1 to list L and makes L1 the empty list.
Precondition L ! =  L1.

void L.clear() makes L the empty list.

E& L[item it] returns a reference to the contents of it.

item L += const E& x appends a new item < x > to L and returns it.


next up previous contents index
Next: Sets ( set ) Up: Basic Data Types Previous: Linear Lists ( list   Contents   Index
root 2008-01-09