Related Blog Items

• Detecting a loop in single linked list
• Circular Linked Lists
• Sorting a Linked List with QuickSort - Simple Algorithm
• Reversing a circular single linked list using pointers
• Reversing a double linked list

Linked Lists Basics
[Download this tutorial as , for updated conetnt and comments, generate a new pdf with the option which is present below the post] 

What are Linked Lists?
Linked lists store collections of data like arrays.  Linked lists are chain of records/nodes, one record/node points to the next. Record holds the data.

Why Linked Lists?
There are several  disadvantages with arrays, here are some…
1) The size of the array is fixed. Most often this size is specified at compile time however the size of the array can be deferred until the array is created at runtime (from heap), but after that it remains fixed. This causes to waste memory eventhough e may not use.
2) Inserting new elements at the front is potentially expensive because existing elements need to be shifted over to make room.
3)When array was full, to insert more data, it need to be resized, this operation is quite expensive, even may not be possible if in case memory got fragmented.
Linked lists performs well where arrays fail to do it.

What Linked Lists Look Like
An array allocates memory for all its elements lumped together as one block of memory. In contrast, a linked list allocates space for each element separately in its own block of memory called a "linked list element" or "node". The list gets is overall structure by using pointers to connect all its nodes together like the links in a chain. Each node contains two fields: a "data" field to store whatever element type the list holds for its client, and a "next" field which is a pointer used to link one node to the next node. Here is the graphical representation of linked list in fig1.

 

Empty Linked List
Empty list contains no nodes. The most common representation for the empty list is a NULL head pointer.

Linked List Type:
As we have discussed already linked list is chain of nodes. A node is a strcutre which holds data and pointer to the next node
Here is C structure for a node:

struct Node
{
  void* info; //data
  Node* next; //used to point to next node
};

Implementation Variants
There are a many variations on the basic linked list which have individual advantages over the basic linked list.
Without Special Nodes this implementation doesn’t use any special (head/dummy) nodes, empty list representation of this type of implementation is NULL. The advantage of this variant is, it doesn’t waste meory (it uses  all nodes), on other hand it complicates operations on lists a bit.
Head pointer in this implementation, we choose as a representation of the empty list a single "dummy" node whose .data field is unused. We call this node as head. The advantage of this technique is that it makes operations on the list easy on the other hand it wastes a node without using it.
Tail Pointer The list is not represented by a single head pointer. Instead the list is represented by a head pointer which points to the first node and a tail pointer which points to the last node. The tail pointer allows operations at the end of the list such as adding an end element or appending two lists to work efficiently.
Circular Instead of setting the .next field of the last node to NULL, set it to point back around to the first node. Instead of needing a fixed head end, any pointer into the list will do.
Doubly-Linked Instead of just a single .next field, each node incudes both .next and .previous pointers. Insertion and deletion now require more operations. but other operations are simplified. Given a pointer to a node, insertion and deletion can be performed directly whereas in the singly linked case, the iteration typically needs to locate the point just before the point of change in the list so the .next pointers can be followed downstream.
Circular  Doubly-Linked Instead of setting the .next field of the last node to NULL and .prev field of first node to NULL, set last node to point back around to the first node and first node .prev points to last node. This even simplifies and enhance efficiency of some operations doubly linked list.
Chunk List Instead of storing a single client element in each node, store a little constant size array of client elements in each node. Tuning the number of elements per node can provide different performance characteristics: many elements per node has performance more like an array, few elements per node has performance more like a linked list. The Chunk List is a good way to build a linked list with good performance.
Dynamic Array Instead of using a linked list, elements may be stored in an array block allocated in the heap. It is possible to grow and shrink the size of the block as needed with calls to the system function realloc(). Managing a heap block in this way is a fairly complex, but can have excellent efficiency for storage and iteration., especially because modern memory systems are tuned for the access of contiguous areas of memory. In contrast, linked list can actually be a little inefficient, since they tend to iterate through memory areas that are not adjacent.

Advantages and Disadvantages
Arrays:
1)Accessing/Searching : fast due to random access of any element in array (remember address of array element will be computed as base address + offset, so its just memory fetch along with one addition operation) — O(1)
2)Inserting/Deleting at end — fast — O(1)
3)Even sequential access on arrays are fast — due to locality of reference, for linked lists this may not well applied
1) The size of the array is fixed. Most often this size is specified at compile time however the size of the array can be deferred until the array is created at runtime (from heap), but after that it remains fixed. This causes to waste memory eventhough e may not use.
2) Inserting/Deleting  elements at the front is potentially expensive because existing elements need to be shifted over to make room — O(n)
3)When array was full, to insert more data, it need to be resized, this operation is quite expensive, even may not be possible if in case memory got fragmented.
Linked lists performs well where arrays fail to do it.
Linked Lists:
1)Accessing/Searching: sequential access -  O(n)
2)Inserting/Deleting at the end — fast — O(1)
3)Inserting/Deleting at the beginning — fast — O(1)
4)It makes good persistent data structure (because two or more lists can have a common tail, so several versions of a data can be maintained, new data comes at the beginning of a new list)
5)No space problems, memory effectively used.
6)Inserting/Deleting in the middle — O(n)
7)can not make use of locality of reference

