Data Structures - Comprehensive Detailed Notes

UNIT-I: Introduction to Data Structures

Overview of Data Structures

Definition
A data structure is a way of organizing, storing, and managing data in a computer so that it can
be accessed and modified efficiently. It defines the relationship between data elements and the
operations that can be performed on them.

Classification of Data Structures

1. Linear Data Structures
Elements arranged in sequential order
Each element has unique predecessor and successor (except first and last)
Examples: Arrays, Linked Lists, Stacks, Queues
2. Non-Linear Data Structures
Elements not arranged in sequential order
Each element can have multiple predecessors and successors
Examples: Trees, Graphs, Hash Tables
3. Static vs Dynamic Data Structures
Static: Fixed size determined at compile time (Arrays)
Dynamic: Size can be changed during runtime (Linked Lists, Trees)
4. Homogeneous vs Heterogeneous
Homogeneous: All elements of same data type (Arrays)
Heterogeneous: Elements of different data types (Structures)
Pointers and Dynamic Memory Allocation

Pointer Fundamentals
Definition: A pointer is a variable that stores the memory address of another variable.

int x = 10;
int *ptr = &x; // ptr stores address of x
printf("Value of x: %d\n", *ptr); // Dereferencing
printf("Address of x: %p\n", ptr);

Pointer Operations
1. Declaration: data_type *pointer_name;

2. Initialization: pointer_name = &variable;

3. Dereferencing: *pointer_name
4. Pointer Arithmetic: ptr++, ptr--, ptr+n, ptr-n

Dynamic Memory Allocation

Memory Segments:
Stack: Local variables, function parameters (automatic allocation)
Heap: Dynamic allocation using malloc, calloc, realloc
Data Segment: Global and static variables
Code Segment: Program instructions
Dynamic Allocation Functions:

// malloc() - allocates uninitialized memory

int *ptr = (int*)malloc(sizeof(int) * 10);

// calloc() - allocates zero-initialized memory

int *ptr2 = (int*)calloc(10, sizeof(int));

// realloc() - resizes allocated memory

ptr = (int*)realloc(ptr, sizeof(int) * 20);

// free() - deallocates memory

free(ptr);
ptr = NULL; // Avoid dangling pointers

Best Practices:
Always check if allocation succeeded (if (ptr == NULL))

Free allocated memory to prevent memory leaks

Set pointers to NULL after freeing
 Don't access memory after freeing

Algorithm Specification

Algorithm Characteristics
1. Input: Zero or more inputs
2. Output: At least one output
3. Definiteness: Each step clearly defined
4. Finiteness: Terminates after finite steps
5. Effectiveness: Steps are basic and executable

Algorithm Representation Methods

1. Natural Language
Written in plain English
Easy to understand but ambiguous
2. Flowcharts
Graphical representation using symbols
Visual but can become complex for large algorithms
3. Pseudocode
Structured English-like statements
Balance between clarity and precision
Example Pseudocode:

Algorithm FindMax(A, n)
Input: Array A of n elements
Output: Maximum element in A

1. max = A[0]
2. for i = 1 to n-1 do
3. if A[i] > max then
4. max = A[i]
5. return max

Data Abstraction
Abstract Data Type (ADT)
An ADT is a mathematical model that defines:
A set of data values
A set of operations on those values
Behavior of operations (but not implementation)
Benefits:
Encapsulation: Hide implementation details
Modularity: Separate interface from implementation
Reusability: Same interface, different implementations
Example - Stack ADT:

// Interface
typedef struct {
int *data;
int top;
int capacity;
} Stack;

// Operations
Stack* createStack(int capacity);
int isEmpty(Stack *s);
int isFull(Stack *s);
void push(Stack *s, int item);
int pop(Stack *s);
int peek(Stack *s);
void destroyStack(Stack *s);

Performance Analysis

Time Complexity
Measure of algorithm's execution time as function of input size.
Big O Notation:
O(1): Constant time
O(log n): Logarithmic time
O(n): Linear time
O(n log n): Linearithmic time
O(n²): Quadratic time
O(n³): Cubic time
O(2ⁿ): Exponential time
Analysis Types:
1. Best Case: Minimum time (Omega Ω)
2. Average Case: Expected time (Theta Θ)
3. Worst Case: Maximum time (Big O)

Space Complexity
Amount of memory space algorithm uses relative to input size.
Components:
Fixed Space: Independent of input characteristics
Variable Space: Depends on input size and algorithm behavior
Example Analysis:

// Linear Search - O(n) time, O(1) space

int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) { // O(n)
if (arr[i] == key) return i; // O(1)
}
return -1; // O(1)
}

Performance Measurement

Empirical Analysis
Actual measurement of algorithm performance on real systems.
Steps:
1. Implement algorithm
2. Run with various input sizes
3. Measure execution time and memory usage
4. Plot results and analyze growth rate
Factors Affecting Performance:
Hardware specifications (CPU, RAM)
Compiler optimizations
Operating system overhead
Input characteristics
Arrays and Structures

