linked lists

Searching in Linked List

http://install4install.com

In searching,we find whether the given element is present in the linked list or not.The following program is to search for particular element in linked list.

Program

#include<stdio.h>
struct node
{
    int item;
    struct node *next
};
int main()
{
    struct node *start,*list,*temp;
    int i;
    int num;
    start = (struct node *)malloc(sizeof(struct node));
    list = start;
    start->next = NULL;
    for(i=1;i<5	;i++)
    {   
        list->item = i;
        list->next = (struct node *)malloc(sizeof(struct node));
        list = list->next;
       }
    list->next = NULL;
//printf("Enter the element");
scanf("%d",&num);
temp =start;
 while(temp!=NULL)//Fig2
  {
    if(temp->item == num)
    {
    	printf("%d is present\n",num);
    }
    temp = temp->next;
  }
  printf("Elements of linked lists are:\n");
  while(start != NULL)
    {   
    	if (start->next == NULL) 
    	  {
           break;
    	  }
        printf("%d\n",start->item);
        start = start->next;
    } 
return 0;
}

Run

 

Illustration of Program

  • Refer Linked Lists for creation and display of linked list.
  • temp =start which means temp =140(Fig 1)
  • Say we want to find whether 300 is present in linked list or not.
Screen Shot 2014-04-07 at 1.48.39 PM

Fig 1 : Searching in Linked List

Screen Shot 2014-04-07 at 6.45.25 PM

Fig 2 :Working of Program


Short URL: http://tinyit.cc/dc4848
By Cusp2207 on April 8, 2014 | Computer Science | 1 comment
Tags:

Count number of nodes in Linked List

Counting refers to calculating number of nodes present in linked list.

Counting

Counting

Program

#include<stdio.h>
struct node
{
    int item;
    struct node *next
};
int main()
{
    struct node *start,*list,*temp;
    int i;

    start = (struct node *)malloc(sizeof(struct node));
    list = start;
    start->next = NULL;
    for(i=1;i<5;i++)
    {   
        list->item = i;
        list->next = (struct node *)malloc(sizeof(struct node));
        list = list->next;
       }
    list->next = NULL;
    temp = start;
    int length =0;
    while(temp!=NULL)//Fig 2
    {

    	if (temp->next == NULL) 
    	  {
           break;
    	  }
         else
        {
        length++;
        temp=temp->next;
        }
    }    

printf("Length of Linked List : %d \n",length);
printf("Elements of linked lists are :\n");
   while(start != NULL)
    {   
    	if (start->next == NULL) 
    	  {
           break;
    	  }
        printf("%d\n",start->item);
        start = start->next;
    } 
return 0;
}

Run

Illustration of Program

  • Refer Linked Lists for creation and display of linked list.
  • temp = start which means temp =140(Fig 1)
Screen Shot 2014-04-07 at 1.48.39 PM

Fig 1 : Linked List

Screen Shot 2014-04-07 at 2.14.02 PM

Fig 2 : Working of Program


Short URL: http://tinyit.cc/e0eb10

Deletion in Linked List

The elements of linked list can be deleted in three ways.

  • Deletion at beginning
  • Deletion at end
  • Deletion at any location

Program 1

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *next;
}*head,*var,*trav;

int del_beg()
{
struct node *temp,*start;

temp = start;
start = start->next;
free(temp);
printf("nThe Element deleted Successfully ");
}
int delete_from_middle(int value)
{
     struct node *temp,*var;
     temp=head;
     while(temp!=NULL)
     {
          if(temp->data == value)
          {
                if(temp==head)
                {
                     head=temp->next;
                     free(temp);
                     return 0;
                }
                else
                {
                     var->next=temp->next;
                     free(temp);
                     return 0;
                }
          }
          else
          {
               var=temp;
               temp=temp->next;
          }
     }
printf("data deleted from list is %d",value);
}
int delete_from_end()
{
     struct node *temp;
     temp=head;
     while(temp->next != NULL)
     {
          var=temp;
          temp=temp->next;
     }
     if(temp ==head)
     {
          head=temp->next; 
          free(temp);
          return 0;
     }
     printf("data deleted from list is %d",temp->data);
     var->next=NULL;
     free(temp);
     return 0;
}
void display()
{
     trav=head;
     if(trav==NULL)
     {
          printf("\nList is Empty");
     }
     else
     {
          printf("\nElements in the List: ");
          while(trav!=NULL)
          {
               printf(" -> %d ",trav->data);
               trav=trav->next;
          }
      printf("\n");
      }
}
int main()
{
     int i=0;
     head=NULL;
     while(1)
     {
           printf("\nenter the choice of operation to perform on linked list");
           scanf("%d",&i);
           switch(i)
           {
           		 case 1:
                {
                del_beg();
                display();
                break;
                }

                case 2:
                {
                delete_from_end();
                display();
                break;
                }
                case 3:
                {
                int value;
                display();
                printf("\nenter the data that you want to delete from the list shown above");
                scanf("%d",&value);
                delete_from_middle(value);
                display();
                break;
                }
                case 6:
                {
                exit(0);
                }
           }
      }
return 0;
}

