Unit IV
Linked List
Linked Organization consists of set of nodes linked together by pointers. Linked data structure offers more flexibility in organization of data and allocation of space for it.eg. Linked List, Search Trees, Expression Trees
Linked organization offers various advantages over arrays.
2. Write a Program to create a Linked List
#include <stdio.h>
#include<conio.h>
typedef struct node
{
int data;
struct node *next;
}node;
void main()
{
node *HEAD, *P ;
int n,i;
printf(“Enter no of nodes to be inserted ”)
scanf(“%d”, &n);
HEAD = (node*)malloc(sizeof(node));//get the first node
scanf(“%d”, &(HEAD->data));// get data in first node
HEAD->next= NULL;
P=HEAD;// currently HEAD and P points to same node
for(i=1;i<n;i++)// for n nodes
{
P->next= (node*)malloc(sizeof(node));
P=P->next;
P->next= NULL;
scanf(“%d”, &(P->data));
}
}
Explanation :
Declare node with self referential structure.
Create HEAD node which is first node in Linked List.
HEAD = (node*)malloc(sizeof(node));
Store data in First node .
scanf(“%d”, &(HEAD->data));//
Currently there is only one node in Linked List. So *next contains Null value and HEAD and P points to same node.
HEAD next = NULL;
P = HEAD;
Now create remaining nodes with the help of following code.
for(i=1;i<n;i++)// for n nodes
{
P->next= (node*)malloc(sizeof(node));
P=P->next;
P->next= NULL;
scanf(“%d”, &(P->data));
}
3. Write a Program to create and display the Linked List using function. This program also counts total number of nodes in Linked List
#include <stdio.h>
#include<conio.h>
typedef struct node
{
int data;
struct node *next;
}node;
node *create(int);
void display(node*);
int count(node *);
void main()
{
node *HEAD;
int n, x;
printf(“Enter number of nodes”);
scanf(“%d”, &n);
HEAD = create(n) ;
display(HEAD);
x= count(HEAD);
printf(“Total number of nodes =”+x);
getch();
}
node *create(int n)
{
node *start, *P;
int i;
HEAD= (node*)malloc(sizeof(node));
start-> next = NULL;
scanf(“%d”, &(start->data));
P= start;
for(i=1;i<n;i++)
{
P->next = (node*)malloc(sizeof(node));
P=P->next;
scanf(“%d”, &(P->data));
P->next= NULL;
}
return(start);
}
void display(node *P)
{
printf(“Nodes are”)
while(P!=NULL)
{
printf(“ %d ”P->data);
P=P->next;
}
}
int count(node *P)
{
int i=0;
while(P!=NULL)
{
P=P->next;
i++;
}
return(i)
}
Output :
Enter number of nodes: 3
10 20 30
Nodes are
10 20 30
Total number of nodes: 3
4. What is different OPERATIONS ON LINKED LIST?
Following operations can be performed on Linked List:
1. Creation of a node
2. Insertion of a node
3. Deletion of a node
4. Traversing
INSERTION OF NODE : Node can be inserted at 3 positions
(A) At the beginning of Linked List
(B) In the middle of Linked List
(C) At the end of Linked List
(A) Insertion of node at the beginning of Linked List
In this case, new node is inserted right before the current head node.
Assume that P node is to be inserted.
It can be done in 3 steps:
1. Allocate memory to node P i.e
P = (node*)malloc(sizeof(node));
2. Update the next link of a P node, to point to the current head node.
P->next = Head;
Update Head to point to the node P.
Head = P;
(B) Insertion of a node in the middle of Linked List
To insert a node in the middle of linked list we must know the data value of node after which node is to be inserted. Once we get the data value of node, traverse to that node.
Let us represent data value in a node by variable ‘data’ and value of node after which new node is to be inserted is ‘val’.
Such an insert can be done in following steps:
1. Allocate memory to node P.
P = (node*)malloc(sizeof(node));
2. Assume Q points to first node of Linked List.
Q=Head
3. Traverse the linked list so that Q points to the node after which new node is to be inserted.
while(Q!=NULL)
{
if(Q->data= =val)
break;
Q=Q->next;
}
Suppose we want to insert after 2nd node whose data value is 3.Hence according to step 3 Q will point to 2nd node.
4. Update link of the node Q, to point to the node P.
P next = Q next
Q next = P
5. Update link of the node P, to point to the "next" node.
(C) Insertion of node at the end of linked list
In this case, new node is inserted right after the last node.
It can be done in following steps :
1. Allocate memory to node P.
P = (node*)malloc(sizeof(node));
Update the next link of the current last node, to point to the node P. Position pointer Q to the last node. In order to find this position, list should be traversed first, beginning from the Head. Initially Head and Q points to first node.
Q=Head
while(Q->next!=NULL)
Q=Q->next
Q->next=P
Deletion of Node : Node can be deleted at 3 positions:
(A) beginning of Linked List
(B) the middle of Linked List
(C) end of Linked List
We use standard c function free() to free the memory occupied by node.
(A) Delete first node from Linked List.
In this case, first node i.e. current head node is removed from the list.
It can be done in two steps:
1. Let P and Head points to first node. Update Head link to point to the node which is next to the Head.
(B) Delete node from middle of Linked List
To delete a node in the middle of linked list we must know the data value of node after which node is to be deleted. Once we get the data value of node, traverse to that node.
Let us represent data value in a node by variable ‘data’ and value of node after which new node is to be inserted is ‘val’. Suppose we want to delete 3rd node
Deletion can be done as follows :
1. Intially Q,P and Head points to first node.
P=Head
2. Traverse to the node after which node is to be deleted.
while(P!=NULL)
{
if(P->data==val)
break;
Q=P
P=P->next
}
According to step 2 P points to 3rd node and Q points to 2nd node.
(C) Delete Last Node from the Linked List
In this case, last node is removed from the list.
It can be done in three steps:
Assume last node is pointed by P.
1. Position pointer Q to the node previous to P. In order to find this position, list should be traversed first, beginning from the head.
Q = Head
while(Q->next->next!=NuLL)
Q = Q->next
P = Q->next
5. Write a Program to perform following operations on Linked List
(A) Create a linked list
(B) Insertion of a node
1. At the beginning of Linked List
2. In the middle of Linked List
3. At the end of Linked List
(C) Deletion of a node from
1. beginning of Linked List
2. the middle of Linked List
3. end of Linked List
(D) Display Linked List
#include <stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
} node;
node *create();
node *insert_s(node *head, int x)
node *insert_m(node *head, int x)
node *insert_e(node *head, int x);
node *delete_s(node *head );
node *delete_m(node *head );
node *delete_e(node *head );
void display(node*);
void main()
{
int op,c,x;
node *head= NULL;
do
{
printf(“1.create 2.Insert 3. Delete 4. Display”);
printf(“Enter choice”);
scanf(“%d”, c);
switch(c)
{
case 1:head= create();
break;
case 2: printf(“1.start 2. Middle 3. end”);
scanf(“%d”, &op);
printf(“Enter data to be inserted”);
scanf(“%d”, &x);
switch(op)
{
case 1: head= insert_s(head,x);
break;
case 2: head= insert_m(head,x);
break;
case 3: head= insert_e(head,x);
break;
}
break;
case 3: printf(“1.start 2. Middle 3. end”);
scanf(“%d”, &op);
switch(op)
{
case 1: head= delete_s(head);
break;
case 2: head= delete_m(head);
break;
case 3: head= delete_e(head);
break;
}
break;
case 4: display(head);
break;
}
}while(op!=5)
}
node *create()
{
node *head,*p;
int i,n;
head=NULL:
printf(“Enter no of data”);
scanf(“%d”,&n);
printf(“\n Enter data”);
for(i=0;i<n;i++)
{
if(head==NULL)
p=head=(node*)malloc(sizeof(node));
else
{
p->next= (node*)malloc(sizeof(node));
p=p->next;
}
p->next=NULL;
scanf(“%d”, &(p->data));
}
return(head);
}
node *insert_s(node *head, int x)
node *p;
p= (node*)malloc(sizeof(node));
p->data= x;
p->next=head;
head=p;
return(head);
}
node *insert_m(node *head, int x)
{
node *p, *q;
int y;
p= (node*)malloc(sizeof(node));
p->data= x;
p->next=NULL;
printf(“Insert after which number”);
scanf(“%d”, &y);
for(q=head;q!=NULL && q->data!=y;q=q->next)
{
if(q!=NULL)
{
p->next=q->next;
q->next=p;
}
else
printf(“data not found”);
return(head);
}
node *insert_e(node *head, int x)
{
node *p,*q;
p= (node*)malloc(sizeof(node));
p->data= x;
p->next=NULL;
if(head==NULL)
return(p);
for(q=head;q->next!=NULL;q=q->next)
q->next=p;
return(head);
}
node *delete_s(node *head )
{
node *p,*q;
if(head==NULL)
{
printf(“\n list is empty”);
return (head);
}
p=head;
head=head->next;
free(p);
return (head);
}
node *delete_m(node *head )
{
node *p,*q;
int x,i;
if(head==NULL)
{
printf(“\n list is empty”);
return (head);
}
printf(“Enter data to be deleted”);
scanf(“%d”,&x);
if(head->data==x)
{
p=head;
head=head->next;
free(p);
return (head);
}
for(q=head;q->next->data!=x && q->next!=NULL;q=q->next)
if(q->next==NULL)
{
printf(“\n list is empty”);
return (head);
}
p=q->next;
q->next=q->next->next;
free(p);
return(head);
}
void display(node *head)
{
node *p;
printf(“\n\n”);
for(p=head;p!=NULL;p=p->next);
printf(“%d”,p->data);
}
6. Write a Program to concatenate two Linked List
# include <conio.h>
# include <malloc.h>
struct node
{
int value;
struct node *next;
};
struct node *rear,*start,*f;
struct node *create ();
void concat();
void print ();
int count=1;
struct node *LL1,*LL2;
void main ()
{
clrscr();
LL1=create();
LL2=create();
concat();
print();
}
struct node *create ()
{
struct node *item,*temp;
temp=(struct node *)malloc(sizeof(struct node));
printf ("\nEnter numbers of list (%d) (0) to exit: ",count);
scanf ("%d",&temp->value);
temp->next=NULL;
rear=temp;
while (1)
{
item=(struct node*)malloc(sizeof(struct node));
scanf ("%d",&item->value);
if (item->value==0)
{
break;
}
item->next=NULL;
rear->next=item;
rear=item;
if (count==1)
f=rear;
}
count++;
return (temp);
}
void concat ( )
{
f->next=LL2;
start=LL1;
}
void print ( )
{
printf ("Merged list: ");
while (start!=NULL)
{
printf (" %d ",start->value);
start=start->next;
}
}
Output :
Enter numbers of list (1) (0) to exit: 1 5 9 0
Enter numbers of list (2) (0) to exit: 7 3 4 0
Merged list: 1 5 9 7 3 4
7. Explain Stack using linked list
Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.
The top most node in the stack always contains null in its address field. Lets discuss the way in which, each operation is performed in linked list implementation of stack.
Adding a node to the stack (Push operation)
Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list implementation is different from that of an array implementation. In order to push an element onto the stack, the following steps are involved.
Time Complexity : o(1)
8. Write a Menu Driven program in C implementing all the stack operations using linked list
9. Explain Queue using linked list
Due to the drawbacks discussed in the previous section of this tutorial, the array implementation can not be used for the large scale applications where the queues are implemented. One of the alternative of array implementation is linked list implementation of queue.
The storage requirement of linked representation of a queue with n elements is o(n) while the time requirement for operations is o(1).
In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory.
In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue.
Insertion and deletions are performed at rear and front end respectively. If front and rear both are NULL, it indicates that the queue is empty.
The linked representation of queue is shown in the following figure.
10. Write a Program to create and display doubly linked list
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next,*prev;
}node;
node *create();
void display(node*);
void main()
{
node *head;
head= NULL;
head=create();
printf(“Elements of Doubly Linked List”);
display(head);
}
node *create()
{
node *p, *q, *r;
int i,n,x;
p=NULL;
printf(“Enter number of elements”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{
printf(“Enter data”);
scanf(“%d”,&x);
r= (node*)malloc(sizeof(node));
r->data=x;
r->prev=q->next=NULL;
if(p==NULL)
q=p=r;
else
q->next=r;
r->prev=q;
q=r;
}
return(p);
}
void display()
{
while(p!=NULL)
{
printf(“ %d ”, p->data);
p=p->next;
}
}
