List Data Structures: Basics

Now that we have discussed a large amount of the preliminary material related to the C+ + language, we want to begin our discussion of Abstract Data Structures (ADT's) with the list ADT. The list ADT consists of a finite collection of data of type TYPE together with information about the location of the other elements in the list. A double linked list or DLLIST then contains the finite collection of elements

a₀, a₁,..., a_{N - 1}

arranged in a chain

a₀ $$\leftrightarrow$$  a₁  $$\leftrightarrow$$   ^...   $$\leftrightarrow$$  a_{N - 1}

.

Since each element a_i has a corresponding compiler generated address p_i, we will use the convention that the two sided arrows $\leftrightarrow$ indicate that we store the address of each element a_i's predecessor a_{i - 1} successor a_{i + 1} in some fashion. Some method of storing this triple of information is then required. In general, we then need a block of storage of the form [TYPE a] [TYPE *p] [TYPE *s] where p and s denote the predecessor and successor address, respectively.

Storing both predecessor and successor address information requires, of course, a bit more storage, so another way of organizing the list is to only store the successor information. This generates the chain

a₀ $$\rightarrow$$  a₁  $$\rightarrow$$   ^...   $$\rightarrow$$  a_{N - 1}

,

which only requires us to store the addresses of successors. Note that we use a one sided arrow $\rightarrow$ to denote this choice. We require less storage in this case, using blocks of the form [TYPE a] [TYPE *s]. This is the singly linked list or SLLIST.

A third common type of linked list is the circular chain, in which the successor of the last element in the list is considered to be the first element.

In this chapter, we will implement these sorts of lists using a core class LIST_CORE with various derived children. In general, the list ADT requires several important methods or agents in order to do useful work with the list ADT. These agents will

Check to see if the list is empty:

Delete an element from the list:

Search for a given element in the list:

Count the number of elements in the list:

Build a list from input data:

Insert an element after a specified entry in the list:

Insert an element before a specified entry in the list:

We will design our core class LIST_CORE with the agents above declared pure virtual and then proceed to derive children for the various list possibilities.

The Array Based List:

This implementation uses a fixed vector of size list_size which is instantiated using an pointer to data of type TYPE, TYPE* list. The elements in the list are then potentially numbered from 0 to list_size-1 with list[0] denoting the first element in the list and list[last] giving the final element in the list. The index of the final element in the list is given by the variable last. The ordering scheme for this type of list is quite simple. Each element in the list has a predecessor and a successor in the list. The first element has no predecessor and the final element list[last] has no successor. In this type of list implementation, we build a list by starting at the index position in the list array immediately after list[last] and fill in the list with new elements until the list is completely full. We don't need to store predecessor and successor addresses in this type of list as neighborhood information for a given element is simply ''go up the array'' or ''go down the array'' by one index. However, this version has a fixed size, so we potentially fill the list completely.

The Pointer Based List:

The Singly Linked List:

The Doubly Linked List:

The Circular Linked List: