Data structures: A data structure is a specialized format for organizing
and storing data.
There are many types of data structures used in the modern days. But the basic
data structures are of two types, one is by using static memory allocation and another
is by using dynamic memory allocation. All the data types such has arrays,
unions come under the category of static memory allocation i.e the number of
variables to be entered is fixed before the execution of program. Due to this whenever
a user need to give more number of inputs then there is the restriction.
So, in your current article we shall
discuss about the data structures using dynamic memory allocation. In the dynamic
memory allocation whenever we request for a memory allocation for a variable
the operating system is going to allocate us a memory cell from the heap memory.
Due this whenever we request for memory we get the cell not in contiguous
spaces so, we need to maintain the link between the recently created cell and
the cell created before it. These data structures are called as linked lists.
Here we dealing with address of the other memory cells so we shall use the
concept of POINTERS
Linked lists are mainly divided into three
types:
1.Singly linked lists.
2. Doubly linked lists.
3. Circularly linked lists.
Here we shall discuss about singly linked lists. At first we need
to know about the operations performed on the singly linked lists. the
operations are create, insert at first, insert at last, insert at middle,
delete by position, delete by value, display. In order to do all these
operations we need to ask for a memory cells such that it stores the input data
and stores the address of the next memory cells. These memory cells are
technically called as NODES. These nodes are acquired by using the concept of
STRUCTURES. The spaces in the nodes are called as data field and next field.
Declaration of node:
struct node
{
int data;
struct node *next; (self reference)
}*first,*last,*temp;
Here first,last,temp are the variables.
Creation of the node:
void create()
{
temp=(struct node*)malloc(sizeof(struct
node)); /*dynamic memory allocation*/
printf("\nEnter the Data in the Node:");
scanf("%d",&temp->data);
temp->next=NULL;
if(first==NULL)
{
first=temp;
last=temp;
}
else
/* copying the address the newly crearted in to older on */
{
last->next=temp;
last=temp;
}
}
Inserting at first:
void insert_atfirst()
{
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter Element:");
scanf("%d",&temp->data);
temp->next=first;
/* copying the address of the previously first node to newly created node */
first=temp;
}
Inserting in the middle:
void insert()
{
struct node
*t,t1;
/* nodes for traversing */
int pos, count=1,AB;
printf("\nEnter Position to be inserted:");
scanf("%d",&pos);
printf("\nAfter[1] or Before[2]:");
scanf("%d",&AB);
temp=(struct node*)malloc(sizeof(struct
node));
printf("\nEnter data:");
scanf("%d",&temp->data);
temp->next=NULL;
t=t1=first;
while(t!=NULL)
{
if(pos==count)
/* if the requires position is achieved the loop is breaked */
break;
else
{
t=t1;
t=t->next;
count++;
}
}
if(AB==1)
{
temp->next=t->next;
/* this case comes under inserting at first */
t->next=temp;
}
else if(AB==2)
{
temp->next=t;
/* this case comes under inserting in the middle */
t1->next=temp;
}
else
printf("\nInvalid Input");
}
Inserting at the last:
void insert_atlast()
{
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter value to be inserted at last:");
scanf("%d",&temp->data);
last->next=temp;
/* copying the address newly created to previous last*/
last=temp;
}
Delete by position:
void delete_bypos()
{
struct node *t,*t1;
int pos, count=1;
printf("\nEnter the Position of the element you would
like to delete:");
scanf("%d",&pos);
t=t1=first;
while(t!=NULL)
{
if(pos==count)
t1=t;
t=t->next;
count++;
}
if(pos==1)
{
first=t->next;
/* if it is thre first position */
printf("\nExceuted-->First
Node is deleted!!");
}
else if(t==last)
{
t1->next=NULL; /* if it is the last position
*/
free(t);
printf("\nExecuted-->Last
Node is deleted!!");
}
else
{
t1->next=t->next; /* if the entered position is in the middle */
free(t);
printf("\nExecuted-->Node
has been deleted!!");
}
}
Delete by value:
void delete_byval()
{
int val, count=1;
struct node *t,*t1;
printf("\nEnter value:");
scanf("%d",&val);
t=t1=first;
while(t!=NULL)
{
if(val==t->data)
break;
else
{
t=t->next;
count++;
}
}
if(t==first)
{
first=t->next;
/* If the given value is the first one*/
free(t);
}
else if(t==last)
{
t1->next=NULL;
/* If the given value is the last one */
free(t);
last=t1;
}
else
{
t1->next=t->next; /* The given value is in the middle*/
free(t);
}
}
Display:
void display()
{
temp=first;
while(temp!=NULL)
{
printf("|%d---%u| ------>
",temp->data,temp->next); /* display printf*/
temp=temp->next;
}
}
The main function:
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
void create();
void insert_atfirst();
void insert_atlast();
void insert();
void delete_bypos();
void delete_byval();
void display();
int menu();
struct node
{
int data;
struct node *next;
}*first=NULL,*last=NULL,*temp=NULL;
void main()
{
int ch;
clrscr();
do{
ch=menu();
/*print the menu of the program*/
switch(ch)
{
case
1:create();
/*calls the create function*/
break;
case
2:insert_atfirst();
/*calls the isnert function to insert at first*/
break;
case
3:insert_atlast();
/*calls the insert function to insert at last*/
break;
case
4:insert();
/*calls the insert function to insert at middle*/
break;
case
5:delete_bypos(); /*calls the delete by position function*/
break;
case
6:delete_byval();
/*calls the delete by value function*/
break;
case
7:display(); /*calls the display function*/
break;
case
8:exit(0);
case
9:clrscr();
default:printf("\nError-->Enter a valid choice!!");
exit(0);
}
}while(1);
}
