C++ Data Structures: Circular List, AVL Rotations, DFS & Palindrome

Posted on Jan 2, 2026 in Computer Engineering

Create and Display a Circular Singly Linked List

In a circular singly linked list, the last node’s next pointer points back to the head instead of NULL.

C++

// struct definition
struct Node {
    int data;
    Node* next;
};

// Function to insert a node (Creating the list)
void insertEnd(Node*& head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    
    if (head == NULL) {
        head = newNode;
        newNode->next = head; // Points to itself
    } else {
        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = head; // Point back to head
    }
}

// Function to display the list
void displayList(Node* head) {
    if (head == NULL) {
        cout << "List is empty." << endl;
        return;
    }
    
    Node* temp = head;
    
    // Do-while is preferred for circular lists to ensure body runs once
    do {
        cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);
    
    cout << "(Head)" << endl;
}

AVL Rotations: Types and Example

AVL trees are self-balancing binary search trees. When the balance factor of a node (height of left subtree − height of right subtree) becomes > 1 or < −1, rotations are performed to restore balance.

There are four types of rotations:

1. LL Rotation (Left-Left Case)

• When it happens: A node is inserted into the left subtree of the left child of a node that becomes unbalanced.
• Solution: Perform a right rotation on the unbalanced node.
• Example: Inserting 10 into a tree with 30 → 20 (30 becomes unbalanced).

2. RR Rotation (Right-Right Case)

• When it happens: A node is inserted into the right subtree of the right child.
• Solution: Perform a left rotation.
• Example: Inserting 30 into a tree with 10 → 20.

3. LR Rotation (Left-Right Case)

• When it happens: A node is inserted into the right subtree of the left child.
• Solution: This is a double rotation:

1. Perform a left rotation on the left child.
2. Perform a right rotation on the main unbalanced node.

4. RL Rotation (Right-Left Case)

• When it happens: A node is inserted into the left subtree of the right child.
• Solution: This is a double rotation:

1. Perform a right rotation on the right child.
2. Perform a left rotation on the main unbalanced node.

Depth-First Search (DFS) Graph Traversal Function

Depth-First Search (DFS) starts at a node and explores as far as possible along each branch before backtracking. This is typically implemented using recursion or a stack.

C++

// Assumes an adjacency matrix 'adj[V][V]' and a 'visited[V]' array
// v = current vertex to visit
// V = total number of vertices

void DFS(int v, int visited[], int V, int adj[10][10]) {
    // 1. Mark the current node as visited and print it
    visited[v] = 1;
    cout << v << " ";

    // 2. Traverse all adjacent vertices
    for (int i = 0; i < V; i++) {
        // If there is an edge (adj[v][i] == 1) and 'i' is not visited
        if (adj[v][i] == 1 && visited[i] == 0) {
            DFS(i, visited, V, adj); // Recursive call
        }
    }
}

Insert Node at Given Position in Linked List

This requires traversing the list to find the node just before the desired position (p-1), creating a new node, and adjusting the pointers.

C++

struct Node {
    int data;
    Node* next;
};

void insertAtPosition(Node*& head, int value, int position) {
    Node* newNode = new Node();
    newNode->data = value;

    // Case 1: Insert at the beginning (Position 1)
    if (position == 1) {
        newNode->next = head;
        head = newNode;
        return;
    }

    Node* temp = head;
    // Traverse to position - 1
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }

    // Case 2: If position is invalid (out of bounds)
    if (temp == NULL) {
        cout << "Position out of range." << endl;
        return;
    }

    // Case 3: Insert in middle or end
    newNode->next = temp->next;
    temp->next = newNode;
}

Check If a String Is Palindrome Using a Stack

A stack follows LIFO (last in, first out). To check a palindrome, push all characters onto the stack, then pop them off. Because of LIFO, popping them reverses the string. If the popped characters match the original string, it is a palindrome.

C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isPalindrome(string str) {
    stack<char> s;
    
    // 1. Push all characters of the string onto the stack
    for (int i = 0; i < str.length(); i++) {
        s.push(str[i]);
    }
    
    // 2. Pop characters and compare with the original string
    for (int i = 0; i < str.length(); i++) {
        // Top element is the last character of the original string
        if (s.top() != str[i]) {
            return false; // Mismatch found
        }
        s.pop();
    }
    
    return true; // All matched
}