Linked lists

The linked list is a very flexible dynamic data structure: items may be added to it or deleted from it at will. A programmer need not worry about how many items a program will have to accommodate: this allows us to write robust programs which require much less maintenance. A very common source of problems in program maintenance is the need to increase the capacity of a program to handle larger collections: even the most generous allowance for growth tends to prove inadequate over time!

In a linked list, each item is allocated space as it is added to the list. A link is kept with each item to the next item in the list.

Each node of the list has two elements the item being stored in the list and a pointer to the next item in the list The last node in the list contains a NULL pointer to indicate that it is the end or tail of the list.

As items are added to a list, memory for a node is dynamically allocated. Thus the number of items that may be added to a list is limited only by the amount of memory available.

Handle for the list

The variable (or handle) which represents the list is simply a pointer to the node at the head of the list.

Adding to a list

The simplest strategy for adding an item to a list is to:

1. allocate space for a new node,
2. copy the item into it,
3. make the new node's next pointer point to the current head of the list and
4. make the head of the list point to the newly allocated node.

This strategy is fast and efficient, but each item is added to the head of the list.

An alternative is to create a structure for the list which contains both head and tail pointers:

 struct fifo_list {
 struct node *head;
 struct node *tail;
 };

Doubly Linked Lists

Doubly linked lists have a pointer to the preceding item as well as one to the next.

They permit scanning or searching of the list in both directions. (To go backwards in a simple list, it is necessary to go back to the start and scan forwards.) Many applications require searching backwards and forwards through sections of a list: for example, searching for a common name like "Kim" in a Korean telephone directory would probably need much scanning backwards and forwards through a small region of the whole list, so the backward links become very useful. In this case, the node structure is altered to have two links:

struct t_node {
 void *item;
 struct t_node *previous;
 struct t_node *next;
 } node;