Linked
lists:
a.Linked
list is collection of nodes.
b. Node is a combination
of two fields(data field, link field)
1.
One for sorting
data or information
2. Other for sorting
address of next element
c. For sorting address we have a special
data structures in ‘C’ called pointers, here the second
field of the list must be pointer type.
NODE
Information
|
Pointer
to next node
|
Data
link
Singly
linked list:
Singly linked list is a dynamic data structure.(i.e., they can row or shrink
during the execution of a program).
In ‘C’, a linked list is created using
structures, pointers and dynamic memory allocation function malloc().
We consider head as an external pointer.
This helps in creating and accessing other nodes in linked list.
struct
node
{
Int num;
Struct node *ptr; /*pointer to node*/
};
Typedef
struct node NODE; /*type definition
making it abstract data type*/
NODE *start;
/*pointer to the node of linked list */
Start=(NODE *)malloc(sizof(NODE)); /*dynamic memory allocation*/
When statement,
Start=(NODE *)malloc(sizeof(NODE));
|
Is executed, a block of memory sufficient to store the NODE
is allocated assigns head as the starting address of the NODE.
We can assign values to respective fields of NODE,
Start ---> number=30;
Start---> ptr=NULL;
Any number of nodes can be created and linked to the
existing node
To add another node to above list,
Start--->ptr=(NODE *)malloc(sizeof(NODE));
Start--->ptr.num=100;
Start--->ptr.ptr=NULL;
Program to create element in the
linked list and display the element:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
Void main()
{
Struct node
{
int num;
struct node *next;
}*start=NULL;
Typedef struct node NODE;
NODE *p,*q,*temp;
Int count=0;
Char choice;
Clrscr();
do{
p= (NODE *)malloc(sizeof(NODE));
print(“Enter data item”);
scanf(“%d”,&p->num);
if(start==NULL)
{
p->next=start;
start=p;
}
else
{
q=start;
while(q->next!=NULL)
{
q=q->next;
}
}
print(“Do U want to continue(type y or n)?”);
scanf(“%c”&choice);
}while(choice==’y’)||(choice==’Y’);
printf(“status
of linked list is”);
count++;
temp=temp->next;
}
printf(“No. of nodes
in the list=%d”,count);
}
write a program for inserting
elements of a linked list:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int num;
struct node*next;
};
typedef struct node
NODE;
NODE *start;
void
createemptylist(NODE *start)
{
*start=NULL;
}
void traverse(NODE
*start)
{
p=start;
while(p!=NULL)
{
printf(“%d”,p->num);
p=p->next;
}
}
void
insertatbegin(int item)
{
NODE *p;
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
if(start==NULL)
p->next=NULL;
else
p->next=start;
start=p;
}
void
insert_at_end(int item)
{
NODE *p,*loc;
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
p->next=NULL;
if(start==NULL)
start=p;
else
{
loc=start;
while(loc->next!=NULL)
{
loc=loc->nex5;
}
loc->next=p;
}
}
void insert_at_spe(int
item,int loc)
{
NODE *p,*temp;
int k;
for(k=a,temp=start;k<loc;k++)
{
temp=temp->next;
if(temp==NULL)
{
printf(“NODE in the
list at less than one”);
return;
}
}
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
p->next=temp->next;
p->next=p;
}
void main()
{
int choice,item;
clrscr();
createemptylist(start);
do
{
clrscr();
printf(“1.Inser
element at begining”);
printf(“2.Insert
elememt at end”);
printf(“3.Insert at
specific position”);
printf(“4.Traverse
the list in order”);
printf(“5.Exit”);
printf(“Enter your
choice”);
scanf(“%d”,choice);
switch(choice)
{
case 1: printf(“Enter
item”);
scanf(“%d”,&item);
insertatbegin(item);
break;
case 2: printf(“Enter
item”);
scanf(“%d”,&item);
insert_at_end(item);
break;
case 3: printf(“Enter
item”);
scanf(“%d”,&item);
insert_at_spe(item,2);
break;
case 4:
printf(“Traverse the list”);
traverse(start);
break;
case 5: exit(0);
}
}while(choice!=5);
}
write a program to insert and
delete the nodes linked list:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int num;
struct node *next;
};
typedef struct node
NODE;
NODE *start;
void
createmptylist(NODE *start)
{
*start=NULL;
}
void traverse(NODe
*start)
{
p->start;
while(p!=NULL)
{
printf("%d",p->num);
p=p->next;
}
}
void
insertatbegin(int item)
{
NODE *p;
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
if(start==NULL)
p->next=NULL;
else
p->next=start;
start= p;
}
void insertatend(int item)
{
NODE *p,*loc;
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
p->next=NULL;
if(start==NULL)
start=p;
else
{
loc=start;
while(loc->next!=NULL)
loc=loc->next;
loc->next=p;
}
}
void deletebeg()
{
NODE *p;
if(start==NULL)
printf("list is empty");
else
{
p=start;
start=start->next;
printf("NO.deleted is
=%d",p->num);
free(p);
}
}
void deleteend()
{
NODE *p,*loc;
if(start==NULL)
pribtf("list is empty");
else if((start)->next==NULL)
{
p=start;
start=NULL;
printf("No.
deleted is=%d",p->num);
free(p);
}
else
{
loc=start;
p=start->next;
while(p->next=NULL)
{
loc=p;
p=p->next;
}
loc->next=NULL;
printf("NO. deleted
is=%d",p->num);
free(p);
}
}
void insert_spe(int
item,int loc)
{
NODE *p,*temp;
int k;
for(k,temp=start;k<loc;k++)
{
temp=temp->next;
if(temp==NULL)
{
printf("Node
in the list at less than one");
return;
}
}
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
p->next=temp->next;
temp->next=p;
}
void delte_spe()
{
NODE *p,*temp;
int i,loc;
printf("Enter position to
delete");
scanf("%d",&loc);
if(start==NULL)
{
printf("list
empty");
}
else
{
p=start;
for(i=1;i<=loc;i++)
{
temp=p;
p=p->next;
}
printf("No.
deleted is=%d",p->num);
temp->next=p->next;
free(p);
}
}
void main()
{
int choice,item,loc;
clrscr();
createemptylist(start);
do
{
printf("1.
Insert element at begining");
printf("2.
Insert element at end");
printf("3.
Insert at specific possition");
printf("4.
traverse list in order");
printf("5.
Delete the begining");
printf("6.
Delete the last");
printf("7.
Delete element at specified possition");
printf("8.
Exit");
printf("Enter
your choice");
scanf("%d",&choice);
switch(choice)
{
case
1:printf(Enter item);
scanf("%d",&item);
insertatbegin(item);
break;
case
2:printf("Enter item")
scanf("%d",&item);
insertatend(item);
break;
case
3:printf("Enter item");
scanf("%d",&item);
insert_spe(item,loc);
break;
case
4:printf("Traverse the list");
traverse(start);
break;
case
5:printf("Delete item");
deletebeg();
break;
case
6:printf("Delete element");
deleteend();
break;
case
7:printf("Delete specific element");
delete_spe();
break;
case
8:exit(0);
}
}while(choice!=8);
}
Doubly linked
list:
So far we have
studied singly linked list and their variation circular linked list. One of the
most striking disadvantages of this list is the inability to traverse the list
in the backward direction.
In most of the
application it is necessary to traverse the list both in forward direction and
backward direction. The most appropriate data structure for such an application
is doubly linked list.
Doubly linked list
is collection of nodes. The node is combination of three fields.
Data field, Two
linked fields (Previous and next field)
Data field contain information, previous field maintains address of
previous node and next field
maintains address of next node.
NODE:
address
of previous node
|
information
|
address
of next node
|
In doubly linked
list the previous field of first node and next field of last node are always
NULL.
Structure
definition for the node is declared as,
struct node
{
int num;
struct node *prev;
struct node *next;
};
typedef struct node NODE;
Program to demonstrate operation
of doubly linked list:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int num;
struct node *prev;
struct node *next;
}*start=NULL,*last=NULL;
typedef struct node
NODE;
void
insertatbegin(int item)
{
NODE *p;
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
if(start==NULL)
{
p->prev=NULL;
p->next=NULL;
start=last=p;
}
else
{
p->prev=NULL;
p->next=start;
start->prev=p;
start=p;
}
}
void insertatend(int
item)
{
NODE *p;
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
if(start==NULL)
{
p->prev=NULL;
p->next=NULL;
start=last=p;
}
else
{
p->prev=NULL;
p->next=NULL;
start=last=p;
}
else
{
p->next=NULL;
p->prev=last;
last->next=p;
last=p;
}
}
void deleteatbegin()
{
NODE *p;
if(start==NULL)
printf("List empty");
else if(start->next==NULL)
{
p=start;
start=last=NULL;
}
else
{
p=start;
start=start->next;
start->prev=NULL;
}
free(p);
}
void deleteatend()
{
NODE *p;
if(start==NULL)
printf("lsit empty")
else if(last->prev==NULL)
{
p=last;
start=last=NULL;
}
else
{
p=last;
last=last->prev;
last->next=NULL;
}
free(p);
}
void main()
{
int choice,item;
do
{
clrscr();
printf("1.
Insert at begining");
printf("2.
Insert at end");
printf("3.
Delete at beginning");
printf("4.
Delete at end");
printf("5.
Exit");
printf("Enter
your choice");
scanf("%d",&choice);
switch(choice)
{
case
1:printf("Enter item");
scanf("%d",&item);
insertatbegin(item);
break;
case
2:printf("Enter item")
scanf("%d",&item);
insertatend(item);
break;
case
3:printf("Deleting begining");
deleteatbegin();
break;
case
4:printf("Deleting last");
deleteatend();
break;
case
5:exit(0);
}
}while(choice!=5);
}
Circular linked
list:
It is a singly linked
list in which link field of the last node contain address of the first node of
the list.
Here link field of
the last node does not point to NULL rather it points back to the beginning of
the linked list.
Circular linked list
has no end, hence it is necessary to establish FIRST and LAST nodes in such a
linked list.
The START and LAST
nodes of a circular linked list is represented as,
We declare the structure of
circular linked list as,
struct node
{
int num;
struct node *next;
};
typedef struct node
NODE;
NODE *start=NULL;
NODE *last=NULL:
Program to insert and delete the
nodes from a circular linked list:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int num;
struct node *next;
};
typedef struct node
NODE;
NODE *start=NULL;
NODE *last=NULL;
void main()
{
int choice,item;
do
{
clrscr();
printf("1.
Insert at begining");
printf("2.
Insert at end");
printf("3. Delete
at beginning");
printf("4.
Delete at end");
printf("5.
Traverse");
printf("Enter
your choice");
scanf("%d",&choice);
switch(choice)
{
case
1:printf(“Enter item”);
scanf("%d",&item);
insertfirst(item);
break;
case
2:printf("Enter item")
scanf("%d",&item);
insertlast(item);
break;
case
3:printf("Deleting first");
deletefirst();
break;
case
4:printf("Deleting last");
deletelast();
break;
case
5:printf("Element in last");
traverse();
break;
case
6:exit(0);
}
}while(choice!=6);
}
void insetfirst(int
item)
{
NODE *p;
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
if(start==NULL)
{
p->num=p;
start=p;
last=p;
}
else
{
p->next=start;
start=p;
last->next=p;
}
}
void insertlast(int
item)
{
NODE *p;
p=(NODE *)malloc(sizeof(NODE));
p->num=item;
if(start==NULL)
{
p->next=p;
start=last=p;
}
else
{
last->next=p;
last=p;
last->next=start;
}
}
void deletefirst()
{
NODE *p;
p=start;
if(p==NULL)
{
printf("list
is empty");
}
else
{
p=start;
start=start->next;
printf("element
deleted is =%d",p->num);
last->next=start;
free(p);
}
}
void delerelast()
{
NODE *p,*q;
p=start;
if(p==NULL)
{
printf("list
is empty");
}
else
{
while(p->next!=last)
{
q=p;
p=p->next;
}
printf("Element
deleted is %d",p->num);
q->next=p->next;
}
last=q;
free(p);
}
void traverse()
{
NODE *p;
p=start;
if(p==NULL)
{
printf("list
is empty");
}
else
{
while(p->next!=start)
{
printf("%d",p->num);
p=p->next;
}
}
}
Circular doubly linked list:
A circular doubly linked list is the
variation of doubly linked lists.
A circular doubly linked list is one which
has both the successor pointer and predecessor pointed in circular manner.
The objective behind considering circular
doubly linked list is to simplify the insertion and deletion operations
performed on doubly linked list.
A circular doubly linked list with a head
node is shown below,
A node for circular doubly linked list is
defined as
struct node
{
int num;
struct node *next;
struct node *prev;
}
typedef struct node
NODE;
NODE *start=NULL;
NODE *last=NULL;
program to insert and delete the
node from circular doubly linked list:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int num;
struct node *next;
struct node *prev;
}
typedef struct node
NODE;
NODE *start=NULL;
NODE *last=NULL;
void insertfirst()
{
NODE *p;
p=(NODE *)malloc(sizeof(NODE));
printf("Enter the
number");
scanf("%d",&p->num);
if(start==NULL)
{
start=p;
last=p;
p->next=p;
p->prev=p;
}
else
{
p->next=start;
start->prev=p;
start=p;
p->prev=last;
last->next=p;
}
}
void insertlast()
{
NODE *p;
p=(NODE *)malloc(sizeof(NODE));
printf("Enter the
number");
scanf("%d",&p->num);
if(start==NULL)
{
start=p;
last=p;
p->next=p;
p->prev=p;
}
else
{
last->next=p;
p->prev=last;
last=p;
last->next=start;
start->prev=p;
}
}
void insertbetween()
{
NODE *p,*q;
int pos,i;
p=(NODE *)malloc(sizeof(NODE));
printf("Enter the
number");
scanf("%d",&p->num);
printf("Enter the
position");
scanf("%d",&pos);
q=start;
for(i=1;i<pos;i++)
q=q->next;
p->next=q->next;
(q->next)->prev=p;
p->prev=q;
q->next=p;
}
void deletefirst()
{
NODE *p;
if(start!=NULL)
{
p=start;
start=start->next;
printf("No.
deleted is %d",p->num);
start->prev=last;
last->next=start;
free(p);
}
else
printf("list is
empty");
}
void deletelast()
{
NODE *p;
if(start!=NULL)
{
p=last;
last=last=last->prev;
printf("No.
deleted is %d",p->num);
free(p);
last->next=start;
start->prev=last;
}
else
printf("list is
empty");
}
void deletebetween()
{
NODE *p,*q;
int i,pos;
printf("Enter the position
to delete");
scanf("%d",&pos);
p=start;
for(i=1;i<pos;i++)
{
q=p;
p=p->next;
}
q->next=p->next;
(p->next)->prev=q;
printf("No. deleted is
%d",p->num);
free(p);
}
void traverse()
{
NODE *p;
if(start!=NULL)
{
p=start;
while(p->next=start)
{
printf("%d",p->num);
p=p->next;
}
}
else
printf("list is
empty");
}
void main()
{g
int choice;
ggg do
{
clrscr();
printf("1.
Insert at begining");
printf("2. Insert
at end");
printf("3.
Insert at position");
printf("4.
Delete first");
printf("5.
Delete last");
printf("6.
Delete at position");
printf("7.
Traverse list");
printf("8.
Exit");
printf("Enter
your choice");
scanf("%d",&choice);
switch(choice)
{
case
1: insertfirst();
break;
case
2: insertlast();
break;
case
3: insertbetween();
break;
case
4: deletefirst();
break;
case
5: deletelast();
break;
case
6: deletebetween();
break;
case
7: traverse();
break;
case
8: exit(0);
default:printf("wrong
choice");
}
}while(choice!=8);
}
No comments:
Post a Comment