1.1. Linked lists

A linked link is a simple way to store a list of items. It's main advantage over arrays is that it is very quick to insert and delete items. It can also change size dynamically. The disadvantages are that you cannot directly reference the nth element, and a memory overhead.

How does it work?

A linked list consists of a number of nodes, each of which consists of a piece of data and a pointer to the next node. In the picture, each big rectangle is a node. The left block is the data (in this case, a character) and the right block is the pointer. The last pointer is a null pointer.

The nodes can reside anywhere in memory, independant of each other, and are allocated as needed. The variable used to access the list is usually a pointer to the first node (called the head). Sometimes it is also useful to have a pointer to the last node (called the tail). I will call these the head and tail pointers respectively.

Insertion

To insert an element X after node A, do the following:

1. Allocate memory for a new node, B.
2. Make the data element of B equal to X.
3. Make the pointer of B equal the pointer of A.
4. Make the pointer of A equal the address of B.

To insert an element X at the front of a list, do the following:

1. Allocate memory for a new node, B.
2. Make the data element of B equal to X.
3. Make the pointer of B equal the head pointer.
4. Make the head pointer equal the address of B.

Deletion

To delete a node, do the following:

1. Save a copy of the pointer to the node.
2. Set the previous element's pointer (or the head pointer, if deleting the first element) to the current element's pointer.
3. Dispose of the memory allocated to the deleted node, using the saved pointer.

Last updated Sun Nov 28 22:04:38.0000000000 2004. Copyright Bruce Merry (bmerry '@' gmail dot. com).