Singly Linkedlist in C/C++

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.




A sample C program about various operations on a Singly Linkedlist :
1. Creation
2. Insertion
3. Deletion
4. Traversing
5. Searching
6. Sorting


#include<stdio.h>
#include<conio.h>
#include<malloc.h>
 
struct sll
{
 int val;
 struct sll *ptr;
}*start = NULL;
 
int choice, data;
char c;
 
void create();
void display();
void search();
void ins_beg();
void ins_end();
void ins_agp();
void del_beg();
void del_end();
void del_agp();
void menu();
void seperator();
 
 
 
void main()
{
 menu();
}
 
 
void create()
{
 do{
  struct sll *temp1, *temp2;
  temp1 = (struct sll*)malloc(sizeof(struct sll));
 
  printf("\nEnter Data :: ");
  scanf("%d", &data);
  temp1->val = data;
  temp1->ptr = NULL;
 
  if (start == NULL)
  {
   start = temp1;
  }
  else
  {
   temp2 = start;
   while (temp2->ptr != NULL)
   {
    temp2 = temp2->ptr;
   }
   //temp1->llink=q;
   temp2->ptr = temp1;
   //temp1->link=NULL;
  }
  printf("\nDo you want to insert more (Y/N) ::");
  fflush(stdin);
  scanf("%c", &c);
 
 } while (c == 'Y' || c == 'y');
 
 display();
}
 
 
void display()
{
 struct sll *temp;
 
 if (start == NULL)
 {
  printf("\nList is empty.\n");
 }
 else
 {
  temp = start;
  printf("\nStored Linked List ::");
  while (temp != NULL)
  {
   printf("\n  %d", temp->val);
   temp = temp->ptr;
  }
 }
 printf("\n \nPress any key to continue....");
 getch();
 menu();
}
 
void search()
{
 int x, count = 0;
 struct sll *temp;
 printf("\nEnter data to be find ::");
 scanf("%d", &x);
 if (start == NULL)
 {
  printf("\nError : List is empty.");
 }
 else
 {
  temp = start;
  if (start == temp->ptr && temp->val == x)
  {
   printf("\nLocation :: %d\yValue :: %d", start, start->val);
   count++;
  }
  else
  {
   do
   {
    if (temp->val == x)
    {
     count++;
    }
    temp = temp->ptr;
   } while (temp->ptr != start);
 
  }
 }
 
 if (count == 0)
 {
  printf("\n Element doesnt exists.");
 }
 else
 {
  printf("\n Total %d elements found.", count);
 }
 printf("\n \nPress any key to continue...");
 getch();
 menu();
}
 
void ins_beg()
{
 struct sll *temp;
 temp = (struct sll*)malloc(sizeof(struct sll));
 printf("\nEnter Data ::");
 scanf("%d", &data);
 temp->val = data;
 temp->ptr = start;
 start = temp;
 
 display();
}
 
void ins_end()
{
 struct sll *temp, *q;
 temp = (struct sll*)malloc(sizeof(struct sll));
 printf("\nEnter Data ::");
 scanf("%d", &data);
 temp->val = data;
 if (start == NULL)
 {
  printf("\nError : List is empty.");
 }
 else
 {
  q = start;
  while (q->ptr != NULL)
  {
   q = q->ptr;
  }
  q->ptr = temp;
  temp->ptr = NULL;
  display();
 }
}
void ins_agp()
{
 struct sll *temp, *q, *prev;
 int pos, count = 1;
 temp = (struct sll*)malloc(sizeof(struct sll));
 printf("\nEnter Position ::");
 scanf("%d", &pos);
 printf("\nEnter Data ::");
 scanf("%d", &data);
 temp->val = data;
 if (start == NULL)
 {
  printf("\nError : List is empty.");
 }
 else
 {
  q = start;
  while (count != pos)
  {
   prev = q;
   q = q->ptr;
   count++;
  }
  temp->ptr = q;
  prev->ptr = temp;
  display();
 }
}
 
void del_beg()
{
 if (start == NULL)
 {
  printf("\nError : List is empty.");
  getch();
  menu();
 }
 else
 {
  start = start->ptr;
  printf("\nSuccess !");
  display();
 }
}
 
void del_end()
{
 struct sll *q, *prev;
 if (start == NULL)
 {
  printf("\nError : List is empty.");
  getch();
  menu();
 }
 else
 {
  q = start;
  while (q->ptr != NULL)
  {
   prev = q;
   q = q->ptr;
  }
  prev->ptr = NULL;
  printf("\nSuccess !");
  display();
 }
}
 
void del_agp()
{
 int pos, count = 1;
 struct sll *q, *prev;
 printf("\nEnter Position ::");
 scanf("%d", &pos);
 if (start == NULL)
 {
  printf("\nError : List is empty.");
  getch();
  menu();
 }
 else
 {
  q = start;
  while (count != pos)
  {
   prev = q;
   q = q->ptr;
   count++;
  }
  prev->ptr = q->ptr;
  printf("\nSuccess !");
  display();
 }
}
 
void menu()
{
 clrscr();
 do
 {
  seperator();
  printf("-[[[[[[[[ MENU ]]]]]]]]-\n");
  printf("1.Create \t\t2.Display \n3.Search \t\t");
  printf("4.Insert_at_begining \n5.Insert_at_end \t");
  printf("6.Insert_at_given_position \n7.Delete_at_begining\t");
  printf("8.Delete_at_end\n9.Delete_at_given_position \n");
  printf("\nPress 0 to exit...\n");
  seperator();
 
  printf("Enter your choice :: ");
  scanf("%d", &choice);
 
  switch (choice)
  {
  case 0: exit(); break;
  case 1: create(); break;
  case 2: display(); break;
  case 3: search(); break;
  case 4: ins_beg(); break;
  case 5: ins_end(); break;
  case 6: ins_agp(); break;
  case 7: del_beg(); break;
  case 8: del_end(); break;
  case 9: del_agp(); break;
  default: printf("\nInvalid Command. Try Again."); getch(); menu();
  }
 } while (choice != 0);
}
 
void seperator()
{
 int i;
 for (i = 0; i < 80; i++)
 {
  printf("-");
 }
 printf("\n");
}


Check out other versions of Linked Lists :

Post a Comment