A simple list is an ordered set of elements. If the set represents , then the list contains elements. Element is the first item on the list and is the last item on the list. Element precedes and element follows . Element is at position in . Descriptive information may accompany each item on a list. Lists associated with graph algorithms support the following operations:
Link adds an element to a list at position . Inserting element position results in an updated list: An insertion at position appends to the end of the list.
Unlink removes the element at position from the list. Deleting element results in the list .
Find looks for an element on the list and returns its position. If the element is not a member of the list, is returned.
First returns the position of the first item on the list. When the list is empty, is returned.
Next returns position on the list if position is provided. When is the last item on the list, is returned.
Previous returns position on the list if position is provided. If is one, 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 maintained in a list whose communication buffer is . Each edge in is defined by the pair of vertices that constitute its endpoints. In this situation, the endpoints of edge are referenced as and .