Arrays in C
Definition: Collection of elements of same data type stored in contiguous memory locations.
Declaration and Initialization:

// Declaration
int arr[10]; // Array of 10 integers
int matrix[3][4]; // 2D array

// Initialization
int arr[] = {1, 2, 3, 4, 5}; // Size determined automatically
int arr[5] = {1, 2, 3}; // Remaining elements initialized to 0

Memory Layout:
Elements stored consecutively
Base address + (index × element_size)
Advantages: Random access O(1), cache friendly
Disadvantages: Fixed size, insertion/deletion costly

Dynamically Allocated Arrays

// 1D Dynamic Array
int *arr = (int*)malloc(n * sizeof(int));

// 2D Dynamic Array - Method 1 (Array of pointers)

int **matrix = (int**)malloc(rows * sizeof(int*));
for (int i = 0; i < rows; i++) {
matrix[i] = (int*)malloc(cols * sizeof(int));
}

// 2D Dynamic Array - Method 2 (Single allocation)

int *matrix = (int*)malloc(rows * cols * sizeof(int));
// Access element: matrix[i * cols + j]

Structures
Definition: User-defined data type that groups related data items of different types.

// Structure Definition
struct student {
int id;
char name[50];
float marks;
char grade;
};
 // Declaration and Initialization
struct student s1; // Declaration
struct student s2 = {101, "John", 85.5, 'A'}; // Initialization

// Using typedef
typedef struct {
int x, y;
} Point;

Point p1 = {10, 20};

Structure Operations:

// Accessing members
[Link] = 102;
strcpy([Link], "Alice");

// Pointer to structure
struct student *ptr = &s1;
ptr->id = 103; // Same as (*ptr).id = 103;

// Structure assignment
struct student s3 = s1; // Copies all members

Unions
Definition: Similar to structure but all members share same memory location.

union data {
int i;
float f;
char c;
};

union data d;
d.i = 10; // Only one member can be used at a time
printf("%d\n", d.i); // Valid
d.f = 3.14; // Overwrites the integer value
printf("%f\n", d.f); // Valid, but d.i is now invalid

Key Differences:
Structure: Each member has separate memory
Union: All members share same memory (size = largest member)
Internal Implementation of Structures
Memory Alignment:
Compiler aligns structure members to optimize memory access.

struct example {
char a; // 1 byte
int b; // 4 bytes (may have 3 bytes padding after 'a')
char c; // 1 byte (may have 3 bytes padding after)
};
// Total size might be 12 bytes instead of 6 due to padding

Controlling Alignment:

#pragma pack(1) // Pack without padding

struct packed {
char a;
int b;
char c;
}; // Size will be exactly 6 bytes
#pragma pack() // Restore default packing

Self-Referential Structures
Structures containing pointers to the same structure type.

struct node {
int data;
struct node *next; // Pointer to same structure type
};

// Creating linked structures

struct node *head = (struct node*)malloc(sizeof(struct node));
head->data = 10;
head->next = NULL;

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

second->data = 20;
second->next = NULL;
head->next = second; // Link first node to second

Polynomial Representation
Mathematical Form: P(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀
Array Representation:

#define MAX_DEGREE 100

typedef struct {
 float coeff[MAX_DEGREE + 1]; // Coefficients
int degree; // Highest degree
} Polynomial;

// Example: 3x² + 2x + 1
Polynomial p;
[Link] = 2;
[Link][0] = 1; // Constant term
[Link][1] = 2; // x coefficient
[Link][2] = 3; // x² coefficient

Advantages: Simple indexing, easy arithmetic operations

Disadvantages: Wastes space for sparse polynomials

Polynomial Addition

Polynomial addPolynomials(Polynomial p1, Polynomial p2) {

Polynomial result;
int maxDegree = ([Link] > [Link]) ? [Link] : [Link];

[Link] = maxDegree;

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

float coeff1 = (i <= [Link]) ? [Link][i] : 0;
float coeff2 = (i <= [Link]) ? [Link][i] : 0;
[Link][i] = coeff1 + coeff2;
}

// Remove leading zeros

while ([Link] > 0 && [Link][[Link]] == 0) {
[Link]--;
}

return result;
}

UNIT-II: Searching and Strings

Linear Search
Algorithm: Sequentially check each element until target is found or end is reached.

int linearSearch(int arr[], int n, int target) {

for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Return index if found
}
}
return -1; // Return -1 if not found
}
Time Complexity:
Best Case: O(1) - Element at first position
Average Case: O(n/2) = O(n)
Worst Case: O(n) - Element at last position or not present
Space Complexity: O(1)
Advantages:
Simple implementation
Works on unsorted arrays
No additional memory required
Disadvantages:
Inefficient for large datasets
Not suitable when frequent searches needed

Iterative Binary Search

