Data Structures - Final Revision Notes

Stack using Linked List

What is Stack using Linked List?

A stack implementation that uses linked list instead of arrays
Follows LIFO (Last-In-First-Out) principle

Dynamic size - no overflow problem like array-based stacks

Each node has data and a pointer to the next node

Implementation:
c
#include <stdio.h>
#include <stdlib.h> // For malloc

// Structure for a node

struct Node {
int data; // Data of the node
struct Node* next; // Pointer to the next node
};

// Global variable - pointer to the top node

struct Node* top = NULL;

// Function to check if stack is empty

int isEmpty() {
if (top == NULL) { // If top is NULL
return 1; // Return true (stack is empty)
} else {
return 0; // Return false (stack is not empty)
}
}

// Function to push an element onto the stack

void push(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory
if (newNode == NULL) { // If memory allocation failed
printf("Stack Overflow\n");
return;
}
newNode->data = data; // Set the data
newNode->next = top; // Link newNode to current top
top = newNode; // Update top to newNode
printf("%d pushed to stack\n", data);
}

// Function to pop an element from the stack

int pop() {
if (isEmpty()) { // Check if stack is empty
printf("Stack Underflow\n"); // Print error message
return -1; // Return error value
} else {
struct Node* temp = top; // Store current top
int data = temp->data; // Get the data
top = top->next; // Update top to next node
free(temp); // Free the popped node
return data; // Return the data
}
 }

// Function to peek at the top element without removing it

int peek() {
if (isEmpty()) { // Check if stack is empty
printf("Stack is empty\n"); // Print error message
return -1; // Return error value
} else {
return top->data; // Return the top data
}
}

// Function to display the stack

void display() {
if (isEmpty()) { // Check if stack is empty
printf("Stack is empty\n"); // Print error message
return;
}
struct Node* temp = top; // Start from top
printf("Stack: ");
// Traverse and print each node
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

How Stack using Linked List Works:

1. Push Operation:
Create a new node

Set its data to the value being pushed

Point its next pointer to current top

Update top to point to this new node

Show Image

2. Pop Operation:
Check if stack is empty (top == NULL)

If not empty, store top node in temp

 Update top to point to next node
Free the temp node

Return the popped value

Show Image

3. Peek Operation:
Check if stack is empty (top == NULL)
If not empty, return data of top node without removing it

Advantages of Linked List Implementation over Arrays:

Dynamic size - no predefined limit

No overflow problem (unless memory is exhausted)

Better memory utilization - memory allocated as needed

Q&A Section - Stack using Linked List

1. Q: What is a stack using linked list? A: A stack implemented using a linked list data structure where
each element contains data and a pointer to the element beneath it. The top element is accessed with a
'top' pointer.

2. Q: What are the advantages of implementing a stack using linked list over arrays? A: Dynamic
size (no fixed capacity), no overflow condition, better memory utilization, and operations remain O(1)
time complexity.

3. Q: What are the basic operations of a stack using linked list? A: Push (insert at top), Pop (remove
from top), Peek/Top (view top element without removing), and IsEmpty (check if stack is empty).

4. Q: What is the time complexity of Push and Pop operations in a stack implemented using
linked list? A: Both operations have O(1) time complexity as they only involve manipulating the top
pointer.
5. Q: How is memory allocated for a stack implemented using linked list? A: Memory is
dynamically allocated for each node as elements are pushed onto the stack, using malloc() or similar
functions.

6. Q: What happens when Pop is called on an empty stack? A: It results in a "Stack Underflow"
condition, which should be handled by returning an error value or message.

7. Q: Where is the top element located in a stack implemented using linked list? A: The top
element is the node pointed to by the 'top' pointer, which is the head of the linked list.
 8. Q: Can a stack implemented using linked list ever be full? A: Theoretically no, unless the system
runs out of memory for allocating new nodes.

Queue using Linked List

What is Queue using Linked List?

A queue implementation that uses linked list instead of arrays

Follows FIFO (First-In-First-Out) principle

Dynamic size - grows and shrinks as needed

Uses front and rear pointers to track both ends

Implementation:
c
#include <stdio.h>
#include <stdlib.h> // For malloc

// Structure for a node

struct Node {
int data; // Data of the node
struct Node* next; // Pointer to the next node
};

// Global variables - pointers to the front and rear nodes

struct Node* front = NULL;
struct Node* rear = NULL;

// Function to check if queue is empty

int isEmpty() {
if (front == NULL) { // If front is NULL
return 1; // Return true (queue is empty)
} else {
return 0; // Return false (queue is not empty)
}
}

// Function to enqueue an element

void enqueue(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory
if (newNode == NULL) { // If memory allocation failed
printf("Queue Overflow\n");
return;
}
newNode->data = data; // Set the data
newNode->next = NULL; // Set next pointer to NULL

if (rear == NULL) { // If queue was empty

front = rear = newNode; // Set front and rear to newNode
} else {
rear->next = newNode; // Link rear to newNode
rear = newNode; // Update rear to newNode
}
printf("%d enqueued to queue\n", data);
}

// Function to dequeue an element

int dequeue() {
if (isEmpty()) { // Check if queue is empty
printf("Queue Underflow\n"); // Print error message
return -1; // Return error value
 } else {
struct Node* temp = front; // Store current front
int data = temp->data; // Get the data
front = front->next; // Update front to next node

if (front == NULL) { // If the last node was dequeued

rear = NULL; // Update rear to NULL
}

free(temp); // Free the dequeued node

return data; // Return the data
}
}

// Function to get the front element without removing it

int getFront() {
if (isEmpty()) { // Check if queue is empty
printf("Queue is empty\n"); // Print error message
return -1; // Return error value
} else {
return front->data; // Return the front data
}
}

// Function to display the queue

void display() {
if (isEmpty()) { // Check if queue is empty
printf("Queue is empty\n"); // Print error message
return;
}
struct Node* temp = front; // Start from front
printf("Queue: ");
// Traverse and print each node
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

How Queue using Linked List Works:

1. Enqueue Operation:
Create a new node
Set its data to the value being enqueued

If queue is empty, set both front and rear to this new node
 Otherwise, set rear's next to point to new node and update rear

Show Image

2. Dequeue Operation:
Check if queue is empty (front == NULL)
If not empty, store front node in temp

Update front to point to next node

If front becomes NULL, set rear to NULL as well
Free the temp node

Return the dequeued value

Show Image

Advantages of Queue using Linked List:

Dynamic size - no predefined limit

No overflow condition (unless memory is exhausted)

No need to implement as circular structure like in arrays
Efficient memory utilization

Q&A Section - Queue using Linked List

1. Q: What is a queue using linked list? A: A queue implemented using a linked list data structure
where elements are added at the rear and removed from the front, maintaining FIFO (First-In-First-Out)
order.
2. Q: What are the main pointers used in a queue implemented using linked list? A: Front pointer
(points to the first element for dequeue operations) and Rear pointer (points to the last element for
enqueue operations).
3. Q: What happens if we dequeue from an empty queue? A: It results in a "Queue Underflow"
condition, which should be handled by returning an error value or message.

4. Q: What is the time complexity of enqueue and dequeue operations in a queue implemented
using linked list? A: Both operations have O(1) time complexity as they only involve manipulating the
front and rear pointers.
 5. Q: How does queue using linked list overcome the limitations of array-based queue
implementation? A: It eliminates the need for circular implementation, has no fixed size limitation,
and utilizes memory efficiently.

6. Q: What happens to front and rear pointers when the last element is dequeued? A: Both front
and rear pointers are set to NULL, indicating an empty queue.
7. Q: Can a queue implemented using linked list ever be full? A: Theoretically no, unless the system
runs out of memory for allocating new nodes.

8. Q: What is the special case to handle during the dequeue operation? A: When dequeuing the last
element, we need to set both front and rear pointers to NULL to properly indicate an empty queue.

Reversing a Linked List

What is Reversing a Linked List?

A common operation to change the direction of links in a linked list
Each node's next pointer points to the previous node instead of the next node
The last node becomes the first node and vice versa

Implementation:
c
#include <stdio.h>
#include <stdlib.h> // For malloc

// Structure for a node

struct Node {
int data; // Data of the node
struct Node* next; // Pointer to the next node
};

// Global variable - pointer to the first node

struct Node* head = NULL;

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory
newNode->data = data; // Set the data
newNode->next = NULL; // Set next pointer to NULL
return newNode; // Return the new node
}

// Function to insert node at the end

void insertAtEnd(int data) {
struct Node* newNode = createNode(data); // Create a new node
if (head == NULL) { // If list is empty
head = newNode; // Set head to newNode
} else {
struct Node* temp = head; // Start from head
// Traverse to the last node
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode; // Link the last node to newNode
}
printf("%d inserted at the end\n", data);
}

// Function to display the linked list

void display() {
if (head == NULL) { // If list is empty
printf("List is empty\n");
return;
}
struct Node* temp = head; // Start from head
printf("Linked List: ");
// Traverse and print each node
while (temp != NULL) {
 printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

// Function to reverse the linked list

void reverse() {
if (head == NULL || head->next == NULL) { // If list is empty or has only one node
return; // No need to reverse
}
struct Node* prev = NULL; // Previous node
struct Node* current = head; // Current node
struct Node* next = NULL; // Next node

// Traverse the list and reverse the links

while (current != NULL) {
next = current->next; // Store the next node
current->next = prev; // Reverse the link
prev = current; // Move prev to current
current = next; // Move current to next
}
head = prev; // Update head to the last node (now the first)
printf("List reversed successfully\n");
}

How Reversing a Linked List Works:

1. Initialize three pointers: prev = NULL , current = head , next = NULL

2. Iterate through the linked list:

Store the next node: next = current->next

Reverse the current node's pointer: current->next = prev

Move prev to current position: prev = current

Move current to next position: current = next

3. Update the head pointer to point to the last node: head = prev

Show Image

Step-by-Step Example:
Given a linked list: 10 -> 20 -> 30 -> NULL

Step 1:

prev = NULL
current = 10

next = 20
10's next pointer now points to NULL

Step 2:

prev = 10
current = 20

next = 30
20's next pointer now points to 10

Step 3:

prev = 20

current = 30

next = NULL
30's next pointer now points to 20

Step 4:

prev = 30
current = NULL

head = 30

Result: 30 -> 20 -> 10 -> NULL

Q&A Section - Reversing a Linked List

1. Q: Why would we need to reverse a linked list? A: Reversing a linked list is useful in many
algorithms and applications, such as implementing undo operations, certain sorting techniques, or
when needing to process data in reverse order.

2. Q: What is the time complexity of reversing a linked list? A: O(n), where n is the number of nodes
in the linked list, as we need to traverse each node exactly once.

3. Q: What is the space complexity of the iterative approach to reverse a linked list? A: O(1), as we
only use a fixed number of pointers regardless of the list size.
4. Q: Can the reversal of a linked list be implemented recursively? A: Yes, a linked list can be
reversed recursively, though it has O(n) space complexity due to the recursion stack.
 5. Q: What are the edge cases to consider when reversing a linked list? A: Empty list (head = NULL)
and single-node list (head->next = NULL) - in both cases, no reversal is needed.

6. Q: How many pointers are needed to reverse a linked list iteratively? A: Three pointers: previous,
current, and next.

7. Q: After reversing a linked list, which node becomes the new head? A: The last node of the
original list becomes the new head.
8. Q: How does reversing a linked list affect its order? A: The elements appear in reverse order - the
first element becomes the last, the second becomes the second-last, and so on.

Trees

What are Trees?

A hierarchical data structure with nodes connected by edges

Non-linear - data is not stored in sequential order

Each node can have multiple children (except leaf nodes)
Only one path exists between any two nodes

Basic Tree Terms:

Root: The topmost node of a tree
Node: Each element in a tree that contains data and pointers to children

Edge: The link between two nodes

Parent: A node that has one or more child nodes

Child: A node that has a parent node

Leaf: A node with no children
Siblings: Nodes with the same parent

Height: The length of the longest path from the root to a leaf

Depth: The length of the path from the root to a node

Level: The depth of a node plus 1

Binary Tree
A tree in which each node has at most two children

Children are typically referred to as "left child" and "right child"

Types of Binary Trees:

1. Full Binary Tree: Every node has 0 or 2 children
2. Complete Binary Tree: All levels are filled except possibly the last level, which is filled from left to right
 3. Perfect Binary Tree: All internal nodes have two children and all leaves are at the same level
4. Balanced Binary Tree: Height of the tree is O(log n), where n is the number of nodes

5. Degenerate (or Pathological) Tree: Every parent node has only one child

Show Image

Binary Tree Traversals

There are three main ways to traverse a binary tree:

1. In-order Traversal (Left, Root, Right):

Visit the left subtree

Visit the root node

Visit the right subtree

Result: Nodes in ascending order for BST

2. Pre-order Traversal (Root, Left, Right):

Visit the root node

Visit the left subtree

Visit the right subtree

Useful for: Creating a copy of the tree

3. Post-order Traversal (Left, Right, Root):

Visit the left subtree

Visit the right subtree

Visit the root node
Useful for: Deleting a tree

Show Image

Binary Search Tree (BST)

A binary tree where:

The left subtree of a node contains only nodes with keys less than the node's key
 The right subtree of a node contains only nodes with keys greater than the node's key
Both the left and right subtrees must also be binary search trees

Show Image

Implementing a Simple Binary Search Tree:

c
#include <stdio.h>
#include <stdlib.h>

// Structure for a tree node

struct Node {
int data; // Node value
struct Node* left; // Pointer to left child
struct Node* right; // Pointer to right child
};

// Function to create a new node

struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Function to insert a node into BST

struct Node* insert(struct Node* root, int data) {
// If tree is empty, create a new node
if (root == NULL) {
return createNode(data);
}

// Otherwise, recur down the tree

if (data < root->data) {
root->left = insert(root->left, data);
} else if (data > root->data) {
root->right = insert(root->right, data);
}

// Return unchanged root pointer

return root;
}

// Function for inorder traversal

void inorder(struct Node* root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
// Function for preorder traversal
void preorder(struct Node* root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}

// Function for postorder traversal

void postorder(struct Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}

// Function to search a key in BST

struct Node* search(struct Node* root, int key) {
// Base case: root is NULL or key is present at root
if (root == NULL || root->data == key)
return root;

// Key is greater than root's data

if (root->data < key)
return search(root->right, key);

// Key is smaller than root's data

return search(root->left, key);
}

// Function to find the minimum value node

struct Node* minValueNode(struct Node* node) {
struct Node* current = node;

// Find the leftmost leaf

while (current && current->left != NULL)
current = current->left;

return current;
}

// Function to delete a node from BST

struct Node* deleteNode(struct Node* root, int key) {
// Base case
if (root == NULL) return root;
 // If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root->data)
root->left = deleteNode(root->left, key);

// If the key is larger than the root's key

else if (key > root->data)
root->right = deleteNode(root->right, key);

// If key is same as root's key, then this is the node to be deleted

else {
// Node with only one child or no child
if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

// Node with two children: Get the inorder successor (smallest

// in the right subtree)
struct Node* temp = minValueNode(root->right);

// Copy the inorder successor's content to this node

root->data = temp->data;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->data);
}
return root;
}

Q&A Section - Trees

1. Q: What is a tree data structure? A: A tree is a hierarchical, non-linear data structure consisting of
nodes connected by edges, where each node can have multiple children but only one parent (except the
root node).
2. Q: What is the difference between a binary tree and a binary search tree? A: A binary tree is a
tree where each node has at most two children. A binary search tree is a special type of binary tree
 where for each node, all elements in the left subtree are less than the node, and all elements in the right
subtree are greater.

3. Q: What are the common traversal methods for a binary tree? A: The common traversal methods
are: in-order (left-root-right), pre-order (root-left-right), and post-order (left-right-root).

4. Q: Why is in-order traversal important for binary search trees? A: In-order traversal of a binary
search tree visits nodes in ascending order, which is useful for obtaining sorted data.
5. Q: What is the maximum number of nodes at level 'L' of a binary tree? A: 2^L (where the root is
at level 0).
6. Q: What is a balanced binary tree? A: A binary tree in which the height of the left and right subtrees
of any node differ by not more than 1.
7. Q: What is the height of a perfect binary tree with 'n' nodes? A: log₂(n+1) - 1
8. Q: What is the time complexity of searching, insertion and deletion in a binary search tree? A:
Average case: O(log n), Worst case (unbalanced tree): O(n)
9. Q: What is a leaf node in a tree? A: A node that has no children.

10. Q: How do you find the height of a binary tree? A: The height is the length of the longest path from
the root to any leaf. It can be calculated recursively as max(height(left subtree), height(right subtree)) +
1.
11. Q: What is a complete binary tree? A: A binary tree in which all levels are completely filled except
possibly the last level, which is filled from left to right.

12. Q: What are the applications of binary trees? A: Binary trees are used in expression evaluation,
Huffman coding for data compression, priority queues, and as a basis for other data structures like
heaps and binary search trees.

Applications of Data Structures

Stack Applications

1. Infix, Prefix, and Postfix Conversion and Evaluation

Expression Notations:

Infix: Operators between operands (e.g., A + B)

Prefix: Operators before operands (e.g., + A B)

Postfix: Operators after operands (e.g., A B +)

Converting Infix to Postfix using Stack:

 Step Description

1 Scan infix expression from left to right

2 If scanned character is operand, output it

3 If scanned character is operator, check precedence with operator at stack top

4 If higher precedence, push onto stack

5 If lower/equal precedence, pop stack until higher precedence found, then push

6 If opening bracket, push onto stack

7 If closing bracket, pop stack until matching opening bracket found

8 After scanning entire expression, pop remaining operators from stack

 

Example:
Converting A + B * C to postfix:

1. Scan 'A': Output A

2. Scan '+': Push onto stack

3. Scan 'B': Output AB

4. Scan '': '' has higher precedence than '+', push onto stack
5. Scan 'C': Output ABC

6. Pop remaining operators: '' then '+': Output ABC+

Evaluating Postfix Expressions:

1. Scan postfix expression from left to right

2. If operand, push onto stack
3. If operator, pop top two elements, apply operator, push result back

Example:
Evaluating 6 2 3 + - 3 8 2 / + * 2 ^

1. Push 6, Push 2, Push 3

2. '+': Pop 3, Pop 2, Push (2+3)=5

3. '-': Pop 5, Pop 6, Push (6-5)=1

4. Push 3, Push 8, Push 2

5. '/': Pop 2, Pop 8, Push (8/2)=4

6. '+': Pop 4, Pop 3, Push (3+4)=7

7. '': Pop 7, Pop 1, Push (17)=7
8. Push 2

9. '^': Pop 2, Pop 7, Push (7^2)=49 Result: 49

2. Parentheses Checker

A stack can be used to check if an expression has balanced parentheses:

c
#include <stdio.h>
#include <string.h>
#define MAX 100

// Global variables
char stack[MAX]; // Stack to store opening brackets
int top = -1; // Index of top element

// Function to push a character onto stack

void push(char c) {
if (top == MAX - 1) { // Check if stack is full
printf("Stack Overflow\n"); // Print error message
} else {
stack[++top] = c; // Increment top and push character
}
}

// Function to pop a character from stack

char pop() {
if (top == -1) { // Check if stack is empty
printf("Stack Underflow\n"); // Print error message
return '\0'; // Return null character
} else {
return stack[top--]; // Return character and decrement top
}
}

// Function to check if stack is empty

int isEmpty() {
if (top == -1) { // If top is -1
return 1; // Return true (stack is empty)
} else {
return 0; // Return false (stack is not empty)
}
}

// Function to check if two characters are matching brackets

int isMatchingPair(char character1, char character2) {
if (character1 == '(' && character2 == ')') {
return 1;
} else if (character1 == '{' && character2 == '}') {
return 1;
} else if (character1 == '[' && character2 == ']') {
return 1;
} else {
return 0;
 }
}

// Function to check if an expression has balanced brackets

int areBracketsBalanced(char expr[]) {
int i = 0;
// Traverse the expression
for (i = 0; expr[i] != '\0'; i++) {
// If the current character is an opening bracket, push it onto stack
if (expr[i] == '(' || expr[i] == '{' || expr[i] == '[') {
push(expr[i]);
}
// If the current character is a closing bracket
else if (expr[i] == ')' || expr[i] == '}' || expr[i] == ']') {
// If stack is empty or the top bracket doesn't match
if (isEmpty() || !isMatchingPair(pop(), expr[i])) {
return 0; // Not balanced
}
}
}
// If stack is empty, the expression is balanced
return isEmpty();
}

How it Works:

1. Push opening brackets onto stack

2. When closing bracket found:

If stack is empty or top doesn't match - unbalanced

If top matches - pop and continue

3. If stack is empty at end - balanced

Example:
Expression: { [ ( ) ] }

1. Push {, [, (
2. Pop ( for )
3. Pop [ for ]

4. Pop { for }
5. Stack is empty - balanced!

Tree Applications

1. Expression Tree
An expression tree is a binary tree that represents an arithmetic expression:

Leaf nodes are operands (numbers or variables)

Internal nodes are operators (+, -, *, /, etc.)

Show Image

Benefits:

Easy to evaluate expressions

Maintains operator precedence

Simplifies expression parsing

How to Evaluate an Expression Tree:

1. Recursively evaluate left subtree

2. Recursively evaluate right subtree

3. Apply root operator to the results

2. Huffman Encoding

Huffman encoding is a technique for loss