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.
Each node in singly linked list points to next node and it appears to move in one direction. Thus SLL is unidirectional. Fig. 6.3 shows schematic diagram of singly linked list with 4 nodes.
Fig. 6. 3 : Singly Linked List
Implementation in C:
typedef struct node
{
int data;
struct node *next;
}node;
A node is defined by structures in C. This structure is called as self referential structure . This node stores integer value in data field of node. next stores address of next node and hence declared as a pointer variable.
Creation of First Node :
Step 1 : node *P;
Step 2 : P = (node*)malloc(sizeof(node));
Step 3 : P->data = 10;
Step 4 : P->next=NULL;
P1 : 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));
}
P2 : 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
6.2.2 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.
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
(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.
P=Head;
Head=Head->next
2. Dispose removed node.
(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
P3 : 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);
}
Traversing a linked list :
Fig.: Traversing a linked list
Traversal of a linked List starts from first node.
Linked List can be traversed through following code
P=HEAD;
While(P!=NULL)
P=P->next;
Concatenation of two linked list:
Concatenation of two linked List is appending one linked list at the end of other.
P4 : 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
This program creates 2 Linked list LL1 and LL2 through create() function. Function concat() and print() are used to concat and display final merged list. The starting address of the list LL2 is assigned to the rear of the first list. In order to obtain the address of last node of the first list, if condition is inserted and the address of the rear node is stored in the pointer *f. In the function concat (), the starting address of the list LL2 is assigned to rear of the list LL1. The pointer start is assigned the address of the list LL1. Using the same starting address the function print () prints the element
Reverse of a Linked List :
P5 : Singly Linked List can be reversed using following program
# include <stdio.h>
# include <conio.h>
struct node
{
int value;
struct node *next;
};
void create (void);
void reverse(void);
void show (void);
struct node *rear;
int nodes;
struct node *head;
int main ()
{
clrscr();
create();
reverse();
show ();
}
void create ( )
{
struct node *item;
printf ("Enter numbers( 0 to exit): ");
if (head==NULL)
{
head=(struct node*)malloc(sizeof(struct node));
scanf ("%d",&head->value);
head->next=NULL;
rear=head;
}
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;
}
}
void reverse()
{
struct node *prv, *cur, *next;
if (head==NULL)
{
printf ("List is empty");
return;
}
cur=head;
prv =NULL;
while (cur !=NULL)
{
next=cur->next;
cur->next=prv;
prv=cur;
cur=next;
}
head=prv;
}
void show ( )
{
printf ("\n Reverse list is: ");
while (head!=NULL)
{
node++;
printf (" %d ",head->value);
head=head->next;
}
nodes=0;
}
Output :
Enter numbers( 0 to exit): 1 2 3 4 5 6 7 0
Reverse list is: 7 6 5 4 3 2 1
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)
C implementation :
Deleting a node from the stack (POP operation)
Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked list implementation of stack is different from that in the array implementation. In order to pop an element from the stack, we need to follow the following steps :
30. Check for the underflow condition: The underflow condition occurs when we try to pop from an already empty stack. The stack will be empty if the head pointer of the list points to null.
31. Adjust the head pointer accordingly: In stack, the elements are popped only from one end, therefore, the value stored in the head pointer must be deleted and the node must be freed. The next node of the head node now becomes the head node.
Time Complexity : o(n)
C implementation
Display the nodes (Traversing)
Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of stack. For this purpose, we need to follow the following steps.
19. Copy the head pointer into a temporary pointer.
20. Move the temporary pointer through all the nodes of the list and print the value field attached to every node.
Time Complexity : o(n)
C Implementation
Menu Driven program in C implementing all the stack operations using linked list :
Due to the drawbacks discussed in the previous section of this tutorial, the array implementation cannot be used for the large-scale applications where the queues are implemented. One of the alternatives 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.
Operation on Linked Queue
There are two basic operations which can be implemented on the linked queues. The operations are Insertion and Deletion.
Insert operation
The insert operation appends the queue by adding an element to the end of the queue. The new element will be the last element of the queue.
Firstly, allocate the memory for the new node ptr by using the following statement.
There can be the two scenario of inserting this new node ptr into the linked queue.
In the first scenario, we insert element into an empty queue. In this case, the condition front = NULL becomes true. Now, the new element will be added as the only element of the queue and the next pointer of front and rear pointer both, will point to NULL.
In the second case, the queue contains more than one element. The condition front = NULL becomes false. In this scenario, we need to update the end pointer rear so that the next pointer of rear will point to the new node ptr. Since, this is a linked queue, hence we also need to make the rear pointer point to the newly added node ptr. We also need to make the next pointer of rear point to NULL.
In this way, the element is inserted into the queue. The algorithm and the C implementation is given as follows.
Algorithm
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
C Function
Deletion
Deletion operation removes the element that is first inserted among all the queue elements. Firstly, we need to check either the list is empty or not. The condition front == NULL becomes true if the list is empty, in this case , we simply write underflow on the console and make exit.
Otherwise, we will delete the element that is pointed by the pointer front. For this purpose, copy the node pointed by the front pointer into the pointer ptr. Now, shift the front pointer, point to its next node and free the node pointed by the node ptr. This is done by using the following statements.
The algorithm and C function is given as follows.
Algorithm
Write " Underflow "
Go to Step 5
[END OF IF]
C Function
Menu-Driven Program implementing all the operations on Linked Queue
Output:
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?1
Enter value?
123
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?1
Enter value?
90
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?3
printing values .....
123
90
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?2
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?3
printing values .....
90
***********Main Menu**********
==============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?4
Singly or Circular Linked List can be traversed only in forward direction since node contains only one pointer field. Node in doubly linked list contains one data field and two pointer fields.
Left link | Data | Right Link |
Fig.: Structure of a node in DLL
Left Link points to predecessor node and right link points to successor node. Information is stored in data field. Left link of First node and Right link of last node points to NULL. These two links enable bi-directional traversing, i.e. traversing the list in backward and forward direction. Hence called as bidirectional or doubly linked list.
Construction of doubly linked list :
Fig.: Doubly Linked List
Fig.6- shows example of doubly linked list. Assume Our Doubly linked List contains 3 nodes and let us denote it by A, B, and C.
Node A starts at memory address 1000.It does not have any predecessor node so left link points to NULL. Data field contains integer value ‘10’.Right Link of node in doubly linked list always stores memory address of its successor node. Hence right link of node A contains 2000 i.e memory address of node B.
Left Link of node in doubly linked list contains memory address of predecessor node. A is predecessor node of B so left link of B contains 1000 i.e. memory address of A. Data field contains value’20’ and right link contains 3000 i.e memory address of node C.
Same strategy is applied for all nodes in doubly linked list.
Node in doubly linked list is defined as
typedef struct node
{
int data;
struct node *next,*prev;
}node;
Node is defined as self referential structure which contains one data field denoted as ‘data’ and two pointers ‘*next’, ‘*prev’.*next points to successor node and *prev points to predecessor node.
C Implementation of Doubly Linked List :
P6 : 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;
}
}
1. Operations On Doubly Linked List
1. Insertion of Node
2. Deletion of Node
3. Traversing
Insertion of Node
Node can be inserted in doubly linked list at 3 positions.
(A) At the beginning
(B) In the middle
(C) At the end
Algorithms:
Assume node to be inserted is pointed by P.
(A) Insertion of node at the beginning of Doubly Linked List
Suppose our DLL consists of 3 nodes.
Insertion can be done in following steps
1. Allocate memory to node pointed by P
P= (node*)malloc(sizeof(node))
2. Update the next pointer of the node P to the Head node and make prev pointer as
NULL
P->next=Head
P->prev= NULL
3. Now update Head node’s prev pointer to point to node P and make node P as head node.
Head->prev=P
P = Head
Insertion of node in the middle of Doubly Linked List
To insert a node in the middle of DLL 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’. Suppose we want to insert new node after 2nd node.
2. Initially Q points to first node.
Q=Head
Traverse to the node after which node is to be inserted.
while(Q!=NULL)
{
if(Q->data==val)
break;
Q=Q->next
}
Now Q points to 2nd node.
P
Make the next pointer of node P to point to node next to Q. Also make the prev point of node P to point to node 2nd node.
P->next=Q->next
P->prev=Q
Now point Q’s next to P
Q->next=P
Insertion of node at the last of Doubly Linked List
1. Traverse the list to end.
Q=Head
while(Q->next!=Null)
Q=Q->next
2. Update next pointer of Q to point to P.
Q->next=P
3. Make next pointer of P to point to NULL and prev pointer to point to Q
P->prev=Q
P->next=NULL
Deletion Of Node From Dll
Node can be deleted from doubly linked list at 3 positions
(A) At the beginning
(B) In the middle
(C) At the end
Algorithms:
(A) Deletion of node from the beginning of Doubly Linked List
Assume P points to node to be deleted.
2. Now move the Head pointer to point to the next node. Also change the Head’s prev and P’s next to NULL. Then dispose the node pointed by P.
(B) Deletion of node from the middle of Doubly Linked List
To delete a node in the middle of DLL 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
1. Initially P and Head points to first node.
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
}
Now Q points to 2nd node and P points to 3rd node i.e. node to be deleted.
3. Set next of Q to next of P and prev of next of P to Q.
P->next=Q->next
P->next->prev=Q
Dispose P.
free(P)
(c) Deletion of node from the end of Doubly Linked List
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
2. Set next link of the Q and prev link of P to NULL.
Q->next=NuLL
3. Dispose off the Last Node.
free(P)
P7 : Program to perform following operations on doubly linked list
(A) Create a doubly linked list
(B) Insertion of a node
1. At the beginning of doubly Linked List
2. In the middle of doubly Linked List
3. At the end of doubly Linked List
(C) Deletion of a node
1. beginning of doubly Linked List
2. the middle of doubly Linked List
3. end of doubly Linked List
(D) Display doubly Linked List
#include <stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct node
{
char data;
struct node *next, *prev;
}node;
node *create();
node *insert_s(node *head, char x)
node *insert_b(node *head, char x)
node *insert_e(node *head, char x);
node *delete_s(node *head );
node *delete_b(node *head );
node *delete_e(node *head );
void display(node*);
void main()
{
int c,op;
char x;
node *head=NULL;
do
{
printf(“1.create\n2.insert\n3.delete\n4.display\n5.Quit”);
printf(“Enter your choice”);
scanf(“%d”, &c);
switch(c)
{
case 1:head=create();
break;
case 2:printf(“\n 1.Beginning\n2. Middle\n3.end”);
printf(“Enter your choice”);
scanf(“%d”,&op);
printf(“Enter data to be inserted”);
flushall();
x=getchar();
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(“\n 1.Beginning\n2. Middle\n3.end”);
printf(“Enter your choice”);
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;
char x;
head=NULL;
printf(“Enter string”);
flushall();
while(x=getchar()!=’\n’)
{
if(head==NULL)
{
head=p=(node *)malloc(sizeof(node));
head->next=head->prev=NULL;
}
else
{
p->next=(node*)malloc(sizeof(node));
p->next->prev=p;
p=p->next;
p->next=NULL;
}
p->data=x;
}
return(head);
}
node *insert_s(node *head, char x)
{
node *p;
p= (node*)malloc(sizeof(node));
p->data=x;
if(head==NULL)
{
Head=p;
Head->next=head->prev=NULL;
}
else
{
p->next=head;
head->prev=p;
p->prev=NULL;
head=p;
}
return(head);
}
node *insert_m(node *head, char x)
{
node *p,*q;
char y;
p= (node*)malloc(sizeof(node));
p->data=x;
printf(“Insert after which character”);
flushall();
y=getchar();
for(q=head;q!=NULL && q->data!=y;q=q->next)
{
if(q->data==y)
{
p->next=q->next;
p->prev=q;
p->next->prev=p;
p->prev->next=p;
}
else
printf(“data not found”);
return(head);
}
}
node *insert_e(node *head, char x)
{
node *p,*q;
p= (node*)malloc(sizeof(node));
p->data=x;
if(head==NULL)
{
head=p;
head->next=head->prev=NULL;
}
else
{
for(q=head;q->next!=NULL;q=q->next)
{
q->next=p;
p->prev=q;
p->next=NULL;
}
return(head);
}
node *delete_s(node *head)
{
node *p,*q;
if(head==NULL)
{
printf(“Linked list is empty”);
return(head);
}
if(head->next==NULL)
{
p=head;
free(p);
head=NULL;
}
else
{
P=head;
head=head->next;
head->prev=NULL;
free(p);
}
return(head);
}
node *delete_m(node *head)
{
node *p,*q;
char x;
if(head==NULL)
{
printf(“List is empty”);
return(head);
}
printf(“Enter data to be deleted”);
flushall();
x=getchar();
for(p=head;p!=NULL && p->data!=x;p=p->next)
{
if(p->data!=x)
{
printf(“data not found”);
return(head);
}
if(p==head)
{
head=head->next;
if(head!=NULL)
head->prev=NULL;
free(p);
}
else
{
p->prev->next=p->next;
p->next->prev=p->prev;
free(p);
}
return(head);
}
}
void display(node *head)
{
node *p;
if(head!=NULL)
{
for(p=head;p!=NULL;p=p->next)
printf(“%c”, p->data);
}
}
Output :
create
Insert
Delete
Display
Quit
Enter choice: 1
Enter a string: abcde
1. create
2. Insert
3. Delete
4. Display
5. Quit
Enter choice: 2
Beginning
Middle
End
Enter choice: 2
Enter data to be inserted:f
Insert after which character: c
1. create
2. Insert
3. Delete
4. Display
5. Quit
Enter choice: 4
abcfde
1. create
2. Insert
3. Delete
4. Display
5. Quit
Enter choice:3
Beginning
Middle
End
Enter choice: 1
1. create
2. Insert
3. Delete
4. Display
5. Quit
Enter choice:4
bcfde
Reverse of Doubly Linked List:
C Function to reverse a doubly linked list:
void reverse(node *head)
{
node *p;
if(head!=NULL)
{
for(p=head;p->next!=NULL;p=p->next)
{
for(;p!=NULL;p=p->prev)
printf(“%c”, p->data);
}
}
}
A circular linked list is a linked list in which last node points to first node i.e next pointer of last node points to first node. Circular linked list does not contain NULL pointers.
Here A is the first node and C is the last node. C points to A and hence C stores address of A.
Operations On Circular Linked List
1. Insertion of a node
2. Deletion of a node
3. Traversing
Insertion of a node
Node can be inserted at 3 positions i.e. at the beginning, in the middle and at the end of circular linked list.
Insertion at the beginning:
Assume node to be inserted is pointed by P. Insertion can be done in following steps.
1. Position pointer Q to the last node of CLL. For this traverse the list to the end of list.
Q=Head
while(Q->next!=NULL)
Q=Q->next
2. Set next link of Q to P and next link of P to Head of CLL.
Q->next=P
P->next=Head
3. Make P as Head of CLL
Head=P
Insertion in the middle
Insertion of node in the middle of CLL is same as that of Singly linked List. Refer to section 2.2.
Insertion at the end
1. Position pointer Q to the last node of CLL. For this traverse the list to the end of list.
Q= Head
while(Q->next!=Head)
Q=Q->next
2. Set next link of Q to P and next link of P to Head.
P= Q->next
Head= P->next
Deletion Of Node From Cll
Node can be deleted at the beginning, from the middle and end of CLL.
Deletion at the beginning
Assume node to be deleted is pointed by P. Deletion can be done in following steps.
1. Position pointer P to point to Head Node and Q to the last node.
P=Q= Head
while(Q->next!=Head)
Q=Q->next
2. Position pointer Head to the next of P. Set next link of Q to point to new Head.
Head=Head->next
Head= Q->next
3. Dispose P.
free(P)
Deletion in the middle of CLL
Deletion of node in middle of CLL is same as that of Singly linked list. Refer to section…
Deletion at the end of CLL
Position pointer Q to last but one node of CLL.
Q=Head
while(Q->next->next!=Head)
Q=Q->next
2. Set next link of Q to Head and P to NULL. Dispose P.
Q->next=Head
free(P)
2. Set next link of Q to Head and P to NULL. Dispose P.
Q->next=Head
free(P)
P8 : Program to create add remove & display element from circular linked list
#include<stdio.h>
#include<alloc.h>
#include<conio.h>
struct node
{
int data;
struct node *next;
};
struct node *head=NULL;
struct node *tail=NULL;
void main()
{
void addrecord();
void deleterecord();
void disrecord();
int ch;
clrscr();
do
{
printf("\n 1. To add records\n");
printf("\n 2. To delete a records\n");
printf("\n 3. To view the records\n");
printf("\n 4. To exit\n");
printf("\n Enter your choice\n");
scanf("%d",&ch);
fflush(stdin);
switch(ch)
{
case 1:addrecord();
break;
case 2:deleterecord();
break;
case 3: disrecord();
break;
case 4:exit(0);
}
} while (ch!=4);
}
void addrecord()
{
int new_data;
char ans='y';
struct node *ptr,*prev,*temp;
clrscr();
while (ans=='y')
{
temp=(struct node*)malloc(sizeof(struct node));
printf("\n Enter the new element:\n");
scanf("%d",&new_data);
fflush(stdin);
temp->data=new_data;
temp->next=NULL;
if (head==NULL)
{
head=tail=temp;
temp->next=head;
}
else
{
tail->next=temp;
tail=temp;
}
printf("\n Would you like to enter another data(y\\n): \n");
ans = getchar();
fflush(stdin);
}
}
void deleterecord()
{
struct node *ptr,*prev,*delnode;
int elt;
printf("\n Enter the enrollment number to be deleted \n");
scanf("%d",&elt);
fflush(stdin);
if (head==NULL)
{
printf("\n No elements in the list \n");
return;
}
else
{
if (head->data==elt)
{
delnode=head;
if (head==tail)
head=tail=NULL;
else
{
head=head->next;
tail->next=head;
}
}
else if (tail->data==elt)
{
for(ptr=head;(ptr!=tail);prev=ptr,ptr=ptr->next);
delnode=tail;
tail=prev;
tail->next=head;
}
else
{
for(prev=ptr=head;(ptr->data!=elt)&&(ptr!=tail);
prev=ptr,ptr=ptr->next);
if(ptr->data==elt)
{
delnode=ptr;
prev->next=ptr->next;
printf("yes...");
}
else
{
printf("Given element not found in the list");
getch();
return;
}
}
}
free(delnode);
}
void disrecord()
{
struct node *ptr,*prev=NULL;
if (head==NULL)
{
printf("\n No records to view\n");
return;
}
printf("\n The elements in the circular list are\n");
for (ptr=head;prev!=tail;prev=ptr,ptr=ptr->next)
printf("\n\n %d",ptr->data);
printf(" NULL\n\n ");
getch();
}
Abstract data type can be termed as a mathematical model which store data and methods to access and modify data. An ADT completely determines the functionality of data structure but it does not give any implementation details.
Linked List is used for storing sequence of data in computer memory. It is a sequence of nodes, each node store an element, has a successor, and in the case of doubly linked lists a predecessor. We call this ADT List. We call Linked list ADT as it contains data and operations to manipulate the data.
Operations that can be performed on linked List
1. Insertion
2. Deletion
3. Traversing
4. Searching
5. Returning first and last element
A polynomial can be represented in a linked list by simply storing the coefficient and exponent of each term. A polynomial may not have all terms, especially if it is going to be a very high order polynomial. Consider
5 x12+ 2 x9+ 4x7+ 6x5+ x2+ 12x
Now this 12th order polynomial does not have all the 13 terms (including the constant term). Each node in a linked list will need to store the variable x, the exponent and the coefficient for each term.
Exponent | Coefficient | Link |
Fig. 6.7 : Node of a Polynomial
Eg. 3x2 + 5x + 7 will represent as follows.
Thus we need to define a node structure to hold two integers , i.e. exponent and coefficient
typedef struct node
{
float coeff;
int pow;
struct node *next;
}node;
Program to create and display polynomial equation using linked list.
// Create polynomial equation using linked list
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct link
{
int coef;
int exp;
struct link *next;
};
struct link *node,*start;
int i;
void create_poly(struct link *node);
void display(struct link *node);
void main()
{
clrscr();
printf("\n create polynomial equation");
node=(struct link *)malloc(sizeof(struct link));
create_poly(node);
printf("\n Output\n");
display(node);
getch();
}
void create_poly(struct link *node)
{
char ans;
i=0;
start->next=NULL;
node=start;
fflush(stdin);
printf("\n Enter 'n' for break:-");
ans=getchar();
while(ans!='n')
{
node->next=(struct link *)malloc(sizeof(struct link));
node=node->next;
printf("\n Enter Coeficient value : ");
scanf("%d",&node->coef);
printf("\n Enter exponent value : ");
scanf("%d",&node->exp);
node->next=NULL;
fflush(stdin);
printf("\n Enter 'n' for break:-");
ans=getchar();
i++;
}
}
void display(struct link *node)
{
node=start->next;
while(node)
{
printf("%dX ^ %d",node->coef,node->exp);
node=node->next;
if(node!=NULL)
printf(" + ");
}
}
Operations on Polynomial:
Addition of two polynomials:
We will see how the addition of 2 polynomials is carried out using linked list.
Step 1: Start with the highest power in any polynomial.
If there is no term having same exponent , compare the exponents of both terms. Append the term with higher exponent to the new list and continue with the process.
Step 2: If we find that the exponents are matching, add the coefficients and then store the term in the new list.
Step 3: If one list ends earlier and the other list still contains some lower order terms, then simply append the remaining terms to the new list.
We will follow the same steps to add these two polynomials.
Consider addition of the following polynomials
Let p1, p2, p3 denotes first, second and resultant polynomial respectively.
P1 : 5 x12+ 2 x9+ 4x7+ 6x6 +x3
P2 : 7 x8 + 2 x7+ 8x6+ 6x4+ 2x2+ 40
Step 1 :
P3:
12 | 5 |
|
| 9 | 2 |
|
| 8 | 7 |
|
NULL
Step 2 : Node C of p1 and node G of p2 have same exponent and hence coefficients of them will be added and appended in P3.Same case applies for node D and H .
P3:
12 | 5 |
|
| 9 | 2 |
|
| 8 | 7 |
|
| 7 | 6 |
|
| 6 | 14 |
|
NULL
Repeat step 1 as exponents of next nodes are not matched .The resultant linked list is
Step 3:
List of p1 has ended, hence remaining nodes of p2 will be appended to p3.
The resulting polynomial is going to be
5 x12+ 2 x9+ 7 x8+ 6 x7+ 14x6 + 6x4 + x3 + 2x2 + 40
Program to add two polynomials
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct link
{
int coef;
int exp;
struct link *next;
};
struct link *node,*start,*new1,*pre;
int i;
void create_poly(struct link *node);
void display(struct link *node);
void add_poly(struct link *node);
void main()
{
clrscr();
printf("\n create polynomial equation");
node=(struct link *)malloc(sizeof(struct link));
create_poly(node);
printf("\n Polynomial equation is as follow\n");
display(node);
add_poly(node);
printf("\n after addition polynomial equation :");
display(node);
getch();
}
void create_poly(struct link *node)
{
char ans;
i=0;
start->next=NULL;
node=start;
fflush(stdin);
printf("\n Enter 'n' for break:-");
ans=getchar();
while(ans!='n')
{
node->next=(struct link *)malloc(sizeof(struct link));
node=node->next;
printf("\n Enter Coeficient value : ");
scanf("%d",&node->coef);
printf("\n Enter exponent value : ");
scanf("%d",&node->exp);
node->next=NULL;
fflush(stdin);
printf("\n Enter 'n' for break:-");
ans=getchar();
i++;
}
}
void display(struct link *node)
{
node=start->next;
while(node)
{
printf("%dX ^ %d ",node->coef,node->exp);
node=node->next;
if(node!=NULL)
printf(" + ");
}
}
void add_poly(struct link *node)
{
int t_coef,t_exp;
char ans;
struct link *temp,*tp;
node=start->next;
pre=start;
printf("\n Enter 'n' for break:-");
ans=getchar();
while(ans!='n')
{
printf("\n Enter Coeficient value : ");
scanf("%d",&t_coef);
printf("\n Enter exponent value : ");
scanf("%d",&t_exp);
pre=start;
node=start->next;
while(node)
{
if(t_exp > node->exp)
{
new1=(struct link *)malloc(sizeof(struct link ));
new1->next=node;
pre-> next=new1;
new1->coef=t_coef;
new1->exp=t_exp;
break;
}
else
{
if(t_exp == node->exp)
{
node->coef=node->coef+t_coef;
node->exp=t_exp;
break;
}
}
pre=pre->next;
node=node->next;
}
fflush(stdin);
printf("\n Enter 'n' for break:-");
ans=getchar();
}
}
Multiplication of two polynomials :
Let P1 and P2 be two polynomials to be multiplied and P3 is the resultant polynomial.
Then P1 and P2 can be multiplied in following steps.
Step 1: Multiply P1 with first term of P2.Add this to P3.
Step 2: Repeat step 1 for every term of P2.
We will see these steps with respect to an example.
P1: 10 + 14x + 8x4+7x6
P2: 11+ 8x +7x2
1. Multiply P1 10 + 14x + 8x4 +7x6 with first term of P2 i.e 11. It gives
10 + 14x+8x4+7x6
11
110 + 154x + 88x4 + 77x6
So P3 is 110 + 154x + 88x4 +77x6
2. Multiply P1 with next term i.e 8x
10 + 14x + 8x4 +7x6
8x
80x + 112x2 + 64x5 + 56x7
Add this to P3.
For addition check out the exponents. If exponents are equal add corresponding coefficients. If exponents are different then simply append it to the resultant polynomial. Refer section 6.1 addition of polynomial ---
i.e 110 + 154x + 88x4 + 77x6 + 80x + 112x2 + 64x5 + 56x7
So P3 becomes
110 +234x +112x2 + 88x4 + 64x5 + 77x6 +56x7
Now we are left with only one term i.e 7x2.
Multiply P1 with 7x2.
10 + 14x + 8x4 + 7x6
7x2
70x2 + 98x3 + 56x6 + 49x8
Add this to P3.Follow the same procedure of addition of 2 polynomials.
110 + 234x + 112x2 + 88x4 + 64x5 +77x6 + 56x7 + 70x2 + 98x3+56x6 + 49x8
So P3 becomes
110 + 234x + 182x2 + 98x3 + 88x4 + 64x5 + 133x6 + 56x7 + 49x8
Hence the resultant polynomial is
110 + 234x + 182x2 + 98x3 + 88x4 + 64x5 + 133x6 + 56x7 + 49x8
Algorithm:
Let P1 and P2 points to 2 input polynomials and P3 points to resultant polynomial. P4 is used to store intermediate results.
while(P2!=NULL)
{
P4<-P1*(term pointed by P2)
P3<-P3+P4
P2<-(P2->next)
}
Sr. No | Sequential Memory Organisation
| Linked Memory Organisation |
1
| Sequential memory organization stores data in contiguous memory locations.
| Linked memory organization stores data in non-contiguous memory locations.
|
2
| Size of data structure using sequential memory organization cannot be altered at run time. | Size of data structure using linked memory organization can be altered at run time
|
3 | Data structure using sequential memory organization is static.
| Data structure using sequential memory organization is dynamic. |
4 | Memory may be wasted in sequential memory organization
| Memory is not wasted in linked memory organization |
Reference Books:
1. E Balgurusamy, “Programming in ANSI C”, Tata McGraw-Hill, 3rd Edition.
2. Yedidyah Langsam, Moshe J Augenstein and Aaron M Tenenbaum “Data structures using C and C++” PHI Publications, 2nd Edition.
3. Reema Thareja, “Data Structures using C”, Oxford University Press, 2
nd Edition.
