Chapter 3 – Linked Lists

Linear Data Structures:

A linear data structure is one where data items are organized in a sequence, one after the other. This
means that while traversing, each element is accessed one at a time, in order. In linear data structures,
only one element can be accessed directly during traversal. The entire structure can be traversed in
one pass.

These data structures are easy to implement because computer memory is organized in a linear way.
Examples of linear data structures include arrays, stacks, queues, and linked lists.
• Array: A collection of data items of the same type.
• Stack: A Last In First Out (LIFO) structure, where the last element added is the first to be
removed. All operations are done from one end, called the TOP.
• Queue: A First In First Out (FIFO) structure, where the first element added is the first to be
removed. In a queue, insertion is done at the REAR and deletion at the FRONT.
• Linked List: A collection of nodes, where each node contains data and a reference (or link)
to the next node in the sequence.

Non-Linear Data Structures:

In a non-linear data structure, data items are not organized sequentially. Each element can be
connected to more than one other element, reflecting a special relationship between them. This
means that you cannot traverse all elements in a single pass.

Examples of non-linear data structures include trees and graphs.

• Tree: A collection of nodes arranged hierarchically, forming parent-child relationships.
• Graph: A collection of vertices (or nodes) and edges (connections) between these vertices.
The edges represent relationships among the vertices, which store data.

Linked List: Basic terminologies

A linked list, in simple terms, is a linear collection of data elements. These data elements are called
nodes. A linked list can be perceived as a sequence of nodes in which each node contains one or more
data fields and a pointer to the next node.

In the above diagram, we can see a linked list where each node has two parts: the data part that
contains data (an integer), and the address part that contains a pointer to the next node. The data
part of the node can store simple data types like numbers, arrays, or structures. The pointer part
holds the address of the next node in the sequence.

The last node in the linked list does not point to any other node, so it contains a special value called
NULL. In the above figure, NULL is represented by X. This NULL value tells us that we've reached the

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

end of the list. Since each node in a linked list points to another node of the same type, this structure
is known as a **self-referential structure**.

Linked lists also have a special pointer variable called *START/HEAD*, which stores the address of
the first node in the list. To go through (or "traverse") the entire list, we use HEAD. It points to the
first node, and the pointer in each node then leads to the next one, creating a chain of nodes. If HEAD
equals NULL, it means the linked list is empty and has no nodes.

While implementing a singly linked list in C, we can define a node using the following code:
struct node {
int data;
struct node *next;
};

Let's see how a linked list is stored in memory. The node has two parts:
• DATA: This part stores the information.
• NEXT: This part stores the address of the next node in the sequence.

Together, these two fields allow us to link one node to another, forming a chain of nodes. Refer to
above figure to see how this looks.

In the figure, we see that the variable START is

used to store the address of the first node. In this
example, START is set to 1, meaning the first data
is stored at address 1, which contains the value
"H." The NEXT part of this node holds the address
of the next node, which is 4. So, we go to address
4 to get the next data item. At address 4, the data
is "E." The NEXT part of this node tells us to go to
address 7 to find the next node. At address 7, we
retrieve the data "L." We continue this process,
moving from one node to the next by following
the addresses stored in the NEXT field. This
process continues until we reach a node where
the NEXT part contains the value -1 or NULL.
This indicates that we’ve reached the end of the
linked list.

Linked Lists vs. Arrays

Both arrays and linked lists store a collection of data elements in a linear order. However, there are
key differences between them:
• In an array, data is stored in consecutive memory locations, while in a linked list, nodes are
scattered throughout memory, with each node pointing to the next.
• Arrays allow random access, meaning any element can be accessed directly using an index.
In contrast, linked lists only allow sequential access, so nodes must be accessed one by
one, starting from the first node.
• Both arrays and linked lists support insertions and deletions at any point, but linked lists do
this more efficiently because of their dynamic structure.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

 • Another major advantage of linked lists is their flexibility in size. For example, if an array is
declared as int marks[20], it can only store 20 elements. A linked list, however, can grow as
needed since there is no limit on the number of elements.

Linked lists are efficient for storing related data and performing operations like insertion, deletion,
and updating. However, they require extra space for storing pointers to the next node.

Memory Allocation and Deallocation for Linked Lists

