Chapter 3 Linked Lists

Simple data structures such as arrays, sequential mappings, have the property that successive nodes of the data object are stored a fixed distance apart. These sequential storage schemes proved adequate given the functions one wished to perform (access to an arbitrary node in a table, insertion or deletion of nodes within a stack or queue). However, when a sequential mapping is used for ordered lists, operations such as insertion and deletion of arbitrary elements become expensive. For example, consider the following list of all of the three letter English words ending in AT:

(BAT, CAT, EAT, FAT, HAT, JAT, LAT, MAT, OAT, PAT, RAT, SAT, TAT, VAT, WAT)

To make this list complete we naturally want to add the word GAT. If we are using an array to keep this list, then the insertion of GAT will require us to move elements already in the list either one location higher or lower. We must either move HAT, JAT, LAT,..., WAT or else move BAT, CAT, EAT, FAT. If we have to do many such insertions into the middle, then neither alternative is attractive because of the amount of data movement.Or suppose we decided to move the word LAT. Then again, we have to move many elements so as to maintain the sequential representation of the list.

When our problem called for several ordered lists of varying sizes, sequential representation again proved to be inadequate. By stroing each list in a different array of maximum size, storage may be wasted. By maintaining the lists in a single array a potentially large amount of data movement is needed. "Ordered lists" reduce the time needed for arbitrary insertion and deletion which are explained in this section.

Sequential representation is achieved by using linked representations. Unlike a sequential representation where successive items of a list are located a fixed distance apart, in a linked representation these items may be placed anywhere in memory. Another way of saying this is that in a sequential representation the order of elements is the same as in the ordered list, while in a linked representation these two sequences need not be the same. To access elements in the list in the correct order, with each element we store the address or location of the next element in that list. Thus associated with each data item in a linked representation is a pointer to the next item. This pointer is often referred to as a link. In general a node is a collection of data, data(1), ... ,data(n) and links link(1), ... , link(m). Each item in a node is called a field. A field contains either a data item or a link.

The elements of the list are stored in a one dimensional array called data. But the elements of the list no longer occur in sequential order, BAT before CAT before EAT, etc. Instead we relax this restriction and allow them to appear anywhere in the array and in any order. In order to remind us of the real order, a second array link is added. The values in this array are pointers to elements in the data array. Since the list starts at data[8] = BAT, let us set a variable f=8. link[8] has the value 3, which means it points to data[3] which contaons CAT. The third element of the list is pointed at by link[3] which is EAT. By continuing in this way we can list all the words in the proper order. We recognize that we have come to the end when link has a value of zero.

It is customary to draw linked lists as an ordered sequence of nodes with links being represented by arrows. We shall use the name of the pointer variable that points to the list as the name of the entire list. Thus the list we consider is the list f. Notice that we do not explicitly put in the values of the pointers but simply draw arrows to indicate they are there. This is so that we reinforce in our own mind the facts that (i) the nodes do not actually reside in sequential locations, and that (ii) the locations of nodes may change on different runs. Therefore, when we write a program which works with lists, we almost never look for a specific address except when we test for zero.

It is much more easier to make an arbitrary insertion or deletion using a linked list rather than a sequential list. To insert the data item GAT between FAT and HAT the following steps are adequate:

1. get a node which is currently unused; let its address be x;
2. set the data field of this node to GAT;
3. set the link field of x tp point the node after FAT which contains HAT;
4. set the link field of the node containing FAT to x.

The important thing is that when we insert GAT we do not have to move any other elements which are already in the list. We have overcome the need to move data at the expense of the storage needed for the second field, link.

Now suppose we want to delete GAT from the list. All we need to do is find the element which immediately precedes GAT, which is FAT, and set link[9] to the position of HAT which is 1. Again, there is no need to move the data around. Even though the link field of GAT still contains a pointer to HAT, GAT is no longer in the list.

Click on the example to see an interactive demo.