Data Structures and Algorithms C Implementation

Posted on Jan 29, 2026 in Computer Engineering

Counting Nodes in a Singly Linked List

int count(struct node *p) {
    int c = 0;
    while(p) {
        c++;
        p = p->next;
    }
    return c;
}

Postfix Expression Evaluation

Given values: A=2, B=10, C=4, D=1

i) AB–CD*

  • Substitute: 2 10 – 4 1 *
  • Step 1: 2 – 10 = –8
  • Step 2: 4 * 1 = 4
  • Final Result: –4

ii) ABC–*

  • Substitute: 2 10 4 – *
  • Step 1: 10 – 4 = 6
  • Step 2: 2 * 6 = 12
  • Final Result: 12

Graph Theory Definitions

  • Bridge: An edge whose removal increases the number of connected components.
  • Cyclic Graph: A graph containing at least one cycle.
  • Pendant Vertex: A vertex with a degree of 1.

Circular Linked List Features

  • The last node points back to the head node.
  • There is no NULL at the end; operations must account for circularity.
  • Useful in round-robin scheduling, multiplayer games, and CPU scheduling.
  • The list can be traversed starting from any node.

Required Functions

  • Creation: Allocate nodes dynamically and maintain the circular property.
  • Display: Use a do-while loop to print nodes until the head is reached again.
struct node {
    int data;
    struct node *next;
};

void create(int arr[], int n) {
    struct node *head, *temp, *last;
    head = malloc(sizeof(struct node));
    head->data = arr[0];
    head->next = head;
    last = head;
    for(int i = 1; i < n; i++) {
        temp = malloc(sizeof(struct node));
        temp->data = arr[i];
        temp->next = head;
        last->next = temp;
        last = temp;
    }
}

void display(struct node *head) {
    struct node *p = head;
    if (head == NULL) return;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while(p != head);
}

AVL Tree Rotations and Balancing

An AVL Tree is a self-balancing Binary Search Tree where the balance factor (BF) of each node must be: BF = height(left) – height(right) = -1, 0, or +1.

1. LL Rotation (Left-Left Rotation)

Occurs when insertion happens in the left child of the left subtree. Fix by performing a single right rotation.

     A                     B
    /                     / \
   B         →           C   A
  /
 C

2. RR Rotation (Right-Right Rotation)

Occurs when insertion happens in the right child of the right subtree. Fix by performing a single left rotation.

 A                         B
  \                       / \
   B         →           A   C
    \
     C

3. LR Rotation (Left-Right Rotation)

Occurs when insertion happens in the right child of the left subtree.

  1. First, left rotate the left subtree.
  2. Then, right rotate the main node.
    A                     A                C
   /                     /               / \
  B         →           C         →     B   A
   \                  
    C                 B

Depth First Search (DFS) Traversal

Depth First Search (DFS) is an algorithm that explores as far as possible along each branch before backtracking. It utilizes recursion or a stack.

  • Follows deep exploration first.
  • Uses a visited[] array to track nodes.
  • Works for graphs represented via adjacency matrices or lists.
  • Useful for cycle detection and topological sorting.

Steps of DFS

  1. Start from a source vertex.
  2. Mark the vertex as visited.
  3. Visit all adjacent unvisited nodes recursively.
  4. Backtrack when no adjacent nodes remain.
void DFS(int v) {
    visited[v] = 1;
    printf("%d ", v);
    for(int i = 0; i < n; i++)
        if(G[v][i] == 1 && !visited[i])
            DFS(i);
}

Inserting a Node at a Specific Position

In a singly linked list, insertion at a specific position requires:

  1. Traversing the list up to (position – 1).
  2. Creating a new node.
  3. Adjusting pointers to maintain the structure.

Note: If the position is 1, the new node becomes the head. All positions must be validated.

void insertPos(int pos, int data) {
    struct node *temp = malloc(sizeof(struct node));
    temp->data = data;

    if(pos == 1) {
        temp->next = head;
        head = temp;
        return;
    }
    struct node *p = head;
    for(int i = 1; i < pos - 1 && p != NULL; i++) p = p->next;

    if(p != NULL) {
        temp->next = p->next;
        p->next = temp;
    }
}

Checking Palindromes Using a Stack

A palindrome string reads the same forward and backward. Using a stack, we can compare characters because the stack follows the LIFO (Last-In, First-Out) property.

Steps

  1. Push each character of the string onto the stack.
  2. Pop characters one by one.
  3. Compare popped characters with the original string.
  4. If all characters match, the string is a palindrome.
int isPalindrome(char s[]) {
    char stack[50];
    int top = -1;

    for(int i = 0; s[i] != '\0'; i++)
        stack[++top] = s[i];

    for(int i = 0; s[i] != '\0'; i++)
        if(s[i] != stack[top--])
            return 0;

    return 1;
}