Dr.

Anupam Kumar Sharma

28 August 2025 09:39

A circular linked list is a variation of a linked list where the last node points back to the first node,
forming a closed loop or circle. Unlike a regular singly linked list that ends with a pointer, a circular
linked list has no definitive "end"—you can keep traversing it indefinitely.

Key Characteristics
• Circular Structure: The pointer of the last node points to the head node.
• No Null Terminator: There's no at the end, which makes traversal logic slightly different.
• Can Be Singly or Doubly Linked:
• Singly Circular: Each node has one pointer to the next node.
• Doubly Circular: Each node has two pointers— and —and both ends connect to form a loop.

Advantages
• Efficient for applications that require continuous cycling through elements (e.g., round-robin
scheduling).
• Insertion and deletion can be optimized, especially when using a tail pointer.
• Useful in buffer management, music playlists, and real-time systems.

Example
Imagine a music player playlist that loops songs endlessly. A circular linked list allows you to move
from the last song back to the first without resetting the pointer manually.

C++ Implementation
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};

class CircularLinkedList {
private:
Node* tail;

public:
CircularLinkedList() : tail(nullptr) {}

void insert(int val) {

Node* newNode = new Node(val);
if (!tail) {
tail = newNode;
tail->next = tail;
} else {
newNode->next = tail->next;
tail->next = newNode;
tail = newNode;
}
Week 3 Lec 7 8 9 Page 1
 }
}

void deleteNode(int val) {

if (!tail) return;

Node* curr = tail->next;

Node* prev = tail;

do {
if (curr->data == val) {
if (curr == tail && curr->next == tail) {
delete curr;
tail = nullptr;
} else {
prev->next = curr->next;
if (curr == tail) tail = prev;
delete curr;
}
return;
}
prev = curr;
curr = curr->next;
} while (curr != tail->next);
}

void display() {
if (!tail) {
cout << "List is empty\n";
return;
}
Node* temp = tail->next;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != tail->next);
cout << endl;
}
};

int main() {
CircularLinkedList cll;
[Link](10);
[Link](20);
[Link](30);
[Link](); // Output: 10 20 30
[Link](20);
[Link](); // Output: 10 30
return 0;
}

Java Implementation
Week 3 Lec 7 8 9 Page 2
Java Implementation
class Node {
int data;
Node next;

Node(int val) {
data = val;
next = null;
}
}

class CircularLinkedList {
private Node tail;

public CircularLinkedList() {
tail = null;
}
public void insert(int val) {
Node newNode = new Node(val);
if (tail == null) {
tail = newNode;
[Link] = tail;
} else {
[Link] = [Link];
[Link] = newNode;
tail = newNode;
}
}

public void deleteNode(int val) {

if (tail == null) return;

Node curr = [Link];

Node prev = tail;

do {
if ([Link] == val) {
if (curr == tail && [Link] == tail) {
tail = null;
} else {
[Link] = [Link];
if (curr == tail) tail = prev;
}
return;
}
prev = curr;
curr = [Link];
} while (curr != [Link]);
}

public void display() {

if (tail == null) {
Week 3 Lec 7 8 9 Page 3
 if (tail == null) {
[Link]("List is empty");
return;
}
Node temp = [Link];
do {
[Link]([Link] + " ");
temp = [Link];
} while (temp != [Link]);
[Link]();
}

public static void main(String[] args) {

CircularLinkedList cll = new CircularLinkedList();
[Link](10);
[Link](20);
[Link](30);
[Link](); // Output: 10 20 30
[Link](20);
[Link](); // Output: 10 30
}
}

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Think of it like a
stack of plates—only the top plate can be removed or added at any time.
Stack Basics
Key Operations:
• Push: Add an element to the top.
• Pop: Remove the top element.
• Peek/Top: View the top element without removing it.
• isEmpty: Check if the stack is empty.
Use Cases:
• Function call management (call stack)
• Undo operations in editors
• Expression evaluation (postfix, prefix)
• Backtracking algorithms (e.g., maze solving)

C++ implementation

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};