Double Linked Lists:
1)More space for node
2)Complicates basic operations like insertion and deletion, however inserting/deleting any node will done in constant number of operations given that node address — O(1).
3)manipulating nodes are easy because provides access from both sides of the list
4)do not allow tail sharing, so can not be used as persistent data structures

Circular Linked Lists & Circular Double Linked Lists:
1)Can be traversed anywhere given any node in the list, which gives flexibility
2)Enahnces efficiencies of some operations
3)Complicates operations by inducing special cases to deal with circularity of list

Operations on Linked Lists:
Inserting node:

A node can inserted if we know the previous node’s address. Previous node’s next pointer altered to point to new node, new node’s next pointer points previous node’s next node.

//insert after a known node and return the inserted node
Node *insert(Node *after, void *data)
{
  Node* n;
  n = (Node *) malloc (sizeof(Node));
  n->info = data;
 
  //incase header node is not created
  if (!after)
  {
    n->next = after;
    return n;
  }
 
  n->next = after->next;
  after->next = n;
 
  return n;
}

Complexity: O(n)
Special Cases: inserting at beginning: O(1)

Deleting Node:

A node can deleted if we know the previous node’s address. Previous node’s next pointer altered to point to next next node, and previous node’s next node memory will be freed.

//delete after a known node and return the node after deleted node
Node *delete(Node *after)
{
  Node* tmp;
 
  if (!after || !(after->next))
  {
    return NULL;
  }
 
  tmp = after->next;
 
  after->next = tmp->next;
  free(tmp);
 
  return after->next;
 
}

Complexity: O(n)
Special Cases: Deleting at beginning: O(1)

Searching List:
Sequentially can all nodes.

//given any node in list, search entire list
Node *searchlist(Node *h, void *info)
{
  Node* after = h;
 
  //search all nodes after n (if any)
  while(after)
  {
    if (after->info == info)
    {
      return after;
    }
    after = after->next;
  }
 
  return NULL;
}

Complexity: O(n)

Length:
Finds out length of linked list.

int countnodes(Node *list)
{
  int i = 0;
 
  for (;list; list=list->next)
  {
    i++;
  }
 
  return i;
}

Complexity: O(n)

Printing List:
Sequentially print all nodes data.

//given a node in list, prints entire list after the node
int printlist(Node *h)
{
  Node* t = h;
 
  while(t)
  {
    printf(" %d ", t->info);
    t = t->next;
  }
 
  printf(" NULL\n");
  return 0;
}

Complexity: O(n)

Destroy List:
Free the memory for all nodes in the list.

destroylist(Node **n)
{
  Node * tmp;
 
  if (!n || !*n)
  {
    return;
  }
 
  while(*n)
  {
    tmp = (*n)->next;  
    free(*n);
    *n = tmp;
  }
}

Complexity: O(n)

Reversing List:
All the nodes point in reverse direction.

void reverse(struct node** headRef)
{
  Node* result = NULL;
  Node* current = *headRef;
  Node* next;
 
  while (current != NULL)
  {
    next = current->next; // tricky: note the next node
    current->next = result; // move the node onto the result
    result = current;
    current = next;
  }
  *headRef = result;
}

Complexity: O(n)

Merging Lists:
Two linked lists merged as one list and list pointer returned, all the duplicate nodes will be deleted.

//merge two single linked lists, eliminates duplicates 
//while merging
Node *mergelists(Node *list1, Node *list2)
{
  Node *list = list1;
  Node *mergedlist = list;
  Node *tlist = list;
  int dflag = 0;
 
  //just go to end of first list
  for (;list && list->next; list=list->next);
 
  for (;(list2 != NULL);)
  {
    dflag = 0;
 
    for (tlist=list1; tlist!=NULL; tlist=tlist->next)
    {
      if (tlist->info == list2->info)
      {
        dflag = 1;
        break;
      }
    }
 
    if (!dflag)
    {    
      list->next = list2;    
      list2 = list2->next;
      list = list->next;
      list->next = NULL;
    }
    else
    {
      tlist = list2;
      list2 = list2->next;
      //destroy duplicate node
      free(tlist);
    }
  }
 
  return mergedlist;
}

