Header linked list

Definition-

A header linked list is a type of linked list which always contains a special node called the header node at the very beginning of the linked list.It is an extra node kept at the front of a list.

Such a node does not represent an item in the linked list.The information part of this node can be used to store any global information about the whole linked list.

 

Source-pages.cs.wisc.edu

Advantages of having a header node-  

• In header node, you can maintain count variable which gives number of nodes in the list. You can update header node count member whenever you add /delete any node. It will help in getting list count without traversing in O(1) time.
• In addition to address of first node you can also store the address of last node. So that if you want to insert node at the rear end you don't have to iterate from the beginning of the list. Also in tcase of DLL(Doubly Linked List) if you want to traverse from rear end it helps.
• We can also use it to store the pointer to the current node in the linked list which eliminates the need of an external pointer during the traversal of the linked list.
• While inserting a new node in the linked list we don't need to check whether start node is null or not because the header node will always exist and we can insert a new node just after that.

Operations on a header linked list such as insertion, deletion are same as singly list.The only difference will be that we have to create header node first whose data field will be null initially and after that we can perform any operations on that linked list and store the global information about the linked list on the header node.

Header linked list in C- 

Here is a basic c program for header linked list, in this we are performing three operations and in each operation we can see the use of header node.

• Insert at start-  

  We don't need to check whether start node is null or not.We can start adding node after header node.

• Insert at end-

  We don't need start pointer to reach the end node.We can use header node data to reach the end node.

• Insert  given position-

  We don't need a for or while loop to check whether position is valid or not. We can check this by using header data.If position is greater then header data then it is invalid else it is valid.
  
  

  #include<stdio.h>
  #include<stdlib.h>
  int count=0;
  //structure of a single node 
  //we are also creating two nodes start and header
  
  struct node{
   int data;
   struct node* next;
  }*start,*header;
  
  //function to print the list
  void print()
  {
   struct node *p=start;
   while(p!=NULL)
   {
    printf("%d->",p->data);
    p=p->next;
   }
   printf("\n");
  }
  
  //insertion at the front of the header linked list
  //we can see that we don't need to check whether
  //start is null or not because there will always be a
  //header node
  
  void insert_at_front(int node_data)
  {
   struct node *p;
   p=(struct node *)malloc(sizeof (struct node));
   p->data=node_data;
   p->next=header->next;
   start=p;
   //header will always point to start
   header->next=start;
   //increase the node counter
   count++;
   //store the count value in header
   header->data=count;
   
   printf("after inserting at the front=\n");
   print();
  }
  
  
  
  void insert_at_end(int node_data)
  {
   struct node *p=start,*q;
   //create a new node to insert at last
   q=(struct node *)malloc(sizeof (struct node));
   q->data=node_data;
   q->next=NULL;
   //store header->data in temp for while loop
   int temp=header->data; 
   //loop to reach last node
   //we can see that we are directly using header node's data
   //to reach the last node
   while(temp>1)
   {
    p=p->next;
    temp--;
   }
   p->next=q;
   count++;
   header->data=count;
   printf("after inserting at the end=\n");
   print();
  }
  
  //function to insert after given position
  void insert_after(int pos,int node_data)
  {
   //we can see that we don't need to check the whole list
   //whether position is valid or not, we can directly use header data
   if(pos>header->data)
    printf("we can not found the position\n");
   else{
    struct node *p,*q=start;
    p=(struct node *)malloc(sizeof (struct node));
    p->data=node_data;
    p->next=NULL;
    while(pos>1)
    {
     q=q->next;
     pos--;
    }
    p->next=q->next;
    q->next=p;
    count++;
    header->data=count;
   }
   printf("after inserting after given position=\n");
   print();
  }
  int main()
  {
   header=(struct node *)malloc(sizeof (struct node));
   start=(struct node *)malloc(sizeof (struct node));
   //initially header node conatains no data
   header->data=count;
   header->next=NULL;
   insert_at_front(3);
   insert_at_front(4);
   insert_at_end(5);
   insert_at_end(8);
   insert_after(2,7);
  return 0;
  }
  

  OUTPUT-

  after inserting at the front=
  3->
  after inserting at the front=
  4->3->
  after inserting at the end=
  4->3->5->
  after inserting at the end=
  4->3->5->8->
  after inserting after given position=
  4->3->7->5->8->