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:)





 
 

What does FILE *fp means ??

What exactly does the following statement means?
'FILE *fp;
fp=fopen("filename","mode");'

Many of you might answer:we have declared a file pointer 'fp' which points to the file 'filename'.
But actually,this is not correct.

C has a special "data type" for handling files which is defined in the standard library 'stdio.h '.
It is called the file pointer and has the syntax FILE*.

First of all let me confirm you that **FILE is not a key word** , perhaps its a user defined data type defined in 'stdio.h' , presenting you the following code to justify my answer !

typedef struct {
int level; /* fill/empty level of buffer */
unsigned flags; /* File status flags */
char fd; /* File descriptor */
unsigned char hold; /* Ungetc char if no buffer */
int bsize; /* Buffer size */
unsigned char *buffer; /* Data transfer buffer */
unsigned char *curp; /* Current active pointer */
unsigned istemp; /* Temporary file indicator */
short token; /* Used for validity checking */
}FILE;

This is the structure stored in 'stdio.h' under the name FILE.This file pointer is just to store the composite information about a file subject to manipulation.These components specify certain things about the file to the operating system.
Thus, FILE, which contains all the information about the file, is subsequently used as a communication link between the system and the program.

Starting with the actual process which happens when we use 'FILE':
First of all,u all should know that while doing any operation on a file in C,we are not working on the actual file.
What happens is that the contents of the file we want to perform, are copied in a memory buffer.

and whenever we execute the above two statements, a structure as defined above is created,its elements are setup for the file referred and the base addresss of this srtucture is returned in pointer 'fp'.Thus,fp is not pointing to the file's buffer.
Within the structure to which fp is pointing,there is a character pointer called 'buffer'(refer to the structure).It is this pointer which points to the file's buffer.
It can be explained like this:
address of structure=1500 => address stored in fp=1500
address of file buffer=1700 => address stored in 'char *buffer'=1700

and we dont need to increment this 'buffer' pointer while using func such as getc().This is done by the function itself.To do this internally, operation of the form 'fp->buffer=fp->buffer+1' is done.

This whole information is a basic prerequisite if u want to start-up with using file i/o functions.

hope, this is helpful:)