When a new node is added to an existing linked list, the system first finds free memory space and
then uses it to store the new data. For example, in the following figure, the linked list stores student
roll numbers, biology marks, and a pointer to the next node. If a new student joins the class, their
marks are recorded by finding free memory and adding their information to the linked list. In the
figure, the grey area shows available free memory. One of these free memory locations can be used
to store the new data.

Figure (a) Students’ linked list and (b) linked list after the insertion of new student’s record

Now, how do we know which memory is available and which is occupied? When a node is deleted
from a linked list, who changes its memory status from occupied to available? The operating system
manages this process. It tracks free and occupied memory automatically, without intervention from
the user or programmer.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Deleting Nodes from a Linked List

When a node (or the entire linked list) is deleted, its memory needs to be returned to the free pool so
other programs can reuse it. The operating system handles this by adding the freed memory back to
the free pool. It checks memory when the CPU is idle or when other programs need space.

The operating system scans memory to find unused cells, collects them, and adds their addresses to
the free pool. This process is called garbage collection, which ensures memory is efficiently reused.

Types of Linked Lists

1. Singly Linked List:

In a singly linked list, each node contains two parts: data and a pointer to the next node in the
sequence. The list is traversed in one direction, starting from the first node (HEAD) and moving
towards the last node, which points to NULL.
• Example:

HEAD -> Node1 -> Node2 -> Node3 -> NULL

2. Doubly Linked List:

A doubly linked list has nodes that contain three parts: data, a pointer to the next node, and a
pointer to the previous node. This allows traversal in both forward and backward directions.
• Example:

NULL <- Node1 <-> Node2 <-> Node3 -> NULL

3. Circular Linked List:

In a circular linked list, the last node points back to the first node, forming a circle. There’s no NULL
in the list, and it can be either singly or doubly linked.
• Singly Circular Linked List:

HEAD -> Node1 -> Node2 -> Node3 -> HEAD

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

 • Doubly Circular Linked List:

•
HEAD <-> Node1 <-> Node2 <-> Node3 <-> HEAD

SINGLY LINKED LIST

A singly linked list is a data structure consisting of a series of nodes. Each node contains two parts:
data and a pointer to the next node in the sequence. The list starts at a node called HEAD and ends at
a node that points to NULL.

Operations on Singly Linked Lists

Creating a node
Step 1: Allocate the memory needed for storing the node
Malloc function can be used for allocating the necessary memory.
Step2: Assign values to the node.

Creating a list

Step 1: Repeat steps 2 and 3 for n times (for creating a list of n nodes).
Step 2: Create a new node.
• Allocate memory for the node.
• Assign values to the node (e.g., data).
Step 3: Link the newly created node to the list.
• If it’s the first node, set HEAD = newly created node.
• For subsequent nodes, link the new node to the current last node.
• Update the last node pointer to the new node.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Printing the List

Step 1: Start from the HEAD node.

Step 2: Traverse each node and print the data.
Step 3: Move to the next node by following the link (pointer).
Step 4: Stop when you reach a node with NULL (end of the list).

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Inserting a Node at the Beginning
Step 1: Create a new node.
• Allocate memory for the node.
• Assign the data value to the new node.
Step 2: Link the new node to the list.
• Set the new node’s next pointer to point to the current HEAD.
• Update HEAD to point to the new node.

Inserting a Node at the End

Step 1: Create a new node.
• Allocate memory and assign data to the new node.
Step 2: Check if the list is empty.
• If the list is empty, set HEAD to point to the newly created node and exit the operation.
Step 3: Traverse the list.
• Start from the HEAD and move through each node until you reach the last node (where next
is NULL).
Step 4: Link the new node.
• Set the next pointer of the last node to point to the newly created node.

Inserting a Node at a Specified Position

Step 1: Insert at the beginning if the list is empty or the position is less than 1.
• If the list is empty or the position is less than 1, insert the new node at the beginning.
Step 2: Insert at the end if the position is greater than the size of the list.
• If the specified position exceeds the current list size, insert the new node at the end.
Step 3: Create a new node.
• Allocate memory for the node and assign data to it.
Step 4: Traverse to the node just before the specified position.
• Move through the list to the node just before the desired position.
Step 5: Insert the new node.
• Set the next pointer of the new node to point to the next of the current node.
• Update the next of the current node to point to the new node.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Deleting the First Node
Step 1: Check if the list is empty.
• If the list is empty, exit the operation (return NULL), as deletion is not possible.
Step 2: Update the HEAD.
• Set HEAD to point to the second node in the list.
Step 3: Free the memory of the old first node.
• Deallocate the memory of the node that was previously the first node.