Run

 

 

Illustration of Program 1

  • node is the name of structure.
  • data refers to element of linked list.
  • *next points to subsequent address of linked list.
  • *head points to first node of list.
  •  *var refers to the node.
  •  *trav refers to the node.

Working of  int del_beg()

  • *temp and *start are pointers of structure.
  •   temp =start (Fig 1) – Value of start is stored in temporary pointer.
Fig 1 : Linked List

Fig 1 : Linked List

 

  • start =start ->next – The start pointer will move one position ahead i.e it will point to 2.(Fig 2)
Fig 2 :Working of start = start ->next

Fig 2 :Working of start = start ->next

  • free(temp) – Deletes the temp node(node at beginning of linked list)(Fig 3)
Fig 3 : Deletion at front

Fig 3 : Deletion at front

 

Working of  int delete_from_middle(int value)

  • *temp and *var are pointers of structure.
  • temp = head – Value of head is stored in temp (Fig 4)
  • Refer Fig 5 for working of function.
Screen Shot 2014-04-04 at 3.35.56 PM

Fig 4 : Linked List

 

 

 

 

 

 

Screen Shot 2014-04-04 at 4.15.52 PM

Fig 6 :Working of while loop

 

Screen Shot 2014-04-04 at 4.03.40 PM

Fig 7 : Deletion at any location

 

Working of int delete_from_end()

  • *temp and *var are pointers of structure.
  •  temp = head ;(Value of head is stored in temp)
Screen Shot 2014-04-04 at 3.35.56 PM

Fig 8 : Linked Lis

 

Screen Shot 2014-04-04 at 4.45.04 PM

Fig 9 : Working of while loop

 

 

Screen Shot 2014-04-04 at 4.38.15 PM

Fig 10 : Deletion at end

 

  • main function is used to call the functions.The function is called using cases of switch statement.

Short URL: http://tinyit.cc/9d848
By Cusp2207 on April 4, 2014 | Computer Science | A comment?
Tags:

Insertion in Linked List

There are three ways to insert element in the linked list.

  • Insertion in the beginning

  • Insertion at the end

  • At any location of user choice

The following program deals with insertion in linked list.

Program 1

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int data;
    struct node *next;
}   *head,*var,*trav;

void insert_at_begning(int value)
{
     var=(struct node *)malloc(sizeof (struct node));
     var->data=value;
     if(head==NULL)
     {
         head=var;
         head->next=NULL;
     }
     else
     {
         var->next=head;
         head=var;
     }
}

void insert_at_end(int value)
{
      struct node *temp; 
      temp=head;
      var=(struct node *)malloc(sizeof (struct node));
      var->data=value;
      if(head==NULL)
      {
          head=var;
          head->next=NULL;
      }
      else
      {
          while(temp->next!=NULL)
          {     
               temp=temp->next;
          }
          var->next=NULL;
          temp->next=var;
      }
}
void insert_at_middle(int value, int loc)
{
     struct node *var2,*temp;
     var=(struct node *)malloc(sizeof (struct node));
     var->data=value;
     temp=head;
     if(head==NULL)
     {
          head=var;
          head->next=NULL;
     }
     else
     {
          while(temp->data!=loc)
          {
                temp=temp->next;
          }
          var2=temp->next;
          temp->next=var;
          var->next=var2;
     }
}
void display()
{
     trav=head;
     if(trav==NULL)
     {
          printf("\nList is Empty");
     }
     else
     {
          printf("\nElements in the List: ");
          while(trav!=NULL)
          {
               printf(" -> %d ",trav->data);
               trav=trav->next;
               break;
          }
      printf("\n")
      }

}
int main()
{
     int i=0;
     head=NULL;
     while(1)
     {
           printf("\nenter the choice of operation to perform on linked list");
           scanf("%d",&i);
           switch(i)
           {
                case 1:
                {
                 int value;
                 printf("\nenter the value to be inserted");
                 scanf("%d",&value);
                 insert_at_begning(value);
                 display();                
                 break; 
                }
                case 2:
                {  
                int value;
                printf("\nenter value to be inserted");
                scanf("%d",&value);
                insert_at_end(value);
                display();
                break;
                }
                case 3:
                {
                int value,loc;
                printf("\nafter which data you want to insert the data");
                scanf("%d",&loc);
                printf("\nenter the value to be inserted");
                scanf("%d",&value);
                insert_at_middle(value,loc);
                display();
                break;
                }
                case 6:
                {
                exit(0);
                }
           }
      }
return 0;
}

 

Run

 

Illustration of Program

  • node is the name of structure.
  • data refers to element of linked list.
  • *next points to subsequent address of linked list.
  • *head points to first node of list.
  •  *var refers to the node.
  • *trav refers to the node.

Explanation of function –> void insert_at_beginning(int value)

Fig 1 : Insert at front

Fig 1 : Insert at front

 

Screen Shot 2014-04-04 at 11.25.01 AM

Fig 4 :Working of void insert_at_beginning

 

 

Explanation of function –>void insert_at_end(int value)

Screen Shot 2014-04-07 at 11.41.22 AM

Fig 3 : Insert at End

 

Screen Shot 2014-04-04 at 11.57.32 AM

Fig 5 : Working of insert_at_end()

 

 

Explanation of  void insert_at_middle(int value, int loc)

Screen Shot 2014-04-04 at 12.18.33 PM

Fig8 : Working of insert_at_middle()

 

  • Display function is used to display the value inserted in linked list.
  • switch cases are defined in main and functions are called in different  switch cases .

Short URL: http://tinyit.cc/fc0e8c

Linked Lists

Linked Lists is the data structure which stores data elements  in a sequence.Each data element is called a Node.Each node further contains data field/fields and a pointer(Refer :Pointers ) to next node(Fig 1).

The  left part  of node has data item and the right part of node has the address of succeeding node.The  address of elements may be  sequential or may be not.START  node has the address of first node .The last node of linked list has  NULL  in the right part.NULL value indicates the  end of list.Chain of nodes is formed using this method.

TipIf  START = NULL ,it means that linked list does not contain any node and the list is empty.

Fig 1 : Linked Lists

FIG 2: A Linked List

Fig 2: A Linked List

In Fig 2,START  stores the address of first node(40).Nodes are at address 40,45,50,65  respectively.10,20,30,40 are the data elements in the left part .45 in first node points to second node at 45 address,50 in second points third node which is at location 50,65 in fourth part points to last node which further does not points to anything.i.e. the last node of list.

 

Implementation of Linked List

Linked lists are implemented in C through structures(Refer :Structures).

Syntax

struct node//Fig 3
{
int data_item;
struct node *link
};
  • node is the name of structure.
  • data_item of int type refers to element of linked list.
  • *link  is a pointer variable of structure .
Fig 3 : A Linked List

Fig 3 : A Linked List

Traversing a Singly Linked List

Program 1

#include<stdio.h>
struct node
{
    int item;
    struct node *link
};

int main()
{
    struct node *start,*list;
    int i;
    start = (struct node *)malloc(sizeof(struct node)); //Refer Program 2 for working of this statement.
    list = start;
    start->link = NULL;
    for(i=0;i<5;i++)
    {   
        list->item = i;
        list->link = (struct node *)malloc(sizeof(struct node));
        list = list->link;
    }   
    list->link = NULL;
    while(start != NULL)
    {   
        printf("%d\n",start->item);
        start = start->link;
    }  
    return 0;
}

Run

 

 

Illustration of Program

  • node is the name of structure.
  • item of int type refers to element of linked list.
  • *link is a pointer variable of structure used to point to next address.
  • *start and *list refers to pointer variables of structure.
  • The function malloc is used to allocate a certain amount of memory during the execution of a program. The malloc function will request a block of memory from the heap. If the request is granted, the operating system will reserve the requested amount of memory.
  • malloc allocates sizeof(struct node) bytes, and returns a void pointer to it, which we cast to  struct node *.
  • start points to the first node of linked list.

Working of Program 1

Screen Shot 2014-04-02 at 5.06.32 PM

Fig 4 : Working of Program1

Program 2

#include<stdio.h>
struct node
{
    int item;
    struct node *link
};

int main()
{
    struct node *start,*list;

    start = (sizeof(struct node));
    printf("%d\n",start);
    start =malloc(sizeof(struct node));
     printf("%d\n",start);
     start =  (struct node*) printf("%d",start);
     printf("%d\n",start);
     return 0;
};

Run

 

 

Practical applications of linked list

  • A list of images that need to be burned to a CD in a medical imaging application
  • A list of users of a website that need to be emailed some notification
  • A list of objects in a 3D game that need to be rendered to the screen

Short URL: http://tinyit.cc/c9e284