Linked Lists

Dynamic storage allocation is useful for building lists, queues, stacks, trees and other linked structures. A linked structure donsists of a collection of nodes. In C, a node is represented by a structure. Each node structure contains one or more pointers to other node structures. A collection of these nodes can be linked together through these pointer members. The simplest collection of linked structures is the linked list. A node in a linked list might look like this:
struct node
{
    struct Data data;
    struct node *next;
};
(Note: All code examples below will use this node definition.)
An ordinary pointer variable points to the first node in the list. This pointer is referred to as the head pointer. To indicate that the list is empty, the head pointer is initialized to NULL.

struct node *head = NULL;

The node at the end of the list always has its next pointer set to NULL.
Each node is created by a call to malloc:

head = (struct node *) malloc(sizeof(struct node));

After the node has been created the data can be loaded into it and the next pointer set to NULL. One way you can access the data component in the node pointed to by head is to write:

(*head).data

However, C provides a special notation for accessing members of structures through pointers to the structure:

head->data

Searching a Linked List:

The following statement searches a list for data with an integer, j:

for(temp = head; temp != NULL && temp->data.i != j; temp = temp->next);

Note that there is no body to the for loop. The entire search is done within the for statement itself. When the loop terminates, temp will point to the node containing j, or, if j is not in the list, temp will be equal to NULL.

Deleting from a Linked List:

Assume for a moment that the struct Data structure contains an int member named i and we want to delete the node where i is some value we have in j. The following statements will delete the first node in the list whose data contains the value of j:

struct node *p, *q;

/* find node to delete */
for (p = head, q = NULL;
     p != NULL && p->data.i != j;
     q = p, p = p->next);

/* remove node from linked list */
if (q == NULL)
    head = head->next;
else if (p != NULL)
    q->next = p->next;

/* free memory containing deleted node */
free(p);
The for is a bit more complex than the previous one so let's dissect it.
The statement contains two initial conditions:
The first is that p is set to head, making it point to the head of the list.
The second is that q is set to NULL to signal that the loop is just starting.
The condition for remaining in the loop is a compound boolean expression:
First, if p is null it means we have reached the end of the list so p must not equal NULL.
Second, if the integer i in the data is equal to j we have found the node we wish to delete.
The incrementing at the end of the loop has to be two-fold also:
First we set q to p (q always points to the previous node in the list).
Second we set p to point to the next node.
Once we exit the for loop we are ready to delete the node:
  • If q is still NULL it means the node we want to delete is the first node in the list (pointed to by head). To remove it we set head to point to the next node in the list.
  • If q is not NULL then it points to the node before the node we want to delete.
  • If p is not NULL it points to the node we wish to delete. To remove p from the list we set the next pointer in q to point to the next node after p.
  • If p is NULL then the node was not found.
    • Don't forget to free the node you removed from the list (p points to it). If you neglect this your program will have "memory leaks."

    Inserting into a Linked List:

    The following statements will create a node containing data, then insert it at the beginning of the list pointed to by head:

    struct node *temp;

    /* create a new node and put somedata in it */
    temp = (struct node *) malloc(sizeof(struct node));
    temp->data = somedata;

    /* set next pointer to head of list */
    temp->next = head;

    /* now put new node at head of list */
    head = temp;
    Using this code to add to a linked list will construct the list LIFO (Last In First Out). To load the list so you always add to the end of the list:

    struct node *temp, *last;

    temp = (struct node *) malloc(sizeof(struct node));
    temp->data = somedata;
    temp->next = NULL;

    /* find the last node in the list */
    for (last = head; last->next != NULL; last = last->next);
    /* add new node to end of list */
    last->next = temp;
    In many cases we need to construct an ordered list. However, we may be collecting the data in a random order. To build an ordered list we must insert into the list at the appropriate place based on our ordering scheme. Suppose we want to order the list based on the int value i contained in data. The following code will insert into the linked list in order from lowest to highest i:

    struct node *p, *q;

    /* find where node goes in list */
    for (p = head, q = NULL;
         p != NULL && p->data.i < j;
         q = p, p = p->next);

    /* add new node to linked list */
    if (q == NULL)
    {
        /* new node goes at head of list */
        temp->next = head;
        head = temp;
    }
    else
    {
        /* new node goes in middle or end of list */
        temp->next = p;
        q->next = temp;
    }
    In the above code code, when the for loop exits our new node (pointed to by temp) goes after the node pointed to by q but before the node pointed to by p. The only special case we need to check is if the new node belongs at the head of the list. If the new node belongs at the end of the list, p is NULL and we can insert the node the same way we would insert it in the middle.