DATA STRUCTURES AND APPLICATIONS (21CS32)

Module 3- Linked List

Linked Lists: Definition, classification of
linked lists. Representation of different
types of linked lists in Memory, Traversing,
Module 3 Syllabus Insertion, Deletion, Searching, Sorting, and
Concatenation Operations on Singly linked
list, Doubly Linked lists, Circular linked
lists, and header linked lists. Linked Stacks
and Queues. Applications of Linked lists –
Polynomials, Sparse matrix representation.
Programming Examples.

3.1 Linked List

We have studied that an array is a linear collection of data elements in which the elements
are stored in consecutive memory locations. While declaring arrays, we have to specify the
size of the array, which will restrict the number of elements that the array can store. For
example, if we declare an array as int marks[10], then the array can store a maximum of 10
data elements but not more than that.
But what if we are not sure of the number of
elements in advance? Moreover, to make
efficient use of memory, the elements must be
stored randomly at any location rather than in
consecutive locations.
So, there must be a data structure that removes the restrictions on the maximum number
of elements and the storage condition to write efficient programs. A linked list does not
store its elements in consecutive memory locations and the user can add any number of
elements to it.
Elements in a linked list can be accessed only in a
sequential manner But like an array, insertions and
deletions can be done at any point in the list in a
constant [Link] are 2 fields in linked list
1. Data
2. Link to next node
So we can write the structure of linked list as in
Fig. 3.1: Linked List Structure
Fig.3.1.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 1

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Linked list Definition

A linked list (Fig.3.2), or one-way list, is a linear collection of data elements, called
nodes, where the linear order is given by means of pointers. That is, each node is divided
into two parts:
 The first part contains the information of the element, and
 The second part, called the link field or nextpointer field, contains the address of the
next node in the list.

Fig3.2: representation of linked list

3.2 Representation of linked lists in Memory

Let LIST be a linked list. Then LIST will be maintained in memory as follows.
1. LIST requires two linear arrays such as INFO and LINK-such that INFO[K] and
LINK[K] contains the information part and the next pointer field of a node of
LIST.
2. LIST also requires a variable name such as START which contains the location of
the beginning of the list, and a next pointer sentinel denoted by NULL-which
indicates the end of the list.
3. The subscripts of the arrays INFO and LINK will be positive, so choose NULL =
0,unless otherwise stated.
The Fig.3.2 can be represented as Fig. 3.3 which indicates that the nodes of a list need not
occupy adjacent elements in the arrays INFO and LINK, and that more than one list may
be maintained in the same linear arrays INFO and LINK. However, each list must have its
own pointer variable giving the location of its first node.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 2

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig. 3.3: Linked List Representation in Memory.

3.3 Memory allocation; Garbage Collection
3.3.1 Memory allocation
The maintenance of linked list in memory assumes the possibility of inserting new nodes
into the list and hence requires some mechanism which provides unused memory space
for the new nodes; i.e. memory space of deleted nodes becomes available for the further
use. So for this, together with linked list in memory, a special list is considered which
consist of unused memory cells. That list which has its own pointer is called as list of
available space or free storage list or free pool or avail list. Suppose our linked lists are
implemented by parallel arrays and insertion and deletions are to be performed on our
linked list, then the unused memory cells in the arrays will also be linked together to form
a linked list using AVAIL as its list pointer (Refer Fig.3.3.1(a)). Here data is organized in
ascending order using linked list. Initially, AVAIL is pointing to 10, next memory is
assumed as location 2. So link points to 2. Then next AVAIL is 6. So link goes to 6 and
that is the end. Hence 0 as link field.

Fig. 3.3.1(a): AVAIL List.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 3

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig. 3.3.1(b): Garbage Collection.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 4

 DATA STRUCTURES AND APPLICATIONS (21CS32)

3.3.2 Garbage Collection

Suppose some memory space becomes reusable because a node is deleted from a list or
an entire list is deleted from a program, that space should be used for future use. To do
this, the operating system of computer may periodically collect all the deleted space on to
the free storage list. Any technique which does this collection is called garbage
collection(Fig.3.3.1(b)). It runs through 2 steps:
1. Computer runs through all lists, tagging those cells which are currently in use.
2. Then computer runs through memory collecting all untagged space on to the free
storage list.
Garbage collection may take place when there is only some minimum amount of space or
no space at all left in free storage list or when CPU is idle and has time to do collection.
Garbage collection is invisible for the programmer.
 Overflow: Sometimes new data are to be inserted into a data structure but there is no
available space, i.e., the free-storage list is empty. This situation is usually called
overflow. The programmer may handle overflow by printing the message
OVERFLOW. In such a case, the programmer may then modify the program by
adding space to the underlying arrays. Overflow will occur with linked lists when
AVAIL = NULL and there is an insertion.
 Underflow: The term underflow refers to the situation where one wants to delete data
from a data structure that is empty. The programmer may handle underflow by
printing the message UNDERFLOW. The underflow will occur with linked lists
when START = NULL and there is a deletion.

3.3 Linked List Operations

3.3.1 Linked list operations
1. Create
Initially we make ‘first’ as ‘NULL’ . When we create a new node, name it as ‘temp’ and
store the value in its data field. For example, enter 10 to linked list as in Fig.1. Now
connect the new node to ‘first’ as in Fig1. Now make ‘temp’ as ‘first’ so that we can
connect next new node to ‘first’ directly as in Fig. We can create ‘n’ number of nodes in
the same way.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 5

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig. 1: Create a node with insertion front.

Program code for create operation

struct node
{
int data;
struct node *link;
};
struct node*first=NULL,*temp,*last;

void create()
{
printf("\n enter the no of elements to be inserted into the list\n");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
temp = (struct node *) malloc(sizeof (struct node));
printf("Enter the data to be inserted:\n");
scanf("%d",temp->data);
temp->link=NULL;
if(first==NULL)
first=temp;
else
{
temp->link=first;

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 6

 DATA STRUCTURES AND APPLICATIONS (21CS32)

first=temp;
}
}
}

