program 66: working with linked lists using user defined functions

The need:
     This program is the same previous program written using User Defined Functions (UDFs). This program takes some numbers from the user stores them in nodes (creates linked list) and prints back for the user in the same order. So this program teaches us creating and accessing linked lists.

The code:  
--------------------------------------------

#include<stdio.h>
#include<stdlib.h>
struct node1
{
 int data;
 struct node1 *next;
};
typedef struct node1 node; //defining a datatype node
void printlist(node *p); //udf to print list
void add_node(int a,node *p); //udf to add node to last of list
node *create_node(int); //udf to create a new node
int main()
{
 int i,j;
 node *head; //head will be first node of list
 head=NULL; //initialising head to null
 printf("Enter numbers to be stored. enter -999 to end.\n");
 while(i!=-999) //this while loop takes the numbers and creates list
 { //loop runs untill user enters -999
  scanf("%d",&i);
  if(head==NULL) //if i is first node
  head=create_node(i); //creates a new node and assigns its address to head
  else
  add_node(i,head);
 }
 printf("All the  numbers has been entered into linked list.\n");
 printf("press any key to view the list\n");
 fflush(stdin); //to flush previous undesired inputs from keyboard
 getchar(); //to give a pause to program untill user press any key
 printf("\nThe list is\n\n");
 printlist(head); //UDF to print the linked list
 printf("\n");
 return 0;
}

void printlist(node *p)
{
 node *temp=p;
 while(temp->next!=NULL) //this loop prints the list
 {
  printf("%d-->",temp->data); //printing current member
  temp=temp->next; //jumping to next member in the list
 }
  printf("END");
}

void add_node(int a,node *p)
{
 node *temp1,*temp2;
 temp2=p;
 /*the case when temp1 is not first node, we have a list of some members.
   Its kind of a line of persons in which a newcomer has to stand at the last
   so we have to go to last position starting from first*/
 temp1=create_node(a);
 while(temp2->next!=NULL) //checking if temp2 is last node
  temp2=temp2->next; //loop exits if temp2 is last node
 temp2->next=temp1; //temp1 is appended to the list after last node
}

node *create_node(int b)
{
 node *temp1;
 temp1=(node*)malloc(sizeof(node)); //allocation of a temporary node
 temp1->data=b; //filling data in node
 temp1->next=NULL; /*making pointer to next location NULL
 because there is no next location till now*/
 return temp1; //return 
}

--------------------------------------------  

The approach:  
The approach is very simple once you have read previous post. Everything has been written near statements as comments. Still this is a new topic so in case of any doubt please let me know. Now onward I'll use UDFs to do deal with linked lists.

program 65: using linked lists

The need:
     This program is written just to show the use of linked lists. This program takes some numbers from the user stores them in nodes (creates linked list) and prints back for the user in the same order. So this program teaches us creating and accessing linked lists.

The code:  
--------------------------------------------

#include<stdio.h>
#include<stdlib.h>
struct node1
{
    int data;
    struct node1 *next;
};
typedef struct node1 node; //defining a datatype node
int main()
{
    int i,j;
    node *head,*temp1,*temp2; //declaring 3 pointers of type node
    head=NULL; //initialising head to null
    printf("Enter numbers to be stored. enter -999 to end.\n");
    while(i!=-999) //this while loop takes the numbers and creates list
    {    //loop runs untill user enters -999
        scanf("%d",&i);
        temp1=(node*)malloc(sizeof(node)); //allocation of a temporary node
        temp1->data=i; //filling data in node
        temp1->next=NULL; /*making pointer to next location NULL
        because there is no next location till now*/
        if(head==NULL) //the case when temp1 is very first node
        {
            head=temp1; //so head will be containing the address of first node permanently
            temp2=head; //temp2 is temporarily given address of first node
        }
        else /*the case when temp1 is not first node, we have a list of some members.
        Its kind of a line of persons in which a newcomer has to stand at the last
         so we have to go to last position starting from first*/
        {
            while(temp2->next!=NULL) //checking if temp2 is last node
            temp2=temp2->next; //loop exits if temp2 is last node
            temp2->next=temp1; //temp1 is appended to the list after last node
        }
    }
    printf("All the  numbers has been entered into linked list.\n");
    printf("press any key to view the list\n");
    fflush(stdin); //to flush previous undesired inputs from keyboard
    getchar(); //to give a pause to program untill user press any key
    printf("\nThe list is\n\n");
    temp2=head;
    while(temp2->next!=NULL) //this loop prints the list
    {
        printf("%d-->",temp2->data); //printing current member
        temp2=temp2->next; //jumping to next member in the list
    }
    printf("\n");
    return 0;
}

 --------------------------------------------  