Deleting the Last Node

Step 1: Check if the list is empty.
• If the list is empty, exit the operation (return NULL), as deletion is not possible.
Step 2: Check if the list has a single node.
• If the list has only one node, free memory of the node and exit the operation (return
NULL).
Step 3: Traverse to the second-to-last node.
Step 4: Update the second-to-last node’s next pointer to NULL.
Step 5: Free the memory of the old last node.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Deleting a Node at a Specified Position
Step 1: Delete First Node if the list is empty or the position is less than 1.
Step 2: Delete the Last Node if the position is greater than the size of the list.
Step 3: Traverse to the node just before the specified position.
Step 4: Update the next pointer.
Set the next of the current node to the next of the node you want to delete.
Step 5: Free the memory of the node being deleted.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Deleting a Node with a Specified Value

Step 1: Check if the list is empty.

• If the list is empty, return NULL as deletion is not possible.
Step 2: Check if the value matches the head node’s value.
• If the head node contains the specified value:
○ Update HEAD to point to the second node.
○ Free the memory of the first node.
○ Return the updated HEAD.
Step 3: Traverse through the list.
• Start from HEAD and search for the node containing the specified value, keeping track of the
previous node.
Step 4: Update the links.
• Set the next of the previous node to point to the next of the node being deleted.
Step 5: Free the memory of the node with the specified value.
• Deallocate the memory of the node that was deleted.

Searching for a Value in the List

Step 1: Traverse the list.

• Start at the HEAD and move through each node.
Step 2: Check each node's data.
• If a match is found, return true.
• If no match is found, continue to the next node.
Step 3: Stop when you reach the end or find the value.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

DOUBLY LINKED LISTS

A doubly linked list is a type of linked list where each node contains three parts:
1. Data
2. A pointer to the next node
3. A pointer to the previous node

This allows traversal in both directions (forward and backward). The structure of a doubly linked list
can be represented in C as:

struct node {
struct node *prev; // Pointer to the previous node
int data; // Data part
struct node *next; // Pointer to the next node
};
• The PREV field of the first node and the NEXT field of the last node will contain NULL,
indicating the start and end of the list.
• The PREV pointer enables backward traversal, while the NEXT pointer enables forward
traversal.

Though a doubly linked list requires more memory (due to two pointers per node), it offers greater
flexibility compared to a singly linked list. It allows easier insertion and deletion operations at both
ends and improves efficiency in searching, as we can move in both directions.

For example, in memory, the list may look like this:

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

 • HEAD points to the first node.
• The list stores data, such as the characters H, E, L, L, and O in a sequence.
• The PREV field of the first node is NULL, and the NEXT field of the last node is also NULL,
marking the boundaries of the list.

By traversing from the first to the last node or vice versa, we can access all elements efficiently.

Advantages of Doubly Linked List

1. Bidirectional Traversal:
○ A doubly linked list allows traversal in both directions—forward and backward—
making it more flexible than a singly linked list.
2. Efficient Deletion and Insertion:
○ Insertion and deletion of nodes at both the beginning and the end of the list are
more efficient. No need to traverse the entire list to remove or insert at the end.
3. More Versatile Operations:
○ Some operations, such as reversing the list or implementing complex data
structures (like deques or complex sorting algorithms), are easier with a doubly
linked list.

Operations on Doubly Linked Lists

Creating a node
Step 1: Allocate the memory needed for storing the node
○ Malloc function can be used for allocating the necessary memory.
Step2: Assign values to the node.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Creating a list

Step 1: Repeat steps 2 and 3 for n times (to create a list of n nodes).
Step 2: Create a new node:
• Allocate memory for the node.
• Assign values to the node (e.g., data).
• Set prev = NULL and next = NULL initially.
Step 3: Link the newly created node to the list:
• If it's the first node, set HEAD = newly created node.
• For subsequent nodes:
○ Set the next pointer of the current last node to the new node.
○ Set the prev pointer of the new node to the current last node.
○ Update the last node pointer to the new node.

Printing the List

Step 1: Start from the HEAD node.

Step 2: Traverse each node and print the data.
Step 3: Move to the next node by following the link (pointer).
Step 4: Stop when you reach a node with NULL (end of the list).

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Printing the List in Reverse Order

Step 1: Start from the HEAD node.