class Stack {
private:
Node* top;
Week 3 Lec 7 8 9 Page 4
class Stack {
private:
Node* top;

public:
Stack() : top(nullptr) {}

void push(int val) {

Node* newNode = new Node(val);
newNode->next = top;
top = newNode;
}

void pop() {
if (!top) {
cout << "Stack Underflow\n";
return;
}
Node* temp = top;
top = top->next;
delete temp;
}

int peek() {
if (!top) {
cout << "Stack is empty\n";
return -1;
}
return top->data;
}

bool isEmpty() {
return top == nullptr;
}

void display() {
Node* temp = top;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
Stack s;
[Link](10);
[Link](20);
[Link](30);
[Link](); // Output: 30 20 10
[Link]();
Week 3 Lec 7 8 9 Page 5
 [Link](20);
[Link](30);
[Link](); // Output: 30 20 10
[Link]();
[Link](); // Output: 20 10
cout << "Top: " << [Link]() << endl; // Output: 20
return 0;
}

Java Implementation
class Node {
int data;
Node next;

Node(int val) {
data = val;
next = null;
}
}

class Stack {
private Node top;

public Stack() {
top = null;
}

public void push(int val) {

Node newNode = new Node(val);
[Link] = top;
top = newNode;
}

public void pop() {

if (top == null) {
[Link]("Stack Underflow");
return;
}
top = [Link];
}

public int peek() {

if (top == null) {
[Link]("Stack is empty");
return -1;
}
return [Link];
}

public boolean isEmpty() {

return top == null;
}

Week 3 Lec 7 8 9 Page 6

 }

public void display() {

Node temp = top;
while (temp != null) {
[Link]([Link] + " ");
temp = [Link];
}
[Link]();
}

public static void main(String[] args) {

Stack s = new Stack();
[Link](10);
[Link](20);
[Link](30);
[Link](); // Output: 30 20 10
[Link]();
[Link](); // Output: 20 10
[Link]("Top: " + [Link]()); // Output: 20
}
}

Labs

Implementation of doubly linked list. Operations on Linked List. Insertion, Deletion, Traversal.

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
private:
Node* head;

public:
DoublyLinkedList() : head(nullptr) {}

void insertAtEnd(int val) {

Node* newNode = new Node(val);
if (!head) {
head = newNode;
return;
Week 3 Lec 7 8 9 Page 7
 return;
}
Node* temp = head;
while (temp->next)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}

void deleteNode(int val) {

if (!head) return;
Node* temp = head;

while (temp && temp->data != val)

temp = temp->next;

if (!temp) return;

if (temp->prev)
temp->prev->next = temp->next;
else
head = temp->next;

if (temp->next)
temp->next->prev = temp->prev;

delete temp;
}

void traverseForward() {
Node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

void traverseBackward() {
if (!head) return;
Node* temp = head;
while (temp->next)
temp = temp->next;

while (temp) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << endl;
}
};

Week 3 Lec 7 8 9 Page 8

int main() {
DoublyLinkedList dll;
[Link](10);
[Link](20);
[Link](30);
[Link](); // Output: 10 20 30
[Link](); // Output: 30 20 10
[Link](20);
[Link](); // Output: 10 30
return 0;
}
Java Program

class Node {
int data;
Node prev, next;

Node(int val) {
data = val;
prev = next = null;
}
}

class DoublyLinkedList {
private Node head;

public DoublyLinkedList() {
head = null;
}

public void insertAtEnd(int val) {

Node newNode = new Node(val);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while ([Link] != null)
temp = [Link];
[Link] = newNode;
[Link] = temp;
}

public void deleteNode(int val) {

if (head == null) return;
Node temp = head;

while (temp != null && [Link] != val)

temp = [Link];

Week 3 Lec 7 8 9 Page 9

 if (temp == null) return;

if ([Link] != null)
[Link] = [Link];
else
head = [Link];

if ([Link] != null)
[Link] = [Link];
}

public void traverseForward() {

Node temp = head;
while (temp != null) {
[Link]([Link] + " ");
temp = [Link];
}
[Link]();
}

public void traverseBackward() {

if (head == null) return;
Node temp = head;
while ([Link] != null)
temp = [Link];

while (temp != null) {

[Link]([Link] + " ");
temp = [Link];
}
[Link]();
}

public static void main(String[] args) {

DoublyLinkedList dll = new DoublyLinkedList();
[Link](10);
[Link](20);
[Link](30);
[Link](); // Output: 10 20 30
[Link](); // Output: 30 20 10
[Link](20);
[Link](); // Output: 10 30
}
}

Implementation of circular linked list. Operations on Linked List. Insertion, Deletion, Traversal.
#include <iostream>
using namespace std;

class Node {
public:
Week 3 Lec 7 8 9 Page 10
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};

class CircularLinkedList {
private:
Node* tail;

public:
CircularLinkedList() : tail(nullptr) {}

// Insert at end
void insert(int val) {
Node* newNode = new Node(val);
if (!tail) {
tail = newNode;
tail->next = tail;
} else {
newNode->next = tail->next;
tail->next = newNode;
tail = newNode;
}
}

// Delete node by value

void deleteNode(int val) {
if (!tail) return;

Node* curr = tail->next;

Node* prev = tail;

do {
if (curr->data == val) {
if (curr == tail && curr->next == tail) {
delete curr;
tail = nullptr;
} else {
prev->next = curr->next;
if (curr == tail) tail = prev;
delete curr;
}
return;
}
prev = curr;
curr = curr->next;
} while (curr != tail->next);
}

// Traverse and display

void traverse() {
Week 3 Lec 7 8 9 Page 11
 void traverse() {
if (!tail) {
cout << "List is empty\n";
return;
}
Node* temp = tail->next;
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != tail->next);
cout << endl;
}
};

int main() {
CircularLinkedList cll;
[Link](10);
[Link](20);
[Link](30);
[Link](); // Output: 10 20 30
[Link](20);
[Link](); // Output: 10 30
return 0;
}
Java Implementation
class Node {
int data;
Node next;

Node(int val) {
data = val;
next = null;
}
}

class CircularLinkedList {
private Node tail;

public CircularLinkedList() {
tail = null;
}

// Insert at end
public void insert(int val) {
Node newNode = new Node(val);
if (tail == null) {
tail = newNode;
[Link] = tail;
} else {
[Link] = [Link];
[Link] = newNode;
tail = newNode;
Week 3 Lec 7 8 9 Page 12
 tail = newNode;
}
}

// Delete node by value

public void deleteNode(int val) {
if (tail == null) return;
Node curr = [Link];
Node prev = tail;
do {
if ([Link] == val) {
if (curr == tail && [Link] == tail) {
tail = null;
} else {
[Link] = [Link];
if (curr == tail) tail = prev;
}
return;
}
prev = curr;
curr = [Link];
} while (curr != [Link]);
}

// Traverse and display

public void traverse() {
if (tail == null) {
[Link]("List is empty");
return;
}
Node temp = [Link];
do {
[Link]([Link] + " ");
temp = [Link];
} while (temp != [Link]);
[Link]();
}

public static void main(String[] args) {

CircularLinkedList cll = new CircularLinkedList();
[Link](10);
[Link](20);
[Link](30);
[Link](); // Output: 10 20 30
[Link](20);
[Link](); // Output: 10 30
}
}
Merge Two Sorted Linked Lists: Write a program/function to merge two sorted linked lists into one
sorted linked list.
C++ implementation
#include <iostream>
using namespace std;

class Node {
public:
Week 3 Lec 7 8 9 Page 13
public:
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
Node* head;

LinkedList() : head(nullptr) {}

void insert(int val) {

Node* newNode = new Node(val);
if (!head || val < head->data) {
newNode->next = head;
head = newNode;
return;
}
Node* temp = head;
while (temp->next && temp->next->data < val)
temp = temp->next;
newNode->next = temp->next;
temp->next = newNode;
}

static Node* mergeSortedLists(Node* l1, Node* l2) {

if (!l1) return l2;
if (!l2) return l1;

Node* dummy = new Node(-1);

Node* tail = dummy;

while (l1 && l2) {

if (l1->data < l2->data) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy->next;
}

void display(Node* node) {

while (node) {
cout << node->data << " ";
node = node->next;
}
Week 3 Lec 7 8 9 Page 14
 }
cout << endl;
}
};

int main() {
LinkedList list1, list2;
[Link](1);
[Link](3);
[Link](5);

[Link](2);
[Link](4);
[Link](6);

Node* mergedHead = LinkedList::mergeSortedLists([Link], [Link]);

LinkedList result;
[Link](mergedHead); // Output: 1 2 3 4 5 6
return 0;
}
Java Implementation
class Node {
int data;
Node next;

Node(int val) {
data = val;
next = null;
}
}

class LinkedList {
Node head;

public void insert(int val) {

Node newNode = new Node(val);
if (head == null || val < [Link]) {
[Link] = head;
head = newNode;
return;
}
Node temp = head;
while ([Link] != null && [Link] < val)
temp = [Link];
[Link] = [Link];
[Link] = newNode;
}

public static Node mergeSortedLists(Node l1, Node l2) {

if (l1 == null) return l2;
if (l2 == null) return l1;
Node dummy = new Node(-1);
Week 3 Lec 7 8 9 Page 15
 Node dummy = new Node(-1);
Node tail = dummy;
while (l1 != null && l2 != null) {
if ([Link] < [Link]) {
[Link] = l1;
l1 = [Link];
} else {
[Link] = l2;
l2 = [Link];
}
tail = [Link];
}
[Link] = (l1 != null) ? l1 : l2;
return [Link];
}

public void display(Node node) {

while (node != null) {
[Link]([Link] + " ");
node = [Link];
}
[Link]();
}

public static void main(String[] args) {

LinkedList list1 = new LinkedList();
LinkedList list2 = new LinkedList();

[Link](1);
[Link](3);
[Link](5);

[Link](2);
[Link](4);
[Link](6);

Node mergedHead = [Link]([Link], [Link]);

LinkedList result = new LinkedList();
[Link](mergedHead); // Output: 1 2 3 4 5 6
}
}
Remove Nth Node from End of List:Write a function to remove the Nth node from the start/end of
a linked list.

C++ program
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Week 3 Lec 7 8 9 Page 16
 Node* next;
Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
private:
Node* head;

public:
LinkedList() : head(nullptr) {}

void insert(int val) {

Node* newNode = new Node(val);
if (!head) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next)
temp = temp->next;
temp->next = newNode;
}

