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
Christian Uhrig 2017-04-07