3.3 List

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

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

  • Unlink removes the element at position ii from the list. Deleting element ii results in the list l1,,li-1,li+1,,ln\{ 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, eoleol is returned.

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

  • Next returns position i+1i+1 on the list if position ii is provided. When lil_{i} is the last item on the list, eoleol is returned.

  • Previous returns position i-1i-1 on the list if position ii is provided. If ii is one, eoleol 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 EE maintained in a list whose communication buffer is ee. Each edge in EE is defined by the pair of vertices v,w(v,w) that constitute its endpoints. In this situation, the endpoints of edge ee are referenced as e.ve.v and e.we.w.