Expert: Joseph Moore - 5/26/2009

Question
Pls help me in understanding linked list in 'C' with easy example

Answer
The linked list is a simple, very commonly used data structure.  Linked lists typically come in a two varieties, singly- and doubly-linked lists, with many different possible implementations.  Typically linked lists are implemented with pointers, though they can be implemented with an array.

A linked list typically consists of a list container and nodes.  The list container will primarily be used as the entry point for the list.  If this were C++, the container would likely be a class and would be where all of your interface functions exist.  In C, your container will likely just be a special instance of a node or a node pointer, since the interface functions will have to exist separately.  The most important feature of the container is that it must know where the beginning (and/or end, depending on implementation) of the list is.  The beginning of a list is called the head.  The end of the list is called the tail.

The nodes contain the data to be stored in the list and one or more pointers to connected nodes.  In a singly-linked list, you will have a single pointer to the next (or previous, depending on implementation) node.  If there is no connected node, then the pointer will be invalid (0 or NULL).  Checking for this condition is how you determine when you are at the end of the list.

A simple, singly-linked list of integers will have a node definition such as:

   typedef struct _SingleListNode
   {
       int nMyData;
       struct _SingleListNode* pNextNode;
   } SingleListNode;

For example purposes, I want to define a list container for this list, too.  Its definition will be:

   typedef struct _SingleList
   {
       SingleListNode* pHead;
   } SingleList;

The absolute, most basic implementation of a linked list would be the unordered, singly-linked list.  An insert to this list would simply happen at the head.  When removing an item, you would have to specify what item to remove, and the entire list would have to be searched until the item was found.  Because this is a singly-linked list, you must keep track of the previous node so that any pointer fix-up can be done.  These functions would look something like the following:

   void insertInList(SingleList* _pList, int _insertVal)
   {
       // We need to allocate a new note to store on the list.
       SingleListNode* pNewNode = (SingleListNode*)malloc(sizeof(SingleListNode));

       // Now we initialize the data in the new node.  Notice that we set the
       // next pointer of the new node to be the head of the list.  This is
       // because the way we add to the list is to simply push the new node
       // onto the front of the list.  It's fast and easy.
       pNewNode->nMyData = _insertVal;
       pNewNode->pNextNode = _pList->pHead;

       // However, pushing the new node to the front of the list means that we
       // must update the list itself to understand that the new node is the
       // head of the list.
       _pList->pHead = pNewNode;
   }

   int removeFromList(SingleList* _pList, SingleListNode* _pNode)
   {
       SingleListNode* pCurrNode = _pList->pHead;
       SingleListNode* pPrevNode = NULL;

       while (pCurrNode)
       {
           // See if we've found the node we're looking for.
           if (pCurrNode == _pNode)
           {
               // If we have a prev node, then we're somewhere in the middle
               // or end of the list... easy
               if (pPrevNode)
               {
                   // Make the previous node's next point to the current
                   // node's next.  This prevents the list from pointing to
                   // invalid memory and keeps the list in tact.
                   pPrevNode->pNextNode = pCurrNode->pNextNode;
               }
               // No prev node means we're removing the head of the list.  Fix
               // the head pointer.
               else
               {
                   _pList->pHead = pCurrNode->pNextNode;
               }

               // We dynamically allocated these nodes in the insert function,
               // so we need to clean them up on the remove.
               free(pCurrNode);

               // Let the caller know that the node was found and removed.
               return 1;
           }

           // Store the current node, move on to the next node.
           pPrevNode = pCurrNode;
           pCurrNode = pCurrNode->pNextNode;
       }

       // Node not found in list.
       return 0;
   }

A full, incredibly simple program using these structures and functions follows.  This program will create a linked list, add a few nodes, then demonstrate removal of the head, tail and a middle node in the list.  Please note that this program is intended to just demonstrate the basics of a singly-linked list.  It isn't a terribly smart program or list setup, but it shows how a linked list works.

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct _SingleListNode
{
   int                        nMyData;
   struct _SingleListNode*    pNextNode;
} SingleListNode;

typedef struct _SingleList
{
   SingleListNode*    pHead;
} SingleList;

void insertInList(SingleList* _pList, int _insertVal)
{
   // We need to allocate a new note to store on the list.
   SingleListNode* pNewNode = (SingleListNode*)malloc(sizeof(SingleListNode));

   // Now we initialize the data in the new node.  Notice that we set the
   // next pointer of the new node to be the head of the list.  This is
   // because the way we add to the list is to simply push the new node
   // onto the front of the list.  It's fast and easy.
   pNewNode->nMyData = _insertVal;
   pNewNode->pNextNode = _pList->pHead;

   // However, pushing the new node to the front of the list means that we
   // must update the list itself to understand that the new node is the
   // head of the list.
   _pList->pHead = pNewNode;
}

int removeFromList(SingleList* _pList, SingleListNode* _pNode)
{
   SingleListNode* pCurrNode = _pList->pHead;
   SingleListNode* pPrevNode = NULL;

   while (pCurrNode)
   {
       // See if we've found the node we're looking for.
       if (pCurrNode == _pNode)
       {
           // If we have a prev node, then we're somewhere in the middle
           // or end of the list... easy
           if (pPrevNode)
           {
               // Make the previous node's next point to the current
               // node's next.  This prevents the list from pointing to
               // invalid memory and keeps the list in tact.
               pPrevNode->pNextNode = pCurrNode->pNextNode;
           }
           // No prev node means we're removing the head of the list.  Fix
           // the head pointer.
           else
           {
               _pList->pHead = pCurrNode->pNextNode;
           }

           // We dynamically allocated these nodes in the insert function,
           // so we need to clean them up on the remove.
           free(pCurrNode);

           // Let the caller know that the node was found and removed.
           return 1;
       }

       // Store the current node, move on to the next node.
       pPrevNode = pCurrNode;
       pCurrNode = pCurrNode->pNextNode;
   }

   // Node not found in list.
   return 0;
}

void printList(SingleList* _pList)
{
   // How we loop through the list
   SingleListNode* pCurrNode = _pList->pHead;

   printf("List contains nodes:\n");
   while (pCurrNode)
   {
       printf("\t%d\n", pCurrNode->nMyData);
       pCurrNode = pCurrNode->pNextNode;
   }
}

int main()
{
   // Storage pointers for some example code
   SingleListNode* pHead = 0;
   SingleListNode* pTail = 0;
   SingleListNode* pMid = 0;

   // Create and initialize a list.
   SingleList myList;
   myList.pHead = NULL;

   // Add some values to the list.
   insertInList(&myList, 7);
   insertInList(&myList, 5);
   insertInList(&myList, 3);
   insertInList(&myList, 9);
   insertInList(&myList, 6);
   insertInList(&myList, 2);
   insertInList(&myList, 4);

   // Retrieve nodes at the head, tail, and middle of the list.
   pHead = myList.pHead;
   pTail = myList.pHead;
   while (pTail->pNextNode)
       pTail = pTail->pNextNode;
   pMid = pHead->pNextNode->pNextNode;

   printList(&myList);
   removeFromList(&myList, pTail);
   printList(&myList);
   removeFromList (&myList, pMid);
   printList(&myList);
   removeFromList(&myList, pHead);
   printList(&myList);
}

If you have further questions or if this is unclear in any way, please just let me know.