Step 2: Traverse through the list and reach the last node.
Step 3: Traverse each node and print the data.
Step 3: Move to the previous node by following the prev link (pointer).
Step 4: Stop when you reach a node with NULL (end of the list).

Inserting a Node at the Beginning of a Doubly Linked List

Step 1: Create a new node.
• Allocate memory for the node.
• Assign the data value to the new node.
Step 2: Link the new node to the list.
• Set the new node’s next pointer to point to the current HEAD.
• If the list is not empty, set the prev pointer of the current HEAD to point to the new node.
• Update HEAD to point to the new node.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Inserting a Node at the End of a Doubly Linked List
Step 1: Create a new node.
• Allocate memory for the node.
• Assign data to the new node.
Step 2: Check if the list is empty.
• If the list is empty, set HEAD to point to the newly created node and exit the operation.
Step 3: Traverse the list.
• Start from the HEAD and move through each node until you reach the last node (where next
is NULL).
Step 4: Link the new node.
• Set the next pointer of the last node to point to the newly created node.
• Set the prev pointer of the newly created node to point to the last node.

Inserting a Node at a Specified Position in a Doubly Linked List

Step 1: Insert at the beginning if the list is empty or the position is less than 1.
• If the list is empty or the position is less than 1, insert the new node at the beginning.
Step 2: Insert at the end if the position is greater than the size of the list.
• If the specified position exceeds the current list size, insert the new node at the end.
Step 3: Create a new node.
• Allocate memory for the node.
• Assign data to the new node.
Step 4: Traverse to the node just before the specified position.
• Move through the list starting from HEAD to reach the node just before the desired position.
Step 5: Insert the new node.
• Set the next pointer of the new node to point to the next of the current node.
• Set the prev pointer of the new node to point to the current node.
• Update the prev pointer of the node that follows the current node (if it exists) to point to the
new node.
• Update the next pointer of the current node to point to the new node.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Deleting the first node from a Doubly Linked List

Step 1: Check if the list is empty.

• If the list is empty, exit the operation (return NULL), as deletion is not possible.
Step 2: Update the HEAD.
• Set HEAD to point to the second node in the list.
Step 3: Update the previous pointer of new head to NULL
• Check if the head is NULL. If it is not NULL, set the previous of head to NULL.
Step 4: Free the memory of the old first node.
• Deallocate the memory of the node that was previously the first node.

Deleting the last node from a Doubly Linked List

Step 1: Check if the list is empty.

• If the head h is NULL, return NULL since there are no nodes to delete.
Step 2: Traverse to the last node.
• Initialize a pointer c to the head h.
• Use a loop to traverse through the list until you reach the last node (where c->next
is NULL).

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Step 3: Check if the last node is the only node in the list. In this case, set head to NULL (the list
will become empty after deletion).
• If the previous pointer (c->prev) of the current node c is NULL, it means c is the only
node in the list.
Step 4: Update the previous node's link.
• If the list has more than one node, update the next pointer of the node before the last
node (c->prev->next) to NULL, effectively removing the last node from the list.
Step 5: Free the memory of the last node.
• Deallocate the memory used by the last node c using the free() function.
Step 6: Return the updated head pointer.
• Return the updated head h (which might be NULL if the list became empty).

Deleting a node from a Doubly Linked List based on its position

Step 1: Check if the list is empty or if the position is less than or equal to 1.
○ If the head head is NULL (the list is empty) or if the position pos is less than or equal
to 1, call the function to delete the first node (deleteFirstNode(head)) and return the
updated list.
Step 2: Check if the position is greater than or equal to the size of the list.
○ Calculate the size of the list using a helper function (listSize(head)).
○ If the specified position is greater than or equal to the size of the list, call the
function to delete the last node (deleteLastNode(head)) and return the updated list.
Step 3: Traverse the list to the node just before the specified position.
○ Use a loop to move pre to the node just before the specified position by iterating
pos-1 times.
Step 4: Identify the node to be removed and its adjacent nodes.
○ Set the pointer curr to the node that needs to be removed (pre->next).
○ Set the pointer nxt to the node that comes after curr (curr->next).
Step 5: Update the links of the nodes pre and nxt to bypass curr.
○ Set the prev pointer of nxt to pre (nxt->prev = pre).
○ Set the next pointer of pre to nxt (pre->next = nxt).
Step 6: Free the memory of the node to be removed (curr).
○ Deallocate the memory used by the node curr using the free() function.
Step 7: Return the updated head pointer.
○ Return the updated head head after the deletion.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Deleting a node from a Doubly Linked List based on its value