[Link] to Front
It works same as create function, by inserting new node to front. Here only one node can
be inserted at a time.
Program code for insert front operation
void insert_front()
{

temp = (struct node *) malloc(sizeof (struct node));

printf("Enter the data to be inserted:\n");
scanf("%d",temp->data);
temp->link=NULL;
}
if(first==NULL)
first=temp;
else
{
temp->link=FIRST;
FIRST=temp;
}
[Link] to End
Suppose we have empty list, then first is equal to NULL. Then directly create new node
and make it as first. But suppose we have list as in Fig.1. Now if we want to perform
insert end, then new node to be attached to right side of the last node (right of 10 here).
Create a new node and name it as temp and read new data(30) to temp as in Fig.3. Check
if lastlink=NULL and if it is not equal to NULL make last=lastlink and
lastlink=NULL as in Fig.3 and then connect new node ‘temp’ to ‘lastlink’ as in
Fig.3.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 7

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig. 3: Insert a New Node at the End of a Linked List

Program code for insert end operation

void insert_end()
{
last=first;
temp = (struct node *) malloc(sizeof (struct node));
printf("Enter the data to be inserted:\n");
scanf("%d",temp->data);
temp->link=NULL;
if(first==NULL)
first=temp;
else
{
while(last->link!=NULL)
{
last=last->link;
}
last->link=temp;
}

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 8

 DATA STRUCTURES AND APPLICATIONS (21CS32)

}
[Link] from Front
Suppose if we want to delete a node from front from the Fig.3, (delete node contains data
20), then make ‘temp’ as ‘first’ and delete tempdata and make ‘templink’ as ‘first’. If
first=NULL, then that means there is no element in the list.

Fig. 4: Example Linked list for performing Delete Front

Program code for delete front operation

void delete_front()
{
temp = first;
if(first == NULL)
printf(“\n list is empty”);
else
{
printf(“deleted element is %d”,temp->data);
first=first->link;
free(temp);
}
}

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 9

 DATA STRUCTURES AND APPLICATIONS (21CS32)

[Link] from End

Suppose if we want to delete a node from the end from the Fig.5 i.e. delete node contains
data 30. If first=NULL, that means there is no element in the list. Otherwise make ‘temp’
as ‘first’ as in Fig.5. Then check if templink= NULL, if it is not equal to NULL, then
make next node as temp and Once againcheck if templink=NULL, if not, repeat the
same previous operation until templink=NULL as in Fig.5. When templink=NULL,
delete tempdata and make lastlink to point to NULL as in Fig.5.

Fig. 5: Delete a Node from the End of a Linked List

Program code for delete end operation

void delete_end()
{
last=NULL;
temp=first;
if(first==NULL) // Check for empty list
printf("List is empty\n");
else if(first->link==NULL) // // Check for single node in SLL
{
printf("Deleted element is %d\n",temp->data);
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 10
 DATA STRUCTURES AND APPLICATIONS (21CS32)

free(first);
first=NULL;
}
else
{
while(temp->link!=NULL)
{
last=temp;
temp=temp->link;
}
last->link=NULL;
printf("Deleted element is %d\n",temp->data);
free(temp); // delete last node
}
return;
}

[Link] (Display) the linked list

Consider Fig. 6. Suppose if ‘first’ is equal to NULL, then no need of traversing. Directly
display that list is empty. Otherwise we need to traverse the whole list by traversing node
by node. For that make ‘first’ as ‘temp’ and start traversing from first and display the
traversed node data i.e. tempdata. Then make next node as temp for traversing next
node and so on until we reach NULL. If we want to count the number of nodes, then put
the counter. Initially set the count value to one and increment the count value after
traversing each node.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 11

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig. 6: Display of a Linked List

Program code for traverse operation

