Linked List is a linear data structure, in which elements are not stored at a contiguous location, rather they are linked using pointers. Linked List forms a series of connected nodes, where each node stores the data and the address of the next node.
Node Structure: A node in a linked list typically consists of two components:
Data: It holds the actual value or data associated with the node.
Next Pointer: It stores the memory address (reference) of the next node in the sequence.
Why linked list data structure needed?
- Dynamic Data structure:
- Ease of Insertion/Deletion:
- Efficient Memory Utilization:
- Implementation:
Types of linked lists:
There are mainly three types of linked lists:
- Single-linked list
- Double linked list
- Circular linked list
Single-linked list
Singly Linked List contains a header pointer which contains address of the first node (the head node). Forward sequential movement, only, is possible here.
Note that the last node has it's link part set to null
Implementation
First we'll create a node class which we will instantiate when we want to create a node.
struct node
{
int d;
struct node *next;
}*start=NULL, *new1;
Creation of first node in singly link list
struct node
{
int d;
struct node *next;
}*start=NULL, *new1;
new1=(struct node *)malloc(sizeof(struct node *));
new1->next=NULL;
printf("\nenter element vlaue:\n");
scanf("%d",&new1->d);
Start=new1;
Creation of singly link list
void create()
{
char ch;
do
{ new1=(struct node *)malloc(sizeof(struct node *));
new1->next=NULL;
printf("\nenter element vlaue:\n");
scanf("%d",&new1->d);
if(start==NULL)
{
start=new1;
cur=new1;
}
else
{
cur->next=new1;
cur=new1;
}
printf("\nenter choice(press n for exit\n");
ch=getche();
}while(ch!='n');
}
Insert node at beginning of the given singly link list
void insertbegin()
{
struct node *new1;
new1=(struct node *)malloc(sizeof(struct node));
printf(" enter element \n");
scanf("%d",&new1->d);
if(start==NULL)
{
start=new1;
new1->next=NULL;
}
else
{
new1->next=start;
start=new1;
}
}
Insert node at end of the given singly link list
void insertend()
{
struct node *new1,*tmp;
new1=(struct node *)malloc(sizeof(struct node));
printf(" enter element \n");
scanf("%d",&new1->d);
if(start==NULL)
{
start=new1;
new1->next=NULL;
}
else
{ tmp=start;
while (tmp->next!=NULL)
{
tmp=tmp->next;
}
tmp->next=new1;
new1->next=NULL;
}
}
Display given singly link list
void display()
{
ptr=start;
while((ptr)!=NULL)
{
printf("%d-->",ptr->d);
ptr=ptr->next;
}
printf("null\n");
}
Insert node after given node in the singly link list
void insertafter()
{
int x;
struct node *new1,*a,*b;
new1=(struct node *)malloc(sizeof(struct node));
printf(" enter element \n");
scanf("%d",&new1->d);
printf("\nenter a value of a given node after
you want to insert a new node\n");
scanf("%d",&x);
b=a=start;
if(start==NULL){
printf("empty"); }
else if(start->d==x){
a=a->next;
new1->next=a;
b->next=new1;}
else{
while(b->d!=x){
b=a;
a=a->next; }//end of while
b->next=new1;
new1->next=a; }//end of else
}//end of insertafter
Insert node before given node in the singly link list
void insertbefore()
{
int x;
struct node *new1,*a,*b;
new1=(struct node *)malloc(sizeof(struct node));
printf(" enter element \n");
scanf("%d",&new1->d);
printf("\nenter a value of a given node before
you want to insert a new node\n");
scanf("%d",&x);
b=a=start;
if(start==NULL)
{
printf("empty");
}
else{
while(a->d!=x){
b=a;
a=a->next; }//end of while
b->next=new1;
new1->next=a; }//end of else
}//end of insertafter
Delete first node from the singly link list
void delbegin()
{
struct node *ptr;
ptr=start;
start=ptr->next;
free(ptr);
}
Delete last node from the singly link list
void delend()
{
struct node *a, *b;
a=b=start;
while(b->next!=NULL)
{
a=b;
b=b->next;
}
a->next=NULL;
}
Delete selected node from the singly link list
void delselected()
{
struct node *a, *b;
int x;
a=b=start;
printf("\nEnter element to be delete\n");
scanf("%d",&x);
while(b->d!=x && b->next!=NULL){
a=b;
b=b->next;
}
if(b->next==NULL){
if(b->d!=x)
printf("Element not found");
else{
a->next=NULL;
}
}
else
a->next=b->next;
}
No comments:
Post a Comment