void removeNthFromStart(int n) {
if (!head || n <= 0) return;
if (n == 1) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* temp = head;
for (int i = 1; temp && i < n - 1; ++i)
temp = temp->next;
if (temp && temp->next) {
Node* toDelete = temp->next;
temp->next = temp->next->next;
delete toDelete;
}
}

void removeNthFromEnd(int n) {
Node* dummy = new Node(0);
dummy->next = head;
Node* fast = dummy;
Node* slow = dummy;

for (int i = 0; i < n; ++i) {

if (!fast->next) return;
fast = fast->next;
}

Week 3 Lec 7 8 9 Page 17

 while (fast->next) {
fast = fast->next;
slow = slow->next;
}

Node* toDelete = slow->next;

slow->next = slow->next->next;
if (toDelete == head) head = head->next;
delete toDelete;
delete dummy;
}

void display() {
Node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};

int main() {
LinkedList list;
for (int i = 1; i <= 5; ++i)
[Link](i); // List: 1 2 3 4 5

[Link](2); // Remove 2nd node from start → 1 3 4 5

[Link]();

[Link](2); // Remove 2nd node from end → 1 3 5

[Link]();

return 0;
}
Java Program

class Node {
int data;
Node next;

Node(int val) {
data = val;
next = null;
}
}