void display_count()
{
int count=1;
temp=first;
printf("Student details:\n");
if(first==NULL) // check for empty list
printf("Student detail is NULL and count is 0\n");
else
{
printf("\nUSN\tNAME\tBRANCH\tPHNO\tSEMESTER\n");
while(temp->link!=NULL) // iterate nodes of SLL until end node
{
count++;
printf( "\n %d”,temp->data);
temp=temp->link; // next node
}
printf( "\n %d”,temp->data);
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 12
 DATA STRUCTURES AND APPLICATIONS (21CS32)

printf("\n node count is %d\n",count);

}
return;
}
[Link] the linked list
Searching can be done for two cases:
1. List is unsorted
2. List is sorted

List is unsorted
Consider the linked list in the Fig.6. To do the search operation say for key=30 for the
unsorted list, we need to follow the following steps:
1. Set first as t
2. Repeat step 3 while t≠NULL
3. If key = tdata; search is successful and return
Else set t=tlink
4. Search failed
5. Exit
Program code for Searching a key in an Unsorted Linked List
void search()
{ struct node *temp;
int key;
temp=first;
printf(“Enter key”);
scanf(“%d”, &key);
while (temp!=NULL)
{ if(key==tempdata)
{ printf(“Search successful”);
return;
}
else temp=templink;
}
printf(“Search failed”);

List is sorted
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 13
 DATA STRUCTURES AND APPLICATIONS (21CS32)

Consider the linked list in the Fig.6. if we want to search a key element 20, then we need
to follow the step to do the search operation for the sorted list, we need to follow the
following steps:
1. Set temp=first
2. Repeat step 3 while temp≠NULL
3. If key>tempdata then set temp=templink
Else if key= tempdata then display search is success
Else display search is failed
4. Exit
Program code for Searching a key in a Sorted Linked List
void search()
{ struct node *temp;
int key;
temp=first;
printf(“Enter key”);
scanf(“%d”, &key);
while (temp!=NULL)
{ if(key>tempdata)
temp=templink;
else if(key==tempdata)
{ printf(“Search successful”);
return;
}
else
printf(“Search unsuccessful”);
}
}

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 14

 DATA STRUCTURES AND APPLICATIONS (21CS32)

[Link] a Node After a Given Node in a Linked List

void insertb()
{
int node1_data;
struct node *ptr;
temp= (struct node*)malloc(sizeof(struct node));
printf(“\n enter the element”);
scanf(“%d”,&temp->data);
temp->link=NULL;
printf(“enter the node1 data and node 2 data for entering the newnode to data\n”);
scanf(“%d%d”,& node1_data);
if(first == NULL)
{
first=temp;
}
else
{
ptr=first;
while(temp->data != node1_data)
{
ptr = ptr->link;
}
temp->link = ptr->link;
ptr->link = temp;
}
printf("\nOne node inserted!!!\n");
}
[Link] a Node After a Given Node in a Linked List
void removeSpecific()
{
struct Node *temp1 = head, *temp2;
int node_data;
printf(“\n enter the node to be deleted”);

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 15

 DATA STRUCTURES AND APPLICATIONS (21CS32)

scanf(“%d”,&node_data);

while(temp1->data != node_data)
{
if(temp1 -> link == NULL){
printf("\nGiven node not found in the list!!!");

}
temp2 = temp1;
temp1 = temp1 ->link;
}
temp2 -> link= temp1 -> link;
free(temp1);
printf("\nOne node deleted!!!\n\n");
}

3.4 Doubly Linked List

Doubly linked list is a linear collection of data elements, called nodes, where each node N
is divided into three parts:
1. An information field INFO which contains the data of N.
2. A pointer field LLINK which contains the pointer to previous node.
3. A pointer field RLINK which contains the pointer to next node.
This list also contains pointer field ‘first’ which points to first node and ‘last’ which
points to last node.
3.4.1 Representation
Fig. 3.4(a) shows the representation of doubly linked list. Using first and RLINK we can
traverse in forward direction. Using last and LLINK we can traverse in backward
direction. Structure declaration of doubly linked list is shown in Fig.3.4(b)

Fig.3.4(a): Representation of Doubly Linked List.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 16

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig.3.4(b): Structure Declaration of Doubly Linked List.

3.4.2 Representation of Doubly Linked List in Memory

Let us view how a doubly linked list is maintained in the memory. It can be represented in
memory as Fig.7.15.

Fig.7.15: Representation of Doubly Linked List in Memory.

3.5 Operations of Doubly Linked List

1. Create
Initially we make ‘first’ as ‘NULL’ as in Fig.1. When we create a new node, name it as
‘temp’ and store the value in its data field. For example, enter 10 to linked list as in Fig.
Then make tempprev and tempnext as NULL as in Fig.1. If we have only one node

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 17

 DATA STRUCTURES AND APPLICATIONS (21CS32)

which is created just now, then first=NULL; then make new node itself as first and end.
We can create ‘n’ number of nodes together. When you create one new node, then first is
not NULL now. So now we have to connect new nodes right link to old nodes left as in
Fig.1and then make first to point to temp as in Fig.1.

Fig.1: Creation of Doubly Linked List

Program code for create function

struct node
{
int data;
struct node *prev;
struct node *next;
};
typedef struct node * NODE;
NODE temp,FIRST=NULL,END=NULL;
void create()

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 18

 DATA STRUCTURES AND APPLICATIONS (21CS32)

{
int n,i=1;
printf("\n enter the no of elements to be inserted into the list\n");
scanf("%d",&n);
while(i<=n)
{
printf(“enter the details of the node %d”,i++);
temp = (NODE)malloc(sizeof (struct node));
printf("Enter the data to be inserted:\n");
scanf("%d",temp->data);
temp->prev = temp->next = NULL;
if (FIRST==NULL)
FIRST = END = temp;
else
{ END->next=temp;
temp->prev=END;
END=temp;
}
}
}

[Link] to end
It works same as create function, by inserting new node to front. Here only one node can
be inserted at a time.
Program code for insert front operation
void insertend()
{ struct node * temp;

temp = (NODE)malloc(sizeof (struct node));

printf("Enter the data to be inserted:\n");
scanf("%d",temp->data);
temp->prev = temp->next = NULL;
if (FIRST==NULL)
FIRST = LAST = temp;

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 19

 DATA STRUCTURES AND APPLICATIONS (21CS32)

else
{ END->next=temp;
temp->prev=END;
END=temp;
}
}

[Link] to front
Here we start from first position. If nothing is there in the list, then ‘first’ is pointing to
NULL. So if first is NULL then the new node created itself will be pointing to last and
first. Then we create a new node temp using malloc and insert a new value=30 to it and
make its left and right link as NULL as in Fig. 3. If first is not equal to NULL, then
connect this temp to the left link of last node as in Fig.3.

Fig.3: Steps to Inserting a new Node to the front of Doubly Linked List

Program code for insert front operation

void insert_end()
{
printf(“enter the details of the node \n”);

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 20

 DATA STRUCTURES AND APPLICATIONS (21CS32)

temp = (NODE)malloc(sizeof (struct node));

printf("Enter the data to be inserted:\n");
scanf("%d",temp->data);
temp->prev = temp->next = NULL;
if (FIRST==NULL)
FIRST = END = temp;
else
{ temp->next=FIRST;
FIRST->prev=temp;
FIRST=temp;
}
}

[Link] from Front

If first is pointing to NULL, then there is no element in the list. Otherwise we make first
as ‘temp’ and delete the data in ‘temp’, make its right link node as ‘first’. Then make first
llink as NULL as in Fig.4. If we have only one node in the list and if we perform delete
front, then the same above steps are followed. But now first = NULL. This means list is
empty. So make ‘last’ also as NULL.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 21

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig.4: Steps to Deleting a Node from the front of a Doubly Linked List

Program code for delete front operation

void Deletionfront() //Delete node from front of DLL
{
temp=FIRST;
if(FIRST==NULL) // check for empty list
printf("List is empty\n");
else if(FIRST==END) // otherwise check for single node in list
{
printf("deleted element is %d\n", temp->data);
FIRST=NULL;
END=NULL;
free(temp);
}
else // otherwise delete node from front of DLL
{
printf("deleted element is %d\n", temp->data);
FIRST =FIRST->next;
FIRST->prev=NULL;
free(temp);
}
return;

[Link] from End

Here we delete nodes from last pointer. If last is pointing to NULL, then list is empty.
Otherwise make last node as‘temp’ and delete tempdata. Then make previous node as
last and its right link to point to NULL as in [Link] if we have only one node after
deletion, and if we perform delete end, last becomes NULL. This means the list is empty.
Hence if last is pointing to NULL, and then make first also pointing to NULL.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 22

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig.5: Steps to Deleting a Node from the end of a Doubly Linked List

Program code for delete end operation

void Deletionend() // delete node at end of DLL

{
temp = END;
if(FIRST==NULL) // check for empty list
printf("List is empty\n");
else if(FIRST==END) // otherwise check for single node in list
{
printf("deleted element is %s\n", temp->ssn);
FIRST=NULL;
END=NULL;
free(temp);
}
else // otherwise delete end node from DLL
{
printf("deleted element is %s\n", temp->ssn);
END=END->prev;

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 23

 DATA STRUCTURES AND APPLICATIONS (21CS32)

END->next=NULL;
free(temp);
}
return ;
} // end of deletionend

[Link] (Display)
If first is pointing to NULL, then print that the list is empty. Else, make temp to point to
first and display tempdata. Then make temp to point to next node and display its data
and so on until temp points to NULL. So we traverse from first node to last node.

void display_count() //Display the status of DLL and count the number of nodes in it
{
temp=FIRST;
int count=0;

if(FIRST==NULL) // check for empty list

printf("the list is NULL and count is %d\n", count);
else

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 24

 DATA STRUCTURES AND APPLICATIONS (21CS32)

{
printf("the list details:\n");
while(temp!=NULL) // display all nodes in the list
{
count++;
printf(“%d”,temp->data);
temp=temp->next;
}
printf("\n node count is %d\n",count);
} // end of else
return;
} // end of display()

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 25

 DATA STRUCTURES AND APPLICATIONS (21CS32)

7. Search
Enter the search key. Make the first node pointing to temp. So start searching the key
from first node till ‘temp’ becomes NULL. Search if key is equal to tempdata. If yes,
then search is successful else make ‘temp’ pointing to next node and compare again.
Finally if there is no match found, then conclude that search is failed.
Program code for search operation
void search()
{
int key;
printf(“Enter key”);
scanf(“%d”, &key);
temp=FIRST;
while (temp!=NULL)
{
if(key==tempdata)
{
printf(“Search successful”);
return;
}
else
temp=tempnext;
}
printf(“Search failed”);
}
3.6 Circular Linked List
In a circular linked list, the last node contains a pointer to the first node of the list. We can
havea circular singly linked list as well as a circular doubly linked list. While traversing a
circular linked list, we can begin at any node and traverse the list in any direction
forward or backward, until we reach the same node where we started. Thus, a circular
linked list has no beginning and no ending. Figure 3.6 shows a circular linked list.

Figure 3.6: Circular Linked List.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 26

 DATA STRUCTURES AND APPLICATIONS (21CS32)

3.7 Operations of Circular linked lists

Fig.3.7: Operations of Circular Linked Lists.

1. When we delete from end, delete the node which lies in the last position and make its
previous node link points to first node as in Fig. 3. 7(a).
2. When we insert to end, make last node link connect to new node and new node link
connect to first node as in Fig. 3. 7 (b).
3. When we delete from front, delete the first node and make the last node link to point
to next node of first node as in Fig. 3. 7 (c).
4. When we insert to front, make last node link connect to new node and new node link
connect to first node and then make new node itself as first as in Fig. 3.7(d).
3.7.1 Create a Node
struct node
{
int data;
struct node *next;
};
struct node *head = NULL,*temp;

3.7.2 Insert into the front of the list

void insertAtBeginning()
{
struct node *newNode;
newNode = (struct node*)malloc(sizeof(struct node));
printf("\n enter the data:");

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 27

 DATA STRUCTURES AND APPLICATIONS (21CS32)

scanf("%d",&newNode -> data);

if(head == NULL)
{
head = newNode;
newNode -> next = head;
}
else
{
temp = head;
while(temp -> next != head)
temp = temp -> next;
newNode -> next = head;
head = newNode;
temp -> next = head;
}
printf("\nInsertion success!!!");
}

3.7.3 Insert into the end

void insertAtEnd()
{
struct node *newNode;
newNode = (struct node*)malloc(sizeof(struct node));
printf("\n enter the data:");
scanf("%d",&newNode -> data);
if(head == NULL)
{
head = newNode;
newNode -> next = head;
}
else
{
temp = head;
while(temp -> next != head)
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 28
 DATA STRUCTURES AND APPLICATIONS (21CS32)

temp = temp -> next;

temp -> next = newNode;
newNode -> next = head;
}
printf("\nInsertion success!!!");
}

3.7.4 Delete from front

void deleteBeginning()
{
temp=head;
if(head == NULL)
{
printf("List is Empty!!! Deletion not possible!!!");
}
else if(temp -> next == head)
{
printf(“the deleted element is %d”,&temp->data);
head = NULL;
free(temp);
}
else
{
struct node*temp2=head;
while(temp->next!=head)
{
temp=temp->next;
}
head = head -> next;
temp->next=head;
free(temp2);
}
printf("\nDeletion success!!!");
}
}
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 29
 DATA STRUCTURES AND APPLICATIONS (21CS32)

3.7.5 Delete from end

void deleteend(
{
temp=head;
if(head == NULL)
{
printf("List is Empty!!! Deletion not possible!!!");
}
else if(temp -> next == head)
{
printf(“the deleted element is %d”,&temp->data);
head = NULL;
free(temp);
}
else
{
struct node* temp2;
printf(“the deleted element is %d”,&temp->data);
while(temp -> next!=head)
{
temp2 = temp;
temp = temp -> next;
}
temp2 -> next = head;
free(temp);
}
printf("\nDeletion success!!!");
}
}

3.8 Header Linked List

A header linked list is a special type of linked list which contains a header node at the
beginning of the list. The following are the two variants of a header linked list:

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 30

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 Grounded header linked list which stores NULL in the next field of the last node as in
Fig. 7.20 (a).
 Circular header linked list which stores the address of the header node in the next
field of the last node. Here, the header node will denote the end of the list as in Fig.
7.20 (b).

7.20: Types of Header Linked Lists.

Properties of circular header lists:
 NULL pointer is not used and hence all pointers contains valid address
 Every node has a predecessor. So the 1st node may not require special case.

Algorithm for circular header lists

1. Set ptr = Link [start]
2. Repeat step 3 and 4 while ptr ≠start
3. Apply process to INFO[ptr]
4. Set ptr = Link[ptr] (pointer points to next node)
5. Exit

3.9 Linked Stacks

 We have seen how a stack is created using an array. This technique of creating a stack
is easy,but the drawback is that the array must be declared to have some fixed size.
 In case the stack is a very small one or its maximum size is known in advance, then
the array implementation of the stack gives an efficient implementation.
 But if the array size cannot be determined in advance, then the other alternative, i.e.,
linked representation, is used. The linked representation of a stack is shown in
Fig.3.9.1

Fig. 3.9.1: Linked Stack.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 31

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 32

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 The push operation is used to insert an element into the stack. The new element is
added at the topmost position of the stack. Consider the linked stack shown in Fig.
3.9.2(a). To insert an element with value 9, we first check if TOP=NULL. If this
is the case, then we allocate memory for a new node, store the value in its DATA
part and NULL in its NEXT part. The new node will then be called TOP.
However, if TOP! =NULL, then we insert the new node at the beginning of the
linked stack and name this new node as TOP. Thus, the updated stack becomes as
shown in Fig. 3.9.2(b).

Fig. 3.9.2: Linked Stack Push Operation

 Figure 3.9.3 shows the algorithm to push an element into a linked stack. In Step 1,
memory is allocated for the new node. In Step 2, the DATA part of the new node
is initialized with the value to be stored in the node. In Step 3, we check if the new
node is the first node of the linked list. This is done by checking if TOP = NULL.
In case the IF statement valuates to true, then NULL is stored in the NEXT part of
the node and the new node is called TOP. However, if the newnode is not the first
node in the list, then it is added before the first node of the list (that is, the TOP
node) and termed as TOP.

Fig. 3.9.3: Algorithm to Insert an Element in a Linked Stack

 The pop operation is used to delete the topmost element from a stack. However,
before deleting the value, we must first check if TOP=NULL, because if this is the
case, then it means that the stack is empty and no more deletions can be done. If
an attempt is made to delete a value from a stack that is already empty, an
UNDERFLOW message is printed. Consider the stack shown in Fig. 3.9.4 (a). In

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 33

 DATA STRUCTURES AND APPLICATIONS (21CS32)

case TOP! =NULL, then we will delete the node pointed by TOP, and make TOP
point to the second element of the linked stack. Thus, the updated stack becomes
as shown in Fig. 3.9.4 (b).

Fig. 3.9.4: Linked Stack Pop Operation.

 Figure 3.9.5 shows the algorithm to delete an element from a stack. In Step 1, we
first check for the UNDERFLOW condition. In Step 2, we use a pointer
 PTR that points to TOP. In Step 3, TOP is made to point to the next node in
sequence. In Step 4, the memory occupied by PTR is given back to the free pool.

Fig. 3.9.5: Algorithm to Delete an Element in a Linked Stack

SLL STACK PROGRAM

#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};

struct Node *top =NULL;

void push(int);
void pop();
void display();
void main()
{
int choice,value;

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 34

 DATA STRUCTURES AND APPLICATIONS (21CS32)

printf("\n Stack using Linked List\n");

while(1)
{
printf("\n****** MENU ******\n");
printf("1. Push\n2. Pop\[Link] \[Link]\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
push(value);
break;
case 2: pop();
break;
case 3: display();
break;
case 4: exit(0);
break;
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}

void push(int value)

{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
}
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 35
 DATA STRUCTURES AND APPLICATIONS (21CS32)

void pop()
{
if(top == NULL)
printf("\nStack is overflow!!!\n");
else
{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}

void display()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else
{
struct Node *temp = top;
while(temp->next != NULL)
{
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL",temp->data);
}
}
3.10 Linked Queue
 We have seen how a queue is created using an array. Although this technique of
creating a queue is easy, its drawback is that the array must be declared to have
some fixed size.
 If we allocate space for 50 elements in the queue and it hardly uses 20–25
locations, then half of the space will be wasted. And in case we allocate less
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 36
 DATA STRUCTURES AND APPLICATIONS (21CS32)

memory locations for a queue that might end up growing large and large, then a lot
of re-allocations will have to be done, thereby creating a lot of overhead and
consuming a lot of time.
 In case the queue is a very small one or its maximum size is known in advance,
then the array implementation of the queue gives an efficient implementation.
But if the array size cannot be determined in advance, the other alternative ,i.e.
the linked representation is used.
 In a linked queue, every element has two parts, one that stores the data and
another which holds the address of the next element. The START pointer of the
linked list is used as FRONT. Here we will also use another pointer called REAR,
which will store the address of the last element in the queue. All insertions will be
done at the rear end and all the deletions will be done at front end. If
FRONT=REAR=NULL, then it indicates that the queue is empty. The linked
representation of queue is shown in Fig. 3.10.1.

Fig. 3.10.1: Linked Stack.

 The insert operation is used to insert an element into the queue. The new element
is added as the last element of the queue. Consider the linked queue shown in Fig.
3.10.2 (a). To insert an element with value 9, we first check if FRONT=NULL. If
this is the case, then we allocate memory for a new node, store the value in its
DATA part and NULL in its NEXT part. The new node will then be called
FRONT and REAR. However, if FRONT! =NULL, then we insert the new node
at the rear end of the linked queue and name this new node as REAR. Thus, the
updated stack becomes as shown in Fig. 3.10.2(b).

Fig. 3.10.2: Linked Queue Insert Operation.

 Figure 3.10.3 shows the algorithm to insert an element into a linked queue. In Step
1, memory is allocated for the new node.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 37

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 In Step 2, the DATA part of the new node is initialized with the value to be stored
in the node.
 In Step 3, we check if the new node is the first node of the linked queue.
This is done by checking if FRONT = NULL. In case the new node is tagged as
FRONT and REAR. Also NULL is stored in the NEXT part of the node.
However, if the new node is not the first node in the list, then it is added at the
REAR end of the linked queue.

Fig. 3.10.3: Algorithm to Insert an Element in a Linked Queue.

Delete Operation
 The delete operation is used to delete the element that is first inserted
 The delete operation is used to delete the element that is first inserted into the
queue. i.e. the element whose address is stored at FRONT.
 However, before deleting the value, we must first check if FRONT=NULL,
because if this is the case, then it means that the queue is empty and no more
deletions can be done. If an attempt is made to delete a value from a stack that is
already empty, an UNDERFLOW message is printed.
 Consider the stack shown in Fig. 3.10.4(a). To delete an element, we first check if
FRONT=NULL. If it is false, then we delete the 1st node pointed by the FRONT.
The FRONT will now point to the 2nd element of the linked queue. Thus the
updated queue becomes as shown in Fig. 3.10.4(b).

Fig. 3.10.4: Linked Queue Delete Operation.

 Figure 3.10.5 shows the algorithm to delete an element froma queue. In Step 1, we
first check for the UNDERFLOW condition. In Step 2, we use a pointer

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 38

 DATA STRUCTURES AND APPLICATIONS (21CS32)

PTR that points to FRONT. In Step 3, FRONT is made to point to the next node in
sequence. In Step 4, the memory occupied by PTR is given back to the free pool.

Fig. 3.10.5: Algorithm to Delete an Element in a Linked Queue.

 Example: Create a SLL queue of N Students Data.

#include<stdio.h>
#include<stdlib.h>
struct Node
{

char usn[20],name[10],branch[5];
unsigned long long int phno;
int sem;
struct Node *next;
};
typedef struct Node * NODE;
NODE temp,front = NULL,rear = NULL;
void insert();
void delete();
void display();
void main()
{
int choice, value;

printf("\n Queue Implementation using Linked List \n");

while(1){
printf("\n****** MENU ******\n");
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 39
 DATA STRUCTURES AND APPLICATIONS (21CS32)

switch(choice){
case 1:insert();
break;
case 2: delete();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}

void insert()
{
NODE newNode;
newNode=(NODE)malloc(sizeof(struct Node));
printf("Enter USN: ");
scanf("%s",newNode->usn);
printf("Enter NAME: ");
scanf("%s",newNode->name);
printf("Enter Branch: ");
scanf("%s",newNode->branch);
printf("Enter phone Number: ");
scanf("%llu",&newNode->phno);
printf("Enter Semester: ");
scanf("%d",&newNode->sem);
newNode->next=NULL;
if(front == NULL)
{

front = rear = newNode;

front->next=NULL;
rear->next=NULL;
}
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 40
 DATA STRUCTURES AND APPLICATIONS (21CS32)

else{
rear -> next = newNode;
rear = newNode;
rear->next=NULL;
}
printf("\nInsertion is Success!!!\n");
}

void delete()
{

if(front == NULL)
printf("\nQueue is Underflow!!!\n");
else{
temp = front;
front = front -> next;
printf("\nDeleted node is with usn: %s", temp->usn);

free(temp);
}
}

void display()
{
if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
temp = front;
while(temp->next != NULL){
printf("The Student information in the node is\n");
printf("\nUSN:%s\nNAME:%s\nBRANCH:%s\nPHONE
NO.:%llu\nSEM:%d\n",temp->usn,temp->name,temp->branch,temp-
>phno,temp->sem);

temp = temp -> next;

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 41
 DATA STRUCTURES AND APPLICATIONS (21CS32)

}
printf("\nUSN:%s\nNAME:%s\nBRANCH:%s\nPHONE
NO.:%llu\nSEM:%d\n",temp->usn,temp->name,temp->branch,temp-
>phno,temp->sem);
}
}

3.11 Applications of Linked lists: Polynomials

Linked lists can be used to represent polynomials and the different operations that can be
performed on them. A polynomial is a combination of coefficients and exponents. We
represent a polynomial, each term as a node containing coefficients and exponent field, as
well as a pointer to next term. The type declarations are shown in Fig. 3.11.

3.11.1 Polynomial representation

Let us see how a polynomial is represented in the memory using a linked list. Consider a
polynomial 6x3 + 9x2 + 7x + 1. Every individual term in a polynomial consists of two
parts, a coefficient and a power. Here, 6, 9, 7, and 1 are the coefficients of the terms that
have 3, 2, 1, and 0 as their powers respectively. Every term of a polynomial can be
represented as a node of the linked list. Figure 3.11.1 showsthe linked representation of
the terms of the above polynomial.

Fig. 3.11.1: Linked Representation of a Polynomial

3.11.2 Polynomial Addition

Consider an example polynomial shown in Fig. 3.11.2. To add polynomial, we examine
their terms starting at the nodes pointed by a and b. There are three cases:

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 42

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig. 3.11.2: Example of a Polynomial

Case 1: If the exponent of a and b are equal

Consider the Fig. [Link](a). Here
aexp = bexp. So add the
coefficients of a and b and store the
result in the new link called ‘res’ as
in Fig. [Link] (b).
Fig. [Link]: Polynomial Addition if aexp = bexp.

Case 2: If the exponent of a is less than exponent of b

Consider the Fig3.11.2.2 (a). Here
aexp < bexp. So copy the
coefficient and exponent of the
bigger term i.e. ‘b’ on to the new
link called ‘res’ as in Fig. [Link]
(b). Fig. [Link]: Polynomial Addition if aexp < bexp.

Case 3: If the exponent of a is greater than exponent of b

Consider the Fig. [Link](a). Here aexp > bexp. So copy the coefficient and
exponent of the bigger term i.e. ‘a’ on to the new link called ‘res’ as in Fig. [Link]
(b).Final polynomial is shown in the Fig. [Link].

Fig. [Link]: Polynomial Addition if aexp > bexp

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 43

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig. [Link]: Resultant Polynomial after Polynomial Addition.

 Program Code for polynomial addition

polyptr addpoly (polyptr a, polyptr b)
{
polyptr c, *temp;
while( a->link && b->link)
{
if( a->exp>b->exp)
{
c->exp=a->exp;
c->coef=a->coef; {
a=a->link; if(a->link)
} {
else if( a->exp<b->exp) c->exp=a->exp;
{ c->coef=a->coef;
c->exp=b->exp; a=a->link;
c->coef=b->coef; }
b=b->link; if(b->link)
} {
else c->exp=b->exp;
{ c->coef=b->coef;
c->exp=a->exp; b=b->link;
c->coef=a->coef + b->coef; }
a=a->link; c->link= (struct poly*)malloc(sizeof(struct
b=b->link; poly));
} c=c->link;
c->link=(struct poly*)malloc(sizeof(struct c->link = NULL;
poly)); }
c=c->link;
c->link = NULL;
while (a->link || b->link)

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 44

 DATA STRUCTURES AND APPLICATIONS (21CS32)

3.12 Circular list representation of Polynomial

Fig. 3.12 : Circular list Representation of Polynomial

The zero polynomial is represented as in Fig. 3.12 (a);while a(x) = 3x14+2x8+1 can be
represented as in Fig 3.12 (b). here link field of last node points to the 1 st node in the list.
So we call this a circular linked list. To simplify the addition algorithm for polynomial
represented as circular linked list, we set coef and exp field of header node to -1. The
structure can be written as in Fig. 3.12 (c).

Program Example for polynomial

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct node // polynomial node
{
int coef;
int x,y,z;
struct node *link;
};
typedef struct node *NODE;

NODE getnode() // create a node

{
NODE x;

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 45

 DATA STRUCTURES AND APPLICATIONS (21CS32)

x=(NODE)malloc(sizeof(struct node));
return x;
} // end of getnode

NODE readpoly()
{
NODE temp,head,cur;
char ch;
head=getnode(); // create a head node and set all values to -1 it is similar to
FIRST in SLL program
head->coef=-1;
head->x=-1;
head->y=-1;
head->z=-1;
head->link=head; // self reference
do
{
temp=getnode(); // create a polynomial node
printf("\nEnter the coefficient and exponent in decreasing
order\n");
scanf("%d%d%d%d",&temp->coef,&temp->x,&temp->y,&temp-
>z );
cur=head;
while(cur->link!=head) // find the last node
cur=cur->link;
cur->link=temp; // connect new node to the last node
temp->link=head; // point back to head
printf("\nDo you want to enter more coefficients(y/n)");
fflush(stdin); // to clear the stdin buffer
scanf("%c",&ch);
} while(ch =='y' || ch == 'Y');
return head; // return the polynomial list
} // end of readpoly

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 46

 DATA STRUCTURES AND APPLICATIONS (21CS32)

int compare(NODE a,NODE b) // function to compare the A and B polynomial

nodes
{
if(a->x > b->x)
return 1;
else if(a->x < b->x)
return -1;
else if(a->y > b->y)
return 1;
else if(a->y < b->y)
return -1;
else if(a->z > b->z)
return 1;
else if(a->z < b->z)
return -1;
return 0;
} // end of compare

void attach(int cf,int x1,int y1, int z1, NODE *ptr) // function to attach the A and
B polynomial node to C Polynomial
{
NODE temp;
temp=getnode();
temp->coef=cf;
temp->x=x1;
temp->y=y1;
temp->z=z1;
(*ptr)->link=temp;
*ptr=temp;
} // end of attach

NODE addpoly(NODE a,NODE b) // function to add polynomial A and B i.e,

C=A+B
{
NODE starta,c ,lastc;
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 47
 DATA STRUCTURES AND APPLICATIONS (21CS32)

int sum,done=0;
starta=a;
a=a->link;
b=b->link;
c=getnode(); // create list C to store A+B
c->coef=-1;
c->x=-1;
c->y=-1;
c->z=-1;
lastc=c;
do{
switch(compare(a,b))
{
case -1:attach(b->coef,b->x,b->y,b->z,&lastc);
b=b->link;
break;
case 0:if(starta==a) done=1;
else{
sum=a->coef+b->coef;
if(sum)
attach(sum,a->x, a->y,a->z,&lastc);
a=a->link;b=b->link;
}
break;
case 1: if(starta==a) done=1;
attach(a->coef,a->x, a->y,a->z,&lastc);
a=a->link;
break;
}
}while(!done); // repeate until not done
lastc->link=c; // point back to head of C
return c; // return answer
}

void print(NODE ptr) // to print the polynomial

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 48
 DATA STRUCTURES AND APPLICATIONS (21CS32)

{
NODE cur;
cur=ptr->link;
while(cur!=ptr) // To print from HEAD node till END node
{
printf("%d*x^%d*y^%d*z^%d",cur->coef,cur->x, cur->y,
cur->z);
cur=cur->link; // move to next node
if (cur!=ptr)
printf(" + ");
}
} // end of print

void evaluate(NODE ptr) // function to evaluate the final polynomial

{
int res=0;
int x,y,z, ex,ey,ez,cof;
NODE cur;
printf("\nEnter the values of x, y,z"); // read values of X, Y and Z
scanf("%d", &x);
scanf("%d", &y);
scanf("%d", &z);
cur=ptr->link; // start with HEAD
while(cur!=ptr) // Repeat until the end of list
{
ex=cur->x; // exponent of x
ey=cur->y; // exponent of y
ez=cur->z; // exponent of z
cof=cur->coef; // coefficient
res+=cof*pow(x,ex)*pow(y,ey)*pow(z,ez); // compute
result for each polynomial
cur=cur->link; // move to next node
}
printf("\nresult: %d",res);
} // end of evaluate
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 49
 DATA STRUCTURES AND APPLICATIONS (21CS32)

void main(void)
{
int i, ch;
NODE a=NULL,b,c;
while(1)
{
printf("\n1: Represent first polynomial A");
printf("\n2: Represent Second polynomial B");
printf("\n3: Display the polynomial A");
printf("\n4: Display the polynomial B");
printf("\n5: Add A & B polynomials"); // C=A+B
printf("\n6: Evaluate polynomial C");
printf("\n7: Exit");
printf("\n Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the elements of the polynomial A");
a=readpoly();
break;
case 2:printf("\nEnter the elements of the polynomial B");
b= readpoly();
break;
case 3: print(a); // display polynomial A
break;
case 4:print(b); // display polynomial A
break;
case 5: c=addpoly(a,b); // C=A+B
printf("\nThe sum of two polynomials is: ");
print(c); // display polynomial C
printf("\n");
break;
case 6:evaluate(c); // Evaluate polynomial C
break;
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 50
 DATA STRUCTURES AND APPLICATIONS (21CS32)

case 7: return;
default: printf("\nInvalid choice!\n");
} //end of switch
} // end of while
} // end of main

3.13 Applications of Linked lists: Sparse matrix representation

 In linked representation, we use linked list data structure to represent a sparse matrix.
In this linked list, we use two different nodes namely header node and element node.
 Header node consists of three fields and element node consists of five fields as shown
in the Fig. 3.13.
 Consider the sparse matrix used in the Triplet representation of Fig. 3.13.1(a). This
sparse matrix can be represented using linked representation as shown in the below
image.
 In this representation, H0, H1..., H5 indicates the header nodes which are used to
represent indexes.
 Remaining nodes are used to represent non-zero elements in the matrix, except the
very first node which is used to represent abstract information of the
sparse matrix (i.e., It is a matrix of 5 X 6 with 6 non-zero elements).
 In this representation, in each row and column, the last node right field points to its
respective header node (Fig 3.13.1 (b)).

Fig 3.13: Header and element node representation.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 51

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig 3.13. Linked list representation of sparse matrix

Sparse matrix using Linked List C program

#include<stdio.h>
#include<stdlib.h>
struct list
{
int row, column, value;
struct list *next;
};
struct list *HEAD=NULL;
void insert(int, int , int );
void print ();
int main()
{
int Sparse_Matrix[4][4] ={ {9 , 0 , 0 , 0 },{0 , 0 , 0 , 0 },{0 , 5 , 0 , 8 },{3 , 0 , 0 , 0 } };
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
if(Sparse_Matrix[i][j] != 0)
{
insert(i, j, Sparse_Matrix[i][j]);
}
}
}
// print the linked list.
print();
}
void insert( int r, int c, int v)
{
struct list *ptr,*temp;
int item;
ptr = (struct list *)malloc(sizeof(struct list));
if(ptr == NULL)

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 52

 DATA STRUCTURES AND APPLICATIONS (21CS32)

{
printf("\n OVERFLOW");
}
else
{
ptr->row = r;
ptr->column = c;
ptr->value = v;
if(HEAD == NULL)
{
ptr->next = NULL;
HEAD = ptr;
}
else
{
temp = HEAD;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
}
}
}
void print()
{
struct list *tmp = HEAD;
printf("ROW NO COLUMN NO. VALUE \n");
while (tmp != NULL)
{
printf("%d \t\t %d \t\t %d \n", tmp->row, tmp->column, tmp->value);
tmp = tmp->next;
}
}
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 53
 DATA STRUCTURES AND APPLICATIONS (21CS32)

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 54

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Question Bank
1. What is linked list? Explain the different types of linked list with examples.
2. Give a node structure to create a linked list of integers and write a C function to
perform the following.
a. Create a three-node list with data 10, 20 and 30
b. Inert a node with data value 15 in between the nodes having data values 10
and 20
c. Delete the node which is followed by a node whose data value is 20
d. Display the resulting singly linked list.
3. With node structure show how would you store the polynomials in linked lists? Write
C function for adding two polynomials represented as circular lists.
4. Write a note on: i. Linked representation of sparse matrix ii. Doubly linked list.
5. Write a function to insert a node at front and rear end in a circular linked list. Write
down sequence of steps to be followed.
6. What is linked list? Explain the different types of linked list with examples.
7. Give a node structure to create a linked list of integers and write a C function to
perform the following.
a) Create a three-node list with data 10, 20 and 30
b) Inert a node with data value 15 in between the nodes having data
values 10 and 20
c) Delete the node which is followed by a node whose data value is 20
d) Display the resulting singly linked list.
8. With node structure show how would you store the polynomials in linked lists? Write
C function for adding two polynomials represented as circular lists.
9. Write a note on: i. Linked representation of sparse matrix ii. Doubly linked list.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 55

 DATA STRUCTURES AND APPLICATIONS (21CS32)

10. Write a function to insert a node at front and rear end in a circular linked list. Write
down sequence of steps to be followed.
11. Write a C program to perform the following operations on doubly linked list: i. Insert
a node ii. Delete a node.
12. Write a C function to insert a node at front and delete a node from the rear end in a
circular linked list.
13. Describe the doubly linked lists with advantages and disadvantages. Write a C
function to delete a node from a circular doubly linked list with header node.
14. Write a C function for the concatenation of linked lists.
15. Write a C function to add two-polynomials represented as circular list with header
node.
16. Write a C function to perform the following i. Reversing a singly linked list ii.
Concatenating singly linked list. iii. Finding the length of the circular linked list. iv.
To search an element in the singly linked list
17. Write a node structure of linked stack. Write a function to perform push and pop
operations on linked stack.
18. List out the differences between doubly linked list over singly linked list. Write a C
functions to perform the following i. Inserting a node into a doubly linked circular list
ii. Deletion from a doubly linked circular list.
19. Write a function for singly linked lists with integer data, to search an element in the
list that is unsorted and a list that is sorted.
20. Given 2 singly linked lists. LIST-1 and LIST-2. Write an algorithm to form a new list
LIST-3 using concatenation of the lists LIST-1 and LIST-2.
21. Write a note on header linked list. Explain the widely used header lists with
diagrams. 23. Illustrate with examples how to insert a node at the beginning, INSERT
a node at intermediate position, DELETE a node with a given value
22. List out any 2 differences between doubly linked lists and singly linked list, Illustrate
with example the following operations on a doubly linked list: i. Inserting a node at
the beginning. ii. Inserting at the intermediate position. iii. Deletion of a node with a
given value
23. For the given sparse matrix write the diagrammatic linked list representation

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 56