Step 1: Search for the node containing the specified value.

• Use a helper function search(head, val) to find the node curr that contains the value val. If the
value is not found, curr will be NULL.
Step 2: Check if the node with the given value exists.
• If the curr is NULL, either the value was not found or the list is empty. In this case, return the
original head without making any changes.
Step 3: Identify the previous (pre) and next (nxt) nodes relative to the node to be removed.
• Set pre to the node preceding curr (curr->prev).
• Set nxt to the node following curr (curr->next).
Step 4: Check if the node to be deleted is the first node in the list.
• If pre is NULL, this means curr is the first node in the list. In this case, call the function
deleteFirstNode(head) to delete the first node and return the updated list.
Step 5: Check if the node to be deleted is the last node in the list.
• If nxt is NULL, this means curr is the last node in the list. In this case, call the function
deleteLastNode(head) to delete the last node and return the updated list.
Step 6: Update the links of the adjacent nodes.
• Set the prev pointer of the nxt node to pre (nxt->prev = pre).
• Set the next pointer of the pre node to nxt (pre->next = nxt).
Step 7: Free the memory of the node to be removed.
• Deallocate the memory used by the node curr using the free() function.
Step 8: Return the updated head pointer.
• Return the updated head head after the deletion.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Search for a Node with a Specific Value in a Doubly Linked List

Step 1: Initialize the search pointer.

○ Set curr to point to the head of the list (curr = head).
Step 2: Traverse through the list.
○ While curr is not NULL and the data field of the curr node does not match the key:
▪ Move to the next node (curr = curr->next).
Step 3: Check if the search was successful.
○ If curr is NULL, it means the value was not found in the list, and the traversal has
reached the end of the list.
○ If the data of curr matches the key, the node containing the key has been found.
Step 4: Return the result.
○ Return the node curr if the key is found, otherwise return NULL.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

POLYNOMIAL ADT

Polynomials can be efficiently represented using singly linked lists, which are useful for manipulating
symbolic polynomials.

General Form of a Polynomial:

A polynomial can be expressed as: A(x)=amxem+am−1xem−1++a1xe1+a0xe0

Where:
• ai are the non-zero coefficients.
• ei are the non-negative integer exponents.
• The exponents follow the order em > em−1 > ⋯ > e1 ≥ 0

Polynomial Representation in Linked Lists:

Each term in the polynomial is represented as a node in a singly linked list. The nodes contain:
• Coefficient: Stores the coefficient ai
• Exponent: Stores the exponent ei
• Next pointer: Points to the next term in the polynomial.

Example of a Node Structure:

struct PolyNode {
int coeff; // coefficient
int exp; // exponent
struct PolyNode *next; // pointer to the next term
};
For instance, the polynomial 5x3+2x2+3x+1 would be represented as:
5 3 2 2 3 1 1 0

Key Points:
• Nodes: Each node contains a term with both the coefficient and the exponent.
• Linked Structure: The terms are linked together in decreasing order of exponents.
• Efficiency: Linked lists allow for easy insertion, deletion, and traversal of terms, making it
an ideal choice for polynomial manipulations like addition, subtraction, and multiplication.

Polynomial Addition Using Singly Linked Lists

To add two polynomials represented as singly linked lists, we process the terms of both
polynomials in parallel, starting from their respective heads.
Steps for Polynomial Addition:
1. Compare Exponents:
o If the exponents of the current terms in both polynomials a and b are equal:
1. Add the coefficients of the two terms.
2. Create a new term in the result list d with the sum of the coefficients and the
common exponent.
o If the exponent of the current term in a is less than that in b:
1. Create a duplicate of the current term in b.
2. Attach this term to the result list d.
3. Move to the next term in b.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

 o If the exponent of the current term in a is greater than that in b:
1. Create a duplicate of the current term in a.
2. Attach this term to the result list d.
3. Move to the next term in a.
2. Continue the Process:
o Repeat the above steps until all terms in both polynomials a and b have been
processed.
3. Remaining Terms:
o If one polynomial is exhausted before the other, append all the remaining terms of
the non-exhausted polynomial directly to the result d.
Example:
If we have:
• Polynomial a = 5x3+3x2+1
• Polynomial b = 4x3+2x+6
• The result of a+b would be: d = (5+4) x3+3x2+2x+(1+6)
Following Figure shows the generation of the first three term of two polynomials a and b.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Following is the C program that implements polynomial ADT and its operations:
#include <stdio.h>
#include<stdlib.h>
struct term
{
int coeff,pow;
struct term *next;
};