class LinkedList {
private Node head;

public void insert(int val) {

Week 3 Lec 7 8 9 Page 18
public void insert(int val) {
Node newNode = new Node(val);
if (head == null) {
head = newNode;
return;
}
Node temp = head;
while ([Link] != null)
temp = [Link];
[Link] = newNode;
}

public void removeNthFromStart(int n) {

if (head == null || n <= 0) return;
if (n == 1) {
head = [Link];
return;
}
Node temp = head;
for (int i = 1; temp != null && i < n - 1; ++i)
temp = [Link];
if (temp != null && [Link] != null)
[Link] = [Link];
}

public void removeNthFromEnd(int n) {

Node dummy = new Node(0);
[Link] = head;
Node fast = dummy, slow = dummy;

for (int i = 0; i < n; ++i) {

if ([Link] == null) return;
fast = [Link];
}

while ([Link] != null) {

fast = [Link];
slow = [Link];
}

if ([Link] == head)
head = [Link];
else
[Link] = [Link];
}

public void display() {

Node temp = head;
while (temp != null) {
[Link]([Link] + " ");
temp = [Link];
}
Week 3 Lec 7 8 9 Page 19
 }
[Link]();
}

public static void main(String[] args) {

LinkedList list = new LinkedList();
for (int i = 1; i <= 5; ++i)
[Link](i); // List: 1 2 3 4 5

[Link](2); // Remove 2nd node from start → 1 3 4 5

[Link]();

[Link](2); // Remove 2nd node from end → 1 3 5

[Link]();
}
}

Given an array of integers (which may include negative numbers), find the contiguous subarray
with the maximum sum.

public class KadaneAlgorithm {

public static int maxSubArraySum(int[] nums) {
int currentMax = nums[0];
int maxSoFar = nums[0];
for (int i = 1; i < [Link]; i++) {
// Decide whether to start fresh or extend previous subarray
currentMax = [Link](nums[i], currentMax + nums[i]);
maxSoFar = [Link](maxSoFar, currentMax);
}
return maxSoFar;
}
public static void main(String[] args) {
int[] array = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
int maxSum = maxSubArraySum(array);
[Link]("Maximum Subarray Sum is: " + maxSum);
}
}

Week 3 Lec 7 8 9 Page 20