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 and initializes it to the empty list. slist< E> L(const E& x) creates an instance L of type slist 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: Sets ( set ) Up: Basic Data Types Previous: Linear Lists ( list   Contents   Index
Christian Uhrig 2017-04-07