typedef struct term node;

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

node * createNode()
{
node *NewNode = (node *)malloc(sizeof(NewNode));
printf("\nEnter Coeff and Pow values:");
scanf("%d %d",&NewNode->coeff,&NewNode->pow);
NewNode->next = NULL;
return NewNode;
}
node * createList(int n)
{
int i;
node *head,*tail,*NN;
for(i=0; i<n; i++)
{
NN = createNode();
if(i==0) head = NN;
else
tail->next = NN;
tail = NN;
}
return head;
}
void traverseList(node *head)
{
printf("\n");
while(head)
{
printf("%dx^%d + ",head->coeff,head->pow);
head=head->next;
}
}
void swapVals(node *n1, node *n2)
{
int tc=n1->coeff, tp=n1->pow;
n1->coeff = n2->coeff;
n1->pow = n2->pow;
n2->coeff = tc;
n2->pow = tp;
}
node * sort(node *head)
{
int s=1;
node *curr;
while(s)
{
s=0;
curr = head;
while(curr->next)
{

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

 if(curr->pow < curr->next->pow)
{
swapVals(curr,curr->next);
s=1;
}
curr = curr->next;
}
}
return head;
}
node * addPoly(node *n1, node *n2)
{
node *head = NULL, *last, *NN;

while(n1 && n2)

{
NN=(node *)malloc(sizeof(NN));
NN->next = NULL;
if(n1->pow > n2->pow)
{
NN->coeff = n1->coeff;
NN->pow = n1->pow;
n1 = n1->next;
}
else if(n1->pow < n2->pow)
{
NN->coeff = n2->coeff;
NN->pow = n2->pow;
n2 = n2->next;
}
else
{
NN->coeff = n1->coeff+n2->coeff;
NN->pow = n1->pow;
n1 = n1->next;
n2 = n2->next;
}
if(head == NULL)
head = NN;
else
last->next = NN;
last = NN;
}
if(n1)
last->next = n1;
else
last->next = n2;
return head;
}
node * removeDuplicates(node *head)

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

{
node *curr=head,*n;
int v;
while(curr->next)
{
v=0;
while(curr->pow == curr->next->pow)
{
n = curr->next;
v+= n->coeff;
curr->next = n->next;
free(n);
if(!curr->next)
{
curr->coeff += v;
return head;
}
}
curr->coeff += v;
curr = curr->next;
}
return head;
}
node * multiplyPoly(node *p1, node *p2)
{
node *t2,*head=NULL,*last, *NN;
while(p1)
{
t2 = p2;
while(t2)
{
NN=(node *)malloc(sizeof(NN));
NN->next = NULL;
NN->coeff = (p1->coeff)*(t2->coeff);
NN->pow = (p1->pow)+(t2->pow);
if(head)
last->next = NN;
else
head = NN;
last = NN;
t2 = t2->next;
}
p1 = p1->next;
}
head = sort(head);
head=removeDuplicates(head);
return head;
}

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

int main()
{
node *head1=NULL, *head2=NULL, *Polysum, *Polyprod;
head1 = createList(1);
head1 = sort(head1);
head2 = createList(3);
head2 = sort(head2);
Polysum = addPoly(head1,head2);
Polyprod = multiplyPoly(head1,head2);
traverseList(head1);
traverseList(head2);
traverseList(Polysum);
traverseList(Polyprod);
return 0;
}

CIRCULAR LINKED LISTS

A circular linked list is a variation of the linked list where the last node in the list points back to the
first node, forming a circular structure. Unlike singly or doubly linked lists, which end at NULL, a
circular linked list does not have a NULL pointer in the last node.

3 2 3 1

Key Characteristics:

1. Last Node Points to First Node: In a circular linked list, the next pointer of the last node
does not point to NULL but to the first node, forming a closed loop.
2. Traversal: Traversal in a circular linked list can continue indefinitely unless a specific
condition, such as returning to the starting node, is checked. This ensures that we do not enter
an infinite loop.
3. No Null Termination: Unlike single/double linked lists, circular linked lists do not end with
NULL. The nodes form a continuous chain, making them useful for scenarios that require
circular traversal (e.g., round-robin scheduling).

