3.3 List

A simple list $L$ is an ordered set of elements. If the set $\{ l_{1},\cdots,l_{i},l_{{i+1}},\cdots,l_{n}\}$ represents $L$, then the list contains $n$ elements. Element $l_{1}$ is the first item on the list and $l_{n}$ is the last item on the list. Element $l_{i}$ precedes $l_{{i+1}}$ and element $l_{{i+1}}$ follows $l_{i}$. Element $l_{i}$ is at position $i$ in $L$. Descriptive information may accompany each item on a list. Lists associated with graph algorithms support the following operations:

• Link adds an element $x$ to a list at position $i$. Inserting element $x$ position $i$ results in an updated list: $\{ l_{1},\cdots,l_{{i-1}},x,l_{i},l_{{i+1}},\cdots,l_{n}\}$ An insertion at position $eol$ appends $x$ to the end of the list.

• Unlink removes the element at position $i$ from the list. Deleting element $i$ results in the list $\{ l_{1},\cdots,l_{{i-1}},l_{{i+1}},\cdots,l_{n}\}$.

• Find looks for an element on the list and returns its position. If the element is not a member of the list, $eol$ is returned.

• First returns the position of the first item on the list. When the list is empty, $eol$ is returned.

• Next returns position $i+1$ on the list if position $i$ is provided. When $l_{i}$ is the last item on the list, $eol$ is returned.

• Previous returns position $i-1$ on the list if position $i$ is provided. If $i$ is one, $eol$ is returned.

A linked list refers to a list implementation that does not require its members to reside in contiguous storage locations. In this environment, an efficient implementation of the previous operator dictates the use of a doubly linked list.

Communicating with a simple list is analogous to adjacency list communication. Read operations (find, first, next, and previous) make list information available in a buffer. Update operations (link, unlink) modify the list based on the current contents of the buffer.

If it is necessary to distinguish discrete elements in the communication buffer, the structure notation of the C programming language is used. For example, consider a set of edges $E$ maintained in a list whose communication buffer is $e$. Each edge in $E$ is defined by the pair of vertices $(v,w)$ that constitute its endpoints. In this situation, the endpoints of edge $e$ are referenced as $e.v$ and $e.w$.