The approach:  
The approach is very simple once you have read previous post. Everything has been written near statements as comments. Still this is a new topic so in case of any doubt please let me know.

Concept of linked lists in C

     You have seen dynamic allocation of memory in C. But that was only introduction. How this is implemented in real life is shown in this post. Imagine the case of scanning some numbers and storing in memory. Now you know that there is something called dynamic memory allocation so you can use that instead of declaring a large array at the start of the program. You can think of scanning a number, then allocating memory for that number and then putting the number in the allocated memory space and repeating the same procedure for next numbers if needed. Your thinking is very good and apreciable but there is a problem that you can face. That is how you will keep track of each and every location allocated dynamically during the execution of the program.

     One solution which can come to your mind is just keep track of first location (just store it's address in a pointer variable) and store address of next location beside it. So this is the situaation in which you dont  This solution is also globally accepted. For this purpose you can create a derrived data-type which would contain a number (or may be more data depending on your need) and a pointer variable to hold the address of next location of data. This pointer is a link between the two nodes ( Each location can be said a node.) This is why these are called linked lists.

     To give you more clear idea of linked lists let me give an analogy. Lets compare arrays and linked lists. An array can be thought as a line of persons so any viewer can easily tell the location of any particular person in the line. He can also judge next person just by seeing the line and the current person because its very obvious. On the other hand linked lists can be think of a bunch of persons which are scattered here and there in a place and every person knows who is the person next to him. No outsider can say anything about their order. In the same way if you want to go to 3rd member of linked list then first of all go to first member take address of second from there, go to second take address of 3rd from there and then go to 3rd. Each time you have to start from first member and then proceed towards the desired member by going through intermediate members.

Remarks:

when you realize that you have got some command on linked list concepts after going through next 3-4 programs, you can have a look on program78 of this blog. This is a good program combining various operations on linked lists.

Data structures in C

You people have seen varius types of structure and derrived data types. You are also familiar to file handling, pointers and arrays. All these things are clearly visible in the source code of the program. There are certain more concepts which are called popular data-structures which are:
1. linked lists
2. queues
3. The stack
4. trees

   Now dont worry about these things. Just read its once and proceed. Concept of linked list has been explained in the next post.Queues, stack, and trees are just three different implementations of linked lists. Those will be explained later in subsequent posts. Just wait for it.

program 64: use of pointer as array

The need:
     This is a simple program to show that pointer is equivalent to a one dimensional array of same datatype and how a pointer variable can be used as an array.

The code:  
-------------------------------------------- 

#include<stdio.h>
#include<stdlib.h>
#define max 5
main()
{
  int i;
  int *p,*q;
  p=(int *)malloc(max * sizeof(int));
  q=p;
  printf("Enter %d integers\n",max);
  for(i=0;i<max;i++)
  {
   printf("Enter number %d =>\t",i);
   scanf("%d",p++);
  }
  printf("\nyou entered\n");
  for(i=0,p=q;i<max;i++)
  {
   printf("%d whose address is %d\n",*p,p);
   p++;
  }
  return 0;
}

--------------------------------------------  

The approach:  
This program takes 5 integers from user, store them in memory and prints back for user. This is a trivial task. Here I have shown how a pointer variable (in our case p) can be used  as an array of integers. This can be done for other data-types and even with derrived datatypes. First of all the pointer p is initialised and allocated sufficient memory (here using malloc function). After that five integers are scanned one by one and each time pointer p is incremented. In each increment p is automatically set to point to the next integer location in the memory. The initial value of p (starting location of array) is temporarily stored in other variable q. Which is later used to access the array to print it.