Prerequisites: Array must be sorted
Algorithm: Repeatedly divide search interval in half, compare target with middle element.

int binarySearch(int arr[], int n, int target) {

int left = 0, right = n - 1;

while (left <= right) {

int mid = left + (right - left) / 2; // Avoid overflow

if (arr[mid] == target) {
return mid;
}
else if (arr[mid] < target) {
left = mid + 1; // Search right half
}
else {
right = mid - 1; // Search left half
}
}

return -1; // Element not found

}

Time Complexity: O(log n)

Space Complexity: O(1)
Recursion
Definition: A function that calls itself directly or indirectly.
Components:
1. Base Case: Termination condition
2. Recursive Case: Function calls itself with modified parameters
Types:
Direct Recursion: Function calls itself
Indirect Recursion: Function A calls B, B calls A
Example - Factorial:

int factorial(int n) {
// Base case
if (n == 0 || n == 1) {
return 1;
}

// Recursive case
return n * factorial(n - 1);
}

Recursive Process Analysis:

factorial(4) = 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1
= 24

Recursive Binary Search

int recursiveBinarySearch(int arr[], int left, int right, int target) {

// Base case - element not found
if (left > right) {
return -1;
}

int mid = left + (right - left) / 2;

// Base case - element found

if (arr[mid] == target) {
return mid;
}

// Recursive cases
if (arr[mid] > target) {
return recursiveBinarySearch(arr, left, mid - 1, target);
 }
else {
return recursiveBinarySearch(arr, mid + 1, right, target);
}
}

Space Complexity: O(log n) due to recursive call stack

String Abstract Data Type

Definition: Sequence of characters terminated by null character ('\0').
String ADT Operations:
Create: Initialize empty string
Length: Return number of characters
Concatenate: Join two strings
Compare: Determine lexicographic order
Substring: Extract part of string
Search: Find pattern in string

String in C
Declaration and Initialization:

// Character array
char str1[20] = "Hello";
char str2[] = "World"; // Size determined automatically
char str3[10] = {'H','i','\0'}; // Explicit initialization

// String pointer
char *str4 = "Constant String"; // Points to string literal

String Input/Output:

char name[50];

// Input
gets(name); // Deprecated - unsafe
fgets(name, sizeof(name), stdin); // Safe alternative
scanf("%s", name); // Stops at whitespace

// Output
puts(name);
printf("%s", name);

String Library Functions:

 #include <string.h>

strlen(str) // Length of string

strcpy(dest, src) // Copy string
strcat(dest, src) // Concatenate strings
strcmp(str1, str2) // Compare strings
strstr(str, substr) // Find substring
strchr(str, ch) // Find character

Pattern Matching

Naive Pattern Matching

Algorithm: Check pattern at every position in text.

int naivePatternSearch(char text[], char pattern[]) {

int n = strlen(text);
int m = strlen(pattern);

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

int j;
for (j = 0; j < m; j++) {
if (text[i + j] != pattern[j]) {
break;
}
}
if (j == m) {
return i; // Pattern found at index i
}
}
return -1; // Pattern not found
}

Time Complexity: O(nm) where n = text length, m = pattern length

Advanced Pattern Matching Algorithms

1. KMP (Knuth-Morris-Pratt): O(n + m)
2. Boyer-Moore: Best case O(n/m)
3. Rabin-Karp: Average case O(n + m)

Stacks and Queues

Stack Abstract Data Type
Definition: Linear data structure following Last-In-First-Out (LIFO) principle.
Operations:
Push: Add element to top
Pop: Remove and return top element
Peek/Top: Return top element without removing
isEmpty: Check if stack is empty
isFull: Check if stack is full
Array Implementation:

#define MAX_SIZE 100

typedef struct {
int data[MAX_SIZE];
int top;
} Stack;

void initStack(Stack *s) {

s->top = -1;
}

int isEmpty(Stack *s) {

return s->top == -1;
}

int isFull(Stack *s) {

return s->top == MAX_SIZE - 1;
}

void push(Stack *s, int item) {

if (isFull(s)) {
printf("Stack Overflow\n");
return;
}
s->data[++s->top] = item;
}

int pop(Stack *s) {

if (isEmpty(s)) {
printf("Stack Underflow\n");
return -1;
}
return s->data[s->top--];
}

int peek(Stack *s) {

if (isEmpty(s)) {
printf("Stack is empty\n");
return -1;
 }
return s->data[s->top];
}

Queue Abstract Data Type

Definition: Linear data structure following First-In-First-Out (FIFO) principle.
Operations:
Enqueue: Add element to rear
Dequeue: Remove and return front element
Front: Return front element without removing
isEmpty: Check if queue is empty
isFull: Check if queue is full
Simple Array Implementation:

#define MAX_SIZE 100

typedef struct {
int data[MAX_SIZE];
int front, rear;
} Queue;

void initQueue(Queue *q) {

q->front = 0;
q->rear = -1;
}

int isEmpty(Queue *q) {

return q->rear < q->front;
}

int isFull(Queue *q) {

return q->rear == MAX_SIZE - 1;
}

void enqueue(Queue *q, int item) {

if (isFull(q)) {
printf("Queue Overflow\n");
return;
}
q->data[++q->rear] = item;
}

int dequeue(Queue *q) {

if (isEmpty(q)) {
printf("Queue Underflow\n");
return -1;
}
 return q->data[q->front++];
}

Circular Queue Using Arrays

Problem with Linear Queue: Space is not reused after dequeue operations.
Solution: Use circular queue where rear wraps around to beginning.

typedef struct {
int data[MAX_SIZE];
int front, rear, count;
} CircularQueue;

void initCircularQueue(CircularQueue *q) {

q->front = 0;
q->rear = -1;
q->count = 0;
}

int isEmpty(CircularQueue *q) {

return q->count == 0;
}

int isFull(CircularQueue *q) {

return q->count == MAX_SIZE;
}

void enqueue(CircularQueue *q, int item) {

if (isFull(q)) {
printf("Queue Overflow\n");
return;
}
q->rear = (q->rear + 1) % MAX_SIZE;
q->data[q->rear] = item;
q->count++;
}

int dequeue(CircularQueue *q) {

if (isEmpty(q)) {
printf("Queue Underflow\n");
return -1;
}
int item = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
q->count--;
return item;
}
Maze Problem
Problem: Find path from start to exit in a maze.
Solution Using Stack (DFS approach):

#define ROWS 10
#define COLS 10

typedef struct {
int x, y;
} Position;

int maze[ROWS][COLS]; // 0 = path, 1 = wall

int visited[ROWS][COLS];

// Directions: right, down, left, up

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

int isValid(int x, int y) {

return (x >= 0 && x < ROWS && y >= 0 && y < COLS &&
maze[x][y] == 0 && !visited[x][y]);
}

int solveMaze(int startX, int startY, int endX, int endY) {

Stack path;
initStack(&path);

Position start = {startX, startY};

push(&path, start);
visited[startX][startY] = 1;

while (!isEmpty(&path)) {
Position current = peek(&path);

if (current.x == endX && current.y == endY) {

return 1; // Path found
}

int moved = 0;
for (int i = 0; i < 4; i++) {
int newX = current.x + dx[i];
int newY = current.y + dy[i];

if (isValid(newX, newY)) {
Position newPos = {newX, newY};
push(&path, newPos);
visited[newX][newY] = 1;
moved = 1;
break;
}
}

if (!moved) {
pop(&path); // Backtrack
 }
}

return 0; // No path found

}

Evaluation of Expressions

Expression Types
1. Infix: Operator between operands (A + B)
2. Prefix (Polish): Operator before operands (+ A B)
3. Postfix (Reverse Polish): Operator after operands (A B +)

Evaluating Postfix Expressions

Algorithm: Use stack to evaluate postfix expression.

int evaluatePostfix(char expr[]) {

Stack s;
initStack(&s);

for (int i = 0; expr[i] != '\0'; i++) {

char ch = expr[i];

if (isdigit(ch)) {
push(&s, ch - '0'); // Convert char to int
}
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
int operand2 = pop(&s);
int operand1 = pop(&s);
int result;

switch (ch) {
case '+': result = operand1 + operand2; break;
case '-': result = operand1 - operand2; break;
case '*': result = operand1 * operand2; break;
case '/': result = operand1 / operand2; break;
}

push(&s, result);
}
}

return pop(&s);
}

Example: "23+4*" = ((2+3)*4) = 20

Stack operations:
Push 2: [2]
 Push 3: [2, 3]
'+': Pop 3,2 → Push 5: [5]
Push 4: [5, 4]
'*': Pop 4,5 → Push 20: [20]
Result: 20

Infix to Postfix Conversion

Algorithm: Use stack to convert infix to postfix using operator precedence.

int precedence(char op) {

switch (op) {
case '+':
case '-': return 1;
case '*':
case '/': return 2;
case '^': return 3;
default: return 0;
}
}

int isOperator(char ch) {

return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^');
}

void infixToPostfix(char infix[], char postfix[]) {

Stack operators;
initStack(&operators);

int i = 0, j = 0;

while (infix[i] != '\0') {

char ch = infix[i];

if (isalnum(ch)) {
postfix[j++] = ch; // Add operand to output
}
else if (ch == '(') {
push(&operators, ch);
}
else if (ch == ')') {
while (!isEmpty(&operators) && peek(&operators) != '(') {
postfix[j++] = pop(&operators);
}
pop(&operators); // Remove '('
}
else if (isOperator(ch)) {
while (!isEmpty(&operators) && peek(&operators) != '(' &&
precedence(peek(&operators)) >= precedence(ch)) {
postfix[j++] = pop(&operators);
}
push(&operators, ch);
}
i++;
}
 // Pop remaining operators
while (!isEmpty(&operators)) {
postfix[j++] = pop(&operators);
}

postfix[j] = '\0';
}

Example: "A+BC" → "ABC+"

Input: A + B * C
Stack operations:
A: Output "A", Stack []
+: Stack [+]
B: Output "AB", Stack [+]
*: Stack [+, *] (higher precedence)
C: Output "ABC", Stack [+, *]
End: Pop *, +: Output "ABC*+"

UNIT-III: Linked Lists

Pointers and Dynamic Storage

Pointer Arithmetic

int arr[] = {10, 20, 30, 40, 50};

int *ptr = arr;

printf("%d\n", *ptr); // 10
printf("%d\n", *(ptr + 1)); // 20
printf("%d\n", ptr[2]); // 30 (equivalent to *(ptr + 2))

ptr++; // Move to next element

printf("%d\n", *ptr); // 20

Dynamic Memory Management

// Allocation
int *ptr = (int*)malloc(sizeof(int));
int *arr = (int*)malloc(10 * sizeof(int));
int *zeros = (int*)calloc(10, sizeof(int)); // Zero-initialized

// Reallocation
arr = (int*)realloc(arr, 20 * sizeof(int));

// Deallocation
free(ptr);
 free(arr);
ptr = NULL; arr = NULL; // Prevent dangling pointers

Singly Linked Lists

Node Structure

typedef struct Node {

int data;
struct Node* next;
} Node;

typedef struct {
Node* head;
int size;
} LinkedList;

Basic Operations
1. Creating a Node:

Node* createNode(int data) {

Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

2. Insertion Operations:
Insert at Beginning:

void insertAtBeginning(LinkedList* list, int data) {

Node* newNode = createNode(data);
if (newNode == NULL) return;

newNode->next = list->head;
list->head = newNode;
list->size++;
}

Insert at End:

void insertAtEnd(LinkedList* list, int data) {

Node* newNode = createNode(data);
 if (newNode == NULL) return;

if (list->head == NULL) {
list->head = newNode;
} else {
Node* current = list->head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
}
list->size++;
}

Insert at Position:

void insertAtPosition(LinkedList* list, int data, int position) {

if (position < 0 || position > list->size) {
printf("Invalid position\n");
return;
}

if (position == 0) {
insertAtBeginning(list, data);
return;
}

Node* newNode = createNode(data);

if (newNode == NULL) return;

Node* current = list->head;

for (int i = 0; i < position - 1; i++) {
current = current->next;
}

newNode->next = current->next;
current->next = newNode;
list->size++;
}

3. Deletion Operations:
Delete by Value:

int deleteByValue(LinkedList* list, int value) {

if (list->head == NULL) return 0;

// If head node contains the value

if (list->head->data == value) {
Node* temp = list->head;
list->head = list->head->next;
free(temp);
list->size--;
return 1;
 }

Node* current = list->head;

while (current->next != NULL && current->next->data != value) {
current = current->next;
}

if (current->next == NULL) return 0; // Value not found

Node* temp = current->next;

current->next = temp->next;
free(temp);
list->size--;
return 1;
}

Delete at Position:

int deleteAtPosition(LinkedList* list, int position) {

if (position < 0 || position >= list->size || list->head == NULL) {
return 0;
}

if (position == 0) {
Node* temp = list->head;
list->head = list->head->next;
free(temp);
list->size--;
return 1;
}

Node* current = list->head;

for (int i = 0; i < position - 1; i++) {
current = current->next;
}

Node* temp = current->next;

current->next = temp->next;
free(temp);
list->size--;
return 1;
}

4. Search and Display:

int search(LinkedList* list, int value) {

Node* current = list->head;
int position = 0;

while (current != NULL) {

if (current->data == value) {
return position;
}
current = current->next;
 position++;
}
return -1; // Not found
}

void display(LinkedList* list) {

Node* current = list->head;
printf("List: ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}

void destroyList(LinkedList* list) {

Node* current = list->head;
while (current != NULL) {
Node* next = current->next;
free(current);
current = next;
}
list->head = NULL;
list->size = 0;
}

Dynamically Linked Stacks and Queues

Linked Stack Implementation

typedef struct StackNode {

int data;
struct StackNode* next;
} StackNode;

typedef struct {
StackNode* top;
} LinkedStack;

void initLinkedStack(LinkedStack* stack) {

stack->top = NULL;
}

int isEmptyLinkedStack(LinkedStack* stack) {

return stack->top == NULL;
}

void pushLinked(LinkedStack* stack, int data) {

StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return;
}
 newNode->data = data;
newNode->next = stack->top;
stack->top = newNode;
}

int popLinked(LinkedStack* stack) {

if (isEmptyLinkedStack(stack)) {
printf("Stack underflow\n");
return -1;
}

StackNode* temp = stack->top;

int data = temp->data;
stack->top = stack->top->next;
free(temp);
return data;
}

int peekLinked(LinkedStack* stack) {

if (isEmptyLinkedStack(stack)) {
printf("Stack is empty\n");
return -1;
}
return stack->top->data;
}

Linked Queue Implementation

typedef struct QueueNode {

int data;
struct QueueNode* next;
} QueueNode;

typedef struct {
QueueNode* front;
QueueNode* rear;
} LinkedQueue;

void initLinkedQueue(LinkedQueue* queue) {

queue->front = NULL;
queue->rear = NULL;
}

int isEmptyLinkedQueue(LinkedQueue* queue) {

return queue->front == NULL;
}

void enqueueLinked(LinkedQueue* queue, int data) {

QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return;
}

newNode->data = data;
 newNode->next = NULL;

if (isEmptyLinkedQueue(queue)) {
queue->front = queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}

int dequeueLinked(LinkedQueue* queue) {

if (isEmptyLinkedQueue(queue)) {
printf("Queue underflow\n");
return -1;
}

QueueNode* temp = queue->front;

int data = temp->data;
queue->front = queue->front->next;

if (queue->front == NULL) {
queue->rear = NULL; // Queue became empty
}

free(temp);
return data;
}

Polynomial Representation as Linked Lists

Node Structure for Polynomial

typedef struct TermNode {

float coefficient;
int exponent;
struct TermNode* next;
} TermNode;

typedef struct {
TermNode* head;
} Polynomial;

Representing Polynomials as Singly Linked Lists

void initPolynomial(Polynomial* poly) {

poly->head = NULL;
}

TermNode* createTerm(float coeff, int exp) {

TermNode* newTerm = (TermNode*)malloc(sizeof(TermNode));
if (newTerm == NULL) return NULL;
 newTerm->coefficient = coeff;
newTerm->exponent = exp;
newTerm->next = NULL;
return newTerm;
}

void insertTerm(Polynomial* poly, float coeff, int exp) {

if (coeff == 0) return; // Don't insert zero coefficient terms

TermNode* newTerm = createTerm(coeff, exp);

if (newTerm == NULL) return;

// Insert in descending order of exponents

if (poly->head == NULL || poly->head->exponent < exp) {
newTerm->next = poly->head;
poly->head = newTerm;
return;
}

TermNode* current = poly->head;

TermNode* prev = NULL;

while (current != NULL && current->exponent > exp) {

prev = current;
current = current->next;
}

// If term with same exponent exists, add coefficients

if (current != NULL && current->exponent == exp) {
current->coefficient += coeff;
free(newTerm);

// Remove term if coefficient becomes zero

if (current->coefficient == 0) {
if (prev == NULL) {
poly->head = current->next;
} else {
prev->next = current->next;
}
free(current);
}
return;
}

// Insert new term

newTerm->next = current;
if (prev == NULL) {
poly->head = newTerm;
} else {
prev->next = newTerm;
}
}

void displayPolynomial(Polynomial* poly) {

TermNode* current = poly->head;
if (current == NULL) {
 printf("0\n");
return;
}

int first = 1;
while (current != NULL) {
if (!first && current->coefficient > 0) {
printf(" + ");
} else if (current->coefficient < 0) {
printf(" - ");
}

if (current->exponent == 0) {
printf("%.1f", fabs(current->coefficient));
} else if (current->exponent == 1) {
if (fabs(current->coefficient) == 1) {
printf("x");
} else {
printf("%.1fx", fabs(current->coefficient));
}
} else {
if (fabs(current->coefficient) == 1) {
printf("x^%d", current->exponent);
} else {
printf("%.1fx^%d", fabs(current->coefficient), current->exponent);
}
}

current = current->next;
first = 0;
}
printf("\n");
}

Adding Polynomials

Polynomial addPolynomials(Polynomial* p1, Polynomial* p2) {

Polynomial result;
initPolynomial(&result);

TermNode* term1 = p1->head;

TermNode* term2 = p2->head;

while (term1 != NULL && term2 != NULL) {

if (term1->exponent > term2->exponent) {
insertTerm(&result, term1->coefficient, term1->exponent);
term1 = term1->next;
}
else if (term1->exponent < term2->exponent) {
insertTerm(&result, term2->coefficient, term2->exponent);
term2 = term2->next;
}
else { // Same exponent
float sumCoeff = term1->coefficient + term2->coefficient;
if (sumCoeff != 0) {
 insertTerm(&result, sumCoeff, term1->exponent);
}
term1 = term1->next;
term2 = term2->next;
}
}

// Add remaining terms

while (term1 != NULL) {
insertTerm(&result, term1->coefficient, term1->exponent);
term1 = term1->next;
}

while (term2 != NULL) {

insertTerm(&result, term2->coefficient, term2->exponent);
term2 = term2->next;
}

return result;
}

Erasing Polynomials

void erasePolynomial(Polynomial* poly) {

TermNode* current = poly->head;
while (current != NULL) {
TermNode* next = current->next;
free(current);
current = next;
}
poly->head = NULL;
}

Polynomials as Circularly Linked Lists

typedef struct CircularPoly {

TermNode* tail; // Points to last node, tail->next points to first
} CircularPolynomial;

void initCircularPolynomial(CircularPolynomial* poly) {

poly->tail = NULL;
}

void insertTermCircular(CircularPolynomial* poly, float coeff, int exp) {

if (coeff == 0) return;

TermNode* newTerm = createTerm(coeff, exp);

if (newTerm == NULL) return;

if (poly->tail == NULL) {
newTerm->next = newTerm; // Points to itself
poly->tail = newTerm;
return;
 }

// Find insertion point

TermNode* current = poly->tail->next; // Start from head
TermNode* prev = poly->tail;

do {
if (current->exponent < exp) {
break;
}
if (current->exponent == exp) {
current->coefficient += coeff;
free(newTerm);
if (current->coefficient == 0) {
// Remove term with zero coefficient
if (current == poly->tail && current->next == current) {
// Only one term, list becomes empty
free(current);
poly->tail = NULL;
} else {
prev->next = current->next;
if (current == poly->tail) {
poly->tail = prev;
}
free(current);
}
}
return;
}
prev = current;
current = current->next;
} while (current != poly->tail->next);

// Insert new term

newTerm->next = current;
prev->next = newTerm;

// Update tail if necessary

if (current == poly->tail->next) {
poly->tail = newTerm;
}
}

Doubly Linked Lists

Node Structure

typedef struct DoublyNode {

int data;
struct DoublyNode* prev;
struct DoublyNode* next;
} DoublyNode;

typedef struct {
 DoublyNode* head;
DoublyNode* tail;
int size;
} DoublyLinkedList;

Basic Operations
Initialization:

void initDoublyList(DoublyLinkedList* list) {

list->head = NULL;
list->tail = NULL;
list->size = 0;
}

DoublyNode* createDoublyNode(int data) {

DoublyNode* newNode = (DoublyNode*)malloc(sizeof(DoublyNode));
if (newNode == NULL) return NULL;

newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}

Insertion Operations:

void insertAtBeginningDoubly(DoublyLinkedList* list, int data) {

DoublyNode* newNode = createDoublyNode(data);
if (newNode == NULL) return;

if (list->head == NULL) {
list->head = list->tail = newNode;
} else {
newNode->next = list->head;
list->head->prev = newNode;
list->head = newNode;
}
list->size++;
}

void insertAtEndDoubly(DoublyLinkedList* list, int data) {

DoublyNode* newNode = createDoublyNode(data);
if (newNode == NULL) return;

if (list->tail == NULL) {
list->head = list->tail = newNode;
} else {
newNode->prev = list->tail;
list->tail->next = newNode;
list->tail = newNode;
}
list->size++;
 }

void insertAtPositionDoubly(DoublyLinkedList* list, int data, int position) {

if (position < 0 || position > list->size) return;

if (position == 0) {
insertAtBeginningDoubly(list, data);
return;
}

if (position == list->size) {
insertAtEndDoubly(list, data);
return;
}

DoublyNode* newNode = createDoublyNode(data);

if (newNode == NULL) return;

DoublyNode* current;

// Choose direction based on position

if (position <= list->size / 2) {
current = list->head;
for (int i = 0; i < position; i++) {
current = current->next;
}
} else {
current = list->tail;
for (int i = list->size - 1; i > position; i--) {
current = current->prev;
}
}

newNode->next = current;
newNode->prev = current->prev;
current->prev->next = newNode;
current->prev = newNode;
list->size++;
}

Deletion Operations:

int deleteByValueDoubly(DoublyLinkedList* list, int value) {

DoublyNode* current = list->head;

while (current != NULL && current->data != value) {

current = current->next;
}

if (current == NULL) return 0; // Value not found

// Update links
if (current->prev != NULL) {
current->prev->next = current->next;
} else {
 list->head = current->next;
}

if (current->next != NULL) {
current->next->prev = current->prev;
} else {
list->tail = current->prev;
}

free(current);
list->size--;
return 1;
}

void displayDoublyForward(DoublyLinkedList* list) {

DoublyNode* current = list->head;
printf("Forward: ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->next;
}
printf("NULL\n");
}

void displayDoublyBackward(DoublyLinkedList* list) {

DoublyNode* current = list->tail;
printf("Backward: ");
while (current != NULL) {
printf("%d <-> ", current->data);
current = current->prev;
}
printf("NULL\n");
}

Advantages of Doubly Linked Lists:

Bidirectional traversal
Easier deletion (no need to find previous node)
Better for certain algorithms (like deque implementation)
Disadvantages:
Extra memory for previous pointer
More complex insertion/deletion logic

UNIT-IV: Trees
Introduction to Trees

Definition
A tree is a hierarchical data structure consisting of nodes connected by edges, with one node
designated as the root. It's a connected acyclic graph.

Tree Terminology
Basic Terms:
Root: Top node with no parent
Parent: Node with children
Child: Node with a parent
Leaf/External Node: Node with no children
Internal Node: Node with at least one child
Siblings: Nodes with same parent
Ancestor: Node on path from root to given node
Descendant: Node in subtree rooted at given node
Structural Terms:
Path: Sequence of nodes connected by edges
Level/Depth: Distance from root (root is at level 0)
Height: Maximum level in tree
Degree: Number of children of a node
Subtree: Tree formed by node and all its descendants

Properties of Trees
1. n nodes ⟹ n-1 edges
2. Exactly one path between any two nodes
3. Removing any edge creates two trees
4. Adding any edge creates a cycle

Tree Representations

Array Representation (Complete Binary Trees)

// For complete binary tree with n nodes

// Root at index 1 (index 0 unused)
int tree[MAX_SIZE];

// Parent of node i: i/2

 // Left child of node i: 2*i
// Right child of node i: 2*i + 1

int parent(int i) { return i / 2; }

int leftChild(int i) { return 2 * i; }
int rightChild(int i) { return 2 * i + 1; }

Linked Representation

typedef struct TreeNode {

int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;

TreeNode* createTreeNode(int data) {

TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (newNode == NULL) return NULL;

newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

First Child-Next Sibling Representation

typedef struct GeneralTreeNode {

int data;
struct GeneralTreeNode* firstChild;
struct GeneralTreeNode* nextSibling;
} GeneralTreeNode;

Binary Trees

Definition
A binary tree is a tree where each node has at most two children, referred to as left child and
right child.

Types of Binary Trees

1. Full Binary Tree:
Every node has either 0 or 2 children
No node has only one child
2. Complete Binary Tree:
All levels filled except possibly the last
 Last level filled from left to right
3. Perfect Binary Tree:
All internal nodes have two children
All leaves at same level
4. Balanced Binary Tree:
Height difference between left and right subtrees ≤ 1 for all nodes

Properties of Binary Trees

Mathematical Properties:
1. Maximum nodes at level i: 2ⁱ
2. Maximum nodes in tree of height h: 2ʰ⁺¹ - 1
3. Minimum height for n nodes: ⌈log₂(n+1)⌉ - 1
4. In complete binary tree with n nodes:
Number of leaf nodes = ⌈n/2⌉
Number of internal nodes = ⌊n/2⌋

Binary Tree Traversals

Depth-First Traversals
1. Preorder (Root → Left → Right):

void preorderTraversal(TreeNode* root) {

if (root == NULL) return;

printf("%d ", root->data); // Process root

preorderTraversal(root->left); // Traverse left subtree
preorderTraversal(root->right); // Traverse right subtree
}

2. Inorder (Left → Root → Right):

void inorderTraversal(TreeNode* root) {

if (root == NULL) return;

inorderTraversal(root->left); // Traverse left subtree

printf("%d ", root->data); // Process root
inorderTraversal(root->right); // Traverse right subtree
}

3. Postorder (Left → Right → Root):

 void postorderTraversal(TreeNode* root) {
if (root == NULL) return;

postorderTraversal(root->left); // Traverse left subtree

postorderTraversal(root->right); // Traverse right subtree
printf("%d ", root->data); // Process root
}

Breadth-First Traversal (Level Order)

void levelOrderTraversal(TreeNode* root) {

if (root == NULL) return;

// Use queue for level order traversal

TreeNode* queue[1000];
int front = 0, rear = 0;

queue[rear++] = root;

while (front < rear) {

TreeNode* current = queue[front++];
printf("%d ", current->data);

if (current->left != NULL) {
queue[rear++] = current->left;
}
if (current->right != NULL) {
queue[rear++] = current->right;
}
}
}

Non-Recursive Traversals Using Stack

Preorder (Iterative):

void preorderIterative(TreeNode* root) {

if (root == NULL) return;

TreeNode* stack[1000];
int top = -1;

stack[++top] = root;

while (top >= 0) {

TreeNode* current = stack[top--];
printf("%d ", current->data);

// Push right first, then left (stack is LIFO)

if (current->right != NULL) {
stack[++top] = current->right;
}
 if (current->left != NULL) {
stack[++top] = current->left;
}
}
}

Inorder (Iterative):

void inorderIterative(TreeNode* root) {

TreeNode* stack[1000];
int top = -1;
TreeNode* current = root;

while (current != NULL || top >= 0) {

// Go to leftmost node
while (current != NULL) {
stack[++top] = current;
current = current->left;
}

// Process current node

current = stack[top--];
printf("%d ", current->data);

// Move to right subtree

current = current->right;
}
}

Binary Search Trees (BST)

Definition
A Binary Search Tree is a binary tree with the following properties:
For every node, all values in left subtree ≤ node value
For every node, all values in right subtree ≥ node value
Both left and right subt