Complexity: O(n2)

Copying List:
Duplicates a linked list (nodes will be created if they do not exist in destination list, if they exist, only data will be copied).

Node *copylist(Node **dst, Node *src)
{
  Node *tmp, *t, *copiedlist;
 
  if (!src)
  {
    return NULL;
  }
 
 
  //create node if dst doesn't have a node, 
  //otherwise copy node's data into dst's node
  if (!dst || (dst && !*dst))
  {
    tmp = (Node *) malloc(sizeof(Node)); 
    tmp->next = NULL;
  }
 
  if (dst && !*dst)
  {
    if (!*dst)
    {
      *dst = tmp;
    }
    else
    {
      tmp = *dst;
    }
  }
 
  copiedlist = tmp;
 
  //treat copying first node as special case
  tmp->info = src->info;
  src = src->next;
 
  //now copy rest of the nodes
  while(src)
  {
    if (!tmp->next)
    {
      //create node only if node doesn't exist in destination list
      t = (Node *) malloc(sizeof(Node));
      t->next = NULL;
    }
    t->info = src->info;
    tmp->next = t;
    tmp = tmp->next;
    src = src->next;
  };
 
  return copiedlist;
}

Complexity: O(n)

Equals:
Find out whether two linked lists are same.

int equals(Node *list1, Node *list2)
{
   int found = 1;
   Node *tmp = list2;
 
   if (!list1 && !list2)
   {
     //empty lists. huh!
     return 1;
   }
   else if (!list1 || !list2)
   {
     //not equal
     return 0;
   }
 
   while(list1)
   { 
     if (list2->info == list1->info)
     {
       list1 = list1->next;
       list2 = list2->next;
     }
     else
     {
       found = 0;
       break;
     }
   }
   return found;
}

Complexity: O(n)

Removing Duplicates:
Removes duplicate nodes in the list. This operation first performs sorting on list, then removes duplicate nodes.

Node *bubblesort(Node *list)
{
  Node *lst, *tmp = list, *prev, *potentialprev = list;
  int idx, idx2, n = 0;
 
  //determine total number of nodes
  for (;tmp->next; tmp=tmp->next)
  {
    n++;
  }
 
  for (idx=0; idx<n-1; idx++) 
  {
    for (idx2=0,lst=list; 
         lst && lst->next && (idx2<=n-1-idx);
         idx2++)
    {
      if (!idx2)
      {
        //we are at beginning, so treat start 
        //node as prev node
        prev = lst;
      }
 
      //compare the two neighbors
      if (lst->next->info < lst->info) 
      {  
        //swap the nodes
        tmp = (lst->next?lst->next->next:0);
 
        if (!idx2 && (prev == list))
        {
          //we do not have any special sentinal nodes
          //so change beginning of the list to point 
          //to the smallest swapped node
          list = lst->next;
        }
        potentialprev = lst->next;
        prev->next = lst->next;
        lst->next->next = lst;
        lst->next = tmp;
        prev = potentialprev;
      }
      else
      {
        lst = lst->next;
        if(idx2)
        {
          //just keep track of previous node, 
          //for swapping nodes this is required
          prev = prev->next;
        }
      }     
    } 
  }
  return list;
}
 
void deleteduplicates(Node *list)
{
  Node *tmp;
  list = bubblesort(list);
 
  for(;list && list->next;list=list->next)
  {
    if (list->info == list->next->info)
    {
      //duplicate
      tmp = list->next;
      list->next = list->next->next;
      free(tmp);
    }
  }
}

Complexity: O(n2)

Download full source code from
HERE

You can find more advanced and detailed topics on individual variants of basic linked list and some operations on them here..

Double Linked List

Circular Double Linked List

Reversing linked list using pointers

Reversing Linked list recursively

Reversing Linked List using Stack

Reversing Circular Linked List

Reversing Double Linked List

Detecting Broken Links in double linked list

Sorting Linked List with Bubble Sort

And all linked list related topics can be found under

Data Structures category..

Let me know your comments..

Popularity: 26%

You need to log on to convert this article into PDF

Related Blog Items

• Detecting a loop in single linked list
• Circular Linked Lists
• Sorting a Linked List with QuickSort - Simple Algorithm
• Reversing a circular single linked list using pointers
• Reversing a double linked list

This entry was written by ponnada and posted on April 12, 2007 at 2:55 pm and filed under C Tidbits, Data Structures in C/C++, Pointers & Callbacks, Tutorials. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.