Types of Circular Linked Lists:

1. Singly Circular Linked List: Each node has a single pointer (next) that points to the next
node. The last node’s next pointer points back to the first node.
2. Doubly Circular Linked List: Each node has two pointers: one (next) that points to the next
node and another (prev) that points to the previous node. The last node’s next points to the
first node, and the first node’s prev points to the last node.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Operations on Circular Linked Lists:

1. Insertion at the Beginning: When a node is inserted at the beginning, the new node’s next
pointer is set to the current head, and the last node’s next pointer is updated to point to this
new node.

Algorithm for Inserting a Node at the Front of a Circular Linked List

Step 1: Create a new node.

• Allocate memory for the new node.
• Assign the given value v to the data field of the new node.
Step 2: Check if the list is empty.
• If the list is empty (last == NULL), the new node becomes the only node in the
circular list. Return the newly created node.
Step 3: Insert the new node at the front.
• Set the next pointer of the new node to point to the first node in the list (i.e., last-
>next).
• Update the next pointer of the last node to point to the new node.
Step 4: Return the last node to keep the circular structure intact.

2. Insertion at the End: The new node is inserted after the last node, and its next pointer is set
to the head. The previous last node’s next pointer is updated to point to the new node.

Algorithm for Inserting a Node at the Rear of a Circular Linked List

Step 1: Create a new node.

• Allocate memory for the new node.
• Assign the given value v to the data field of the new node.
Step 2: Check if the list is empty.
• If the list is empty (last == NULL), the new node becomes the only node in the
circular list. Return the newly created node.
Step 3: Insert the new node at the rear.
• Set the next pointer of the new node to point to the first node in the list (i.e., last-
>next).
• Update the next pointer of the last node to point to the new node.
Step 4: Update the last pointer to the newly inserted node to maintain the circular structure.
Step 5: Return the updated last pointer.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

 3. Traversal: Begin from any node and move through the list by following the next pointers
until the starting node is encountered again.

Algorithm for Printing a Circular Linked List

Step 1: Check if the list is empty.

• If the last pointer is NULL, print "List is empty" and exit the function.
Step 2: Initialize a temporary pointer.
• Set a temporary pointer temp to the node next to last (i.e., temp = last-
>next). This marks the starting node of the list.
Step 3: Traverse the list and Print the node’s data.
• Enter a loop to print the data of each node. Continue moving temp to the
next node until it loops back to the starting node (i.e., temp == last->next).

4. Deletion: Deleting a node requires updating the previous node’s next pointer to skip the node
to be deleted. Special care is needed when deleting the last node to maintain the circular
property.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

 Algorithm for Deleting the First Node in a Circular Linked List

Step 1: Check if the list is empty.

• If last is NULL, return NULL.
Step 2: Point to the first node.
• Set start = last->next.
Step 3: Handle the single node case.
• If start == last, set last = NULL.
Step 4: Handle multiple nodes case (List has more than one node).
• Otherwise, update last->next to start->next (this delinks start from the list).
Step 5: Free the deleted node.
• Free start and return the updated last pointer.

Algorithm for Deleting the Last Node in a Circular Linked List

Step 1: Check if the list is empty.

• If last is NULL, it means the list is empty. Return NULL.
Step 2: Handle the case with only one node.
• Set start = last->next to get the first node.
• If start is the same as last, it means there’s only one node in the list. Free the memory
of last and return NULL to indicate the list is now empty.
Step 3: Traverse to find the second last node.
• Set temp = last->next to start from the first node.
• Move through the list using a loop: while temp->next is not equal to last, keep moving
temp to the next node. This will stop at the second last node.
Step 4: Update the list to remove the last node.
• Set temp->next to start. This effectively removes last from the list and connects temp
(the second last node) back to the first node.
Step 5: Free the memory of the deleted node.
• Finally, free the memory allocated to last to avoid memory leaks. Return temp, which
is now the last node in the updated list.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA

Advantages of Circular Linked Lists:

• Efficient Traversal: Circular lists are useful when you need to continuously cycle through
the list, as in cases like round-robin scheduling.
• No Need for Null Checks: Since there is no NULL termination, handling the end of the list is
simpler when cycling through elements.

CS126 DATA STRUCTURES (R24) DR. APARNA CHAPARALA