//////////////////////////////////////////////////////////////////////////
// 04. Linked Lists : An Introduction                                   //
//     By: Chad Knudson                                                 //
//         AKA Sputnix @EFnet's #c                                      //
//     Email: knudson@sputnix.com                                       //
//////////////////////////////////////////////////////////////////////////

A linked list is a data structure that contains fields for storing the data
as well as one or more pointer fields. This basic data structure is called a
"node". The pointer field(s) point to other nodes in the list. By chaining
nodes together like this with pointers, we can traverse the list by
following the pointers in the nodes.

A Singly Linked List contains one pointer in the NODE, which is typically a
NEXT pointer that points to the next node in the list. A Doubly Linked List
contains two pointers in the NODE, a NEXT pointer that points to the next
node in the list and also a PREV pointer that points to the previous node in
the list. With two pointers, you can traverse the list in either direction.


For the introduction, we will be talking primarily about singly linked
lists.

Here's a sample node structure for a singly linked list that stores integers
in each node:


typedef struct NODE
{
    int iData;
        struct NODE * pNodeNext;
} NODE;



Let's look at a list with nodes containing 10, 20, and 30 in their data
fields: Figure 1.0


          +----+     +----+     +----+
pHead --> | 10 | --> | 20 | --> | 30 | --+
          +----+     +----+     +----+   |
                                         V

Where:

        NODE * pHead;           // Pointer to first node in the list
        

Linked lists are typically drawn with boxes representing nodes, pointers are
drawn as arrows that connect one node to another, and a NULL pointer is
represented by the downwards pointing array after 30.

Notice that we maintain a variable called pHead to keep track of the first
node in the list.

What are some of the benefits of a linked list?

1.Insertion and deletion operations can maintain the list in order at all
times -- you never have to "sort" the list.

2.Since nodes are created dynamically, you don't need to know how many you
will need in advance (as you would with an array.)

Inserting a node into a linked list

We saw in the list of benefits that linked lists can maintain order at all
times and that it never needs to be sorted. How is this possible? It all
happens in the function that is responsible for inserting the nodes in the
list. The insert function needs to find out where in a list a new node
should be placed and update the pointers in the node prior to it in the
list. Let's look at an example and see what needs to take place:

Figure 1.1 - Inserting a node into a singly linked list

          +----+         +----+         +----+
pHead --> | 10 |         | 20 |   -->   | 30 |   --+
          +----+         +----+         +----+     |
                \       /                          V
                 +----+
                 | 15 |
                 +----+

What must take place here? First we need to traverse the list and determine
where the new node needs to be located. Our original list is the list from
Figure 1.0 and we are going to add a new node that contains 15 in the data
field.

We start out with a simple check -- is our list currently empty? An empty
list would have a pHead that contains NULL. If the list is empty, inserting
a node is simple, we simply make pHead point to our new node, and our new
node's pNext pointer will be set to NULL since there are no other nodes in
the list.

Problem with our example, is that things aren't that simple. We are going to
need to traverse the list at least part way to find where our new node
belongs.

The process of traversing the list looking for the correct location to place
a new node involves maintaining a number of variables, more specifically, a
number of NODE * variables. We will use two NODE * variables, pNodePrev and
pNodeCur.

Initially, we will want to set pNodePrev to NULL, indicating that there is
nothing before the beginning of the list. pNodeCur, which will keep track of
the current node that we are looking at, will be initialized to the value of
pHead which is a pointer to the first node in our list.

NODE * pNodePrev = NULL;
NODE * pNodeCur = pHead;

As we traverse the list, we check the value of pNodeCur->iData against the
value of our new node, pNodeNew->iData. If the value of our new node is
greater than the value of the current node of the list, we advance our
position in the list by first setting the value of pNodePrev to be pNodeCur,
then advancing by setting pNodeCur to be equal to pNodeCur->pNodeNext.

If the value of our new node is less than the value of the current node,
then we have found the location and we simply need to fix up a few pointers
to include the new node in the list. Now you will see why we kept both
pNodePrev and pNodeCur pointers around.

pNodePrev may be NULL -- this would indicate that our new node is going to
be the first node in the list. In this situation, you simply set the value
of pNodeNew->pNextNode to the value of pHead and then change pHead to
pNewNode.

If pNodePrev is not NULL, then you need to set pNodeNew->pNodeNext to
pNodePrev->pNodeNext and pNodePrev->pNodeNext should be set to pNodeNew.

Figure 1.2 Singly Linked List with new node added

          +----+     +----+     +----+     +----+
pHead --> | 10 | --> | 15 | --> | 20 | --> | 30 | --+
          +----+     +----+     +----+     +----+   |
                                                    V


Another situation you can find yourself in is that you have not yet added
your new node to the list and pNodeCur is NULL. This indicates that you new
node is to be placed at the end of the list. To insert your new node, the
procedure is exactly the same as when the new node was in the middle of the
list: First you set pNodeNew->pNodeNext to the value in pNodePrev->pNodeNext
(in this case, pNodePrev->pNodeNext is NULL since pNodePrev was the last
node in the list.) Second, you set pNodePrev->pNodeNext to pNodeNew and you
have successfully added a node to the end of the list.

Exercises

In each of the execises below, keep track of the pHead, pNodePrev, pNodeCur
pointers.

1.Go through the procedure of adding the following nodes with the following
data values: 25, 8, 50.

2.Go through the procedure of creating a list with nodes that contain the
following data values: 50, 30, 10, 20, 25, 8

3.Explain how you would accomplish deleting a node from a list? What happens
if the node is the first node of the list? The last node of the list? An
interior node of the list?

Write the Code
--------------
1.Implement a linked list of Integers (NODES similar to the structure
discussed in this chapter.)

2.Implement a singly linked list of strings. The strings should be variable
in length (NODES contain a character pointer to a dynamically allocated
string.)

Diagrams
--------
1.Figure 1.0 - Example of a Singly Linked List
2.Figure 1.1 - Inserting a Node into a Singly Linked List
3.Figure 1.2 - New Node Added to Singly Linked List

Examples
--------
1.Singly-linked list, all elements added to the end of the list
2.Singly-linked list, elements added to the head, tail, in-order, or
in-reverse order

This information is Copyright(c) 1997 Chad Knudson - All Rights Reserved

You can find this article, sample programs, and other useful information
about C programming on his web pages at http://www.sputnix.com/LearnC.

Included file: CS1-04.zip