Thursday, January 12, 2012

Getting started with LINKED LISTS

In this post, I will be discussing about basic operations in linked lists, basically inserting an element(at the end or beginning),deleting the same & printing the list(in a 'programmer's' fashion).I shall not be covering the basic concepts in the operations, rather just covering the main stuff.
So, let’s start with a brief introduction of 'linked list':
A linked list is basically a collection of entities, which are a collection of dissimilar data-types. These entities are linked to each other (each to its next one) through pointers of the same data-type. The end of this list is marked by the 'next' pointer of an entity, pointing to a 'NULL'.
Throughout the post, i will be talking about the following structure:
typedef struct nod
{
      int n;
      struct nod *next;
}node;
//typecasting the name 'struct nod' to 'node'.
And, I have taken a dummy node first (why?, u will get to know after going through the post).
So, what I have now, is a linked list with a single dummy node, having no value & whose next pointer is pointing to NULL.


Ok, time to expand our list, presenting straightaway the function which inserts the no's at the end of the list:
void insert_rec(node *start,int x)
{
      if(start->next==NULL)
      {
            start->next=(node *)malloc(sizeof(node));
            start->next->next=NULL;
            start->next->n=x;
            return ;
      }
      insert_rec(start->next,x);
}
In this, we are traversing the list till the end,i.e. till we encounter that next pointer is pointing to NULL, through 'recursion'.When the same is encountered,we are assigning the memory(equal to the structure) to generate the next node and then, assigning the no. and maintaining the terminating condition.
We can perform this without recursion also, as the following code for entering the no at the beginning demonstrates:
void insert_beg(node *start,int x)
{
      node *temp;
      temp=(node *)malloc(sizeof(node));
      temp->next=start->next;
      temp->n=n;
      start->next=temp;
}
Now this is where dummy node comes into play.Initially, the start pointer is pointing to the dummy node.So, the only thing we have to do is to enter the element between the dummy node and rest of the list.So, we are taking another block of memory, providing it required specifications and just making the appropriate changes in the links.After this, perhaps, u can appreciate the idea of dummy node.

But, to prevent some of you becoming "emotional”, let me clear you that we CAN do it without dummy node, but then, we will have to use double pointer,i.e. we will have to pass the address of the head node to the node, so as to 'change the head pointer' after inserting the new node. Following code explains it well:
void in_beg(node **start,int x)
{
      node *temp;
      temp=(node *)malloc(sizeof(node));
      temp->next=*start;
      temp->n=x;
      *start=temp;//shifting the head pointer
}

Now, which of the two functions is better, depends on your perception.
Similar code for inserting the elements at the end will be:
void insert(node **start,int num)
{
      node *temp,*r;
      if(*start==NULL)
      {
            temp=malloc(sizeof(node));
            temp->next=NULL;
            temp->n=num;
            *start=temp;
            printf("<%d>\n",temp->n);
      }
      else{
      temp=*start;
      while(temp->next)//similiar to (temp->next!=NULL)
            temp=temp->next;
      temp->next=(node*)malloc(sizeof(node));
      temp->next->next=NULL;
      temp->next->n=num;
      }
}
I think there is no need to explain this func,still if any of you has a doubt, can post in comments.

Enough with inserting I think, it’s time to delete now!!

But before deleting, let’s check if we have made our list correctly (of course we have, trust me!).
But only for those emotional people, let’s check it man..
void print(node *start)
{
      start=start->next;//for passing the dummy node
      while(start!=NULL)
      {
            printf("%d",start->n);
            start=start->next;
      }
      printf("\n");
}
This will print the list,BUT it's a quite simple function I think, lets modify it a little bit. Check this out:
void print(node *start)
{
     start=start->next;
    while(start && printf("%d ",start->n))        
       start=start->next;
      printf("\n");
}

This function uses some more facts, apart from linked lists:1.Usage of '&&' operator(lazy evaluation in C)
                                              2.return value of printf
This you all must know that, "a printf function returns the length of the string which is to be printed".So,as long as there is some no. in start->n,it will return a non-zero value and this will continue till the NULL is encountered.Therefore,first printf will be executed, the value will be returned to '&&' operator.
So, what is lazy evaluation?
In C,if the first expression in '&&' operator returns a 'zero' value, then the second condition is not even evaluated and the operator ofcourse,returns a zero value.                
But WHY we need this?
It is because after traversing the list,when the start pointer is pointing to NULL,the printf still tries to print 'start->n',i.e. tries to access the NULL, which is not allowed, resulting in the most common error in structure handling-"segmentation fault".But,when we '&&' it with start, at this situation, it will return a zero value, and therefore the printf will not be executed.
So, start should come first in '&&' operator(U can check by reversing the order)

                       
Finally, time to free some of our precious memory.
The function to delete is rather a simple one, but needs to be dealt carefully.
Following code demonstrates deleting from  beginning and the end:
void delete_beg(node *start)
{
      node *temp;
      temp=start->next;
      start->next=start->next->next;
      free(temp);
}
void delete_end(node *start)
{
      while(start->next->next!=NULL)
                  start->next=start;
      node *temp;
      temp=start->next;
      start->next=start->next->next;
      free(temp);
}
The shifting of the links, I think, do not needs an explanation.Deleting from beginning makes use of 'dummy' node, as in inserting. But yes, here again, we can use a double pointer to perform the same.
void del_beg(node **start)
{
      node *temp;
      temp=*start;
      (*start)=(*start)->next;
      free(temp);
}
The 'free' function is use to free a specific block of memory.

What if we biasly want to delete a particular node?  nothing, refer to the next function:->
void delete(node *start,int x)
{
      while(start->next && (start->next)->n!=x)
            start=start->next;
      if(start->next)
            return;
      node *temp=start->next;
      start->next=(start->next)->next;
      free(temp);
}
The only thing we need to do is-first, reach that node(the extra condition in while) & delete it! and make sure that you don't cross the NULL(if you do reach the NULL, just return the pointer).

So, these were some of the operations to get started with linked lists. In the next post,I will be covering some advanced operations, like sorting a list,reversing,merging two sorted lists..

Hope, this is helpful:)





 
 

No comments: