Tuesday 24 January 2017

Program for single linked list

To store a group of data of same data type array data structure is used. But the problem with arrays is that the size of the array is fixed and it supports static memory allocation which may result in wastage of memory location. Another problem with array is that contiguous memory locations must be available.
An alternate data structure to arrays is linked list which follows dynamic memory allocation and elements need not be in contiguous memory location. To keep track of the next element, the address of the next element is stored in each node of the linked list. 
The following c program shows how to create a linked list and insert or delete elements in the linked list.

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
  int element;
  struct node *next;
}*list=NULL,*P;

struct node *find(int);
struct node *findprevious(int);
void insert(int X);
void delete(int X);
void display( );

void main( )
{
  int data,ch;
  
  clrscr( );
  printf("\n1.Insert\t2.Delete\t3.Display\t4.Exit");
  do
  {
    printf("\nEnter your choice:");
    scanf("%d",&ch);
    switch(ch)
    {
      case 1:
             printf("\nEnter the element to insert:");
             scanf("%d",&data);
             insert(data);
    break;
case 2:
    printf("\nEnter the element to delete:");
    scanf("%d",&data);
    delete(data);
    break;
case 3:
    display();
    break;
case 4:
    exit(0);
    }
  }while(ch<4);
getch();
}

void insert(int X)
{
  struct node *newnode;
  int pos;
  newnode=malloc(sizeof(struct node));
  newnode->element=X;
  if(list->next==NULL)
  {
    list->next=newnode;
    newnode->next=NULL;
  }
  else
  {
    printf("\nEnter the value after which the element to be inserted:");
    scanf("%d",&pos);
    P=find(pos);
    newnode->next=P->next;
    P->next=newnode;
   }
}

struct node *find(int s)
{
  P=list->next;
  while(P!=NULL&&P->element!=s)
  {
    P=P->next;
  }
  return P;
}

void delete(int X)
{
  struct node *temp;
  temp=malloc(sizeof(struct node));
  P=findprevious(X);
  if(P->next!=NULL)
  {
    temp=P->next;
    P->next=temp->next;
    printf("\nThe deleted element is %d",temp->element);
    free(temp);
  }
  else
  {
    printf("Element not found in the list");
  } 
}

struct node *findprevious(int s)
{
  P=list;
  while(P->next!=NULL && P->next->element!=s)
  {
    P=P->next;
  }
  return P;
}

void display()
{
  if(list->next==NULL)
  {
    printf("List is empty");
  }
  else
  {
    P=list->next;
    printf("\nThe contents of the list are:");
    while(P!=NULL)
    {
      printf("%d->",P->element);
      P=P->next;
     }
     printf("NULL");
  }
}

/*
OUTPUT
--------

1.Insert        2.Delete        3.Display       4.Exit
Enter your choice:1

Enter the element to insert:1

Enter your choice:1

Enter the element to insert:2

Enter the value after which the element to be inserted:1

Enter your choice:1

Enter the element to insert:3

Enter the value after which the element to be inserted:2

Enter your choice:3

The contents of the list are:1->2->3->NULL
Enter your choice:4

*/

No comments:

Post a Comment