Data Structures and Algorithms: Essential Reference

Posted on Mar 8, 2026 in Computer Engineering

Data Structure Definition and Operations

A data structure is a systematic way of organizing, storing, and managing data in a computer so that it can be accessed, updated, and processed efficiently.

How Data is Processed in a Data Structure

Data is processed in a data structure through the following basic operations:

• Insertion: Adding new data elements into the data structure.
• Deletion: Removing existing data elements.
• Traversal: Accessing and visiting each data element to perform some operation.
• Searching: Finding a particular data element in the structure.
• Sorting: Arranging data elements in a specific order (ascending or descending).
• Updating: Modifying existing data values.

These operations are performed using algorithms, and the efficiency of data processing depends on the type of data structure used (array, linked list, stack, queue, tree, etc.).

In short: Data structures help in efficient data processing, better memory utilization, faster access, and easier data management.

Binary Tree, Complete, and Almost Complete Trees

1. Binary Tree: A binary tree is a tree data structure in which each node has at most two children, called the left child and the right child. It is used in searching, sorting, and hierarchical data representation.
2. Complete Binary Tree: A complete binary tree is a binary tree in which all levels are completely filled, except possibly the last level, and the nodes in the last level are filled from left to right.
3. Almost Complete Binary Tree: An almost complete binary tree is a binary tree where all levels are fully filled except the last level, and the last level may not be completely filled, but nodes must be filled from left to right with no gaps.

In short: Binary Tree: Each node has at most two children. Complete Binary Tree: All levels full except possibly the last, filled left to right. Almost Complete Binary Tree: Similar to complete, but last level may be partially filled without gaps.

Difference Between Iteration and Recursion

In short: Iteration is loop-based and memory efficient. Recursion is function-based and useful for complex problems like trees and graphs.

Abstract Data Type (ADT) Concepts

An Abstract Data Type (ADT) is a logical description of a data type that defines what operations can be performed on the data and how data behaves, without specifying how the data is implemented in memory.

In ADT, implementation details are hidden and only operations and behavior are visible to the user.

Key Points of ADT

• Focuses on what operations are performed, not how.
• Provides data abstraction.
• Implementation can change without affecting the user.
• Improves modularity and security.

Example: Stack as an ADT

Stack ADT Operations:

• push() – insert an element
• pop() – remove top element
• peek() – view top element
• isEmpty() – check if stack is empty

ADT Representation (Text Diagram)

ADT (Stack)
--------------------
Data: Collection of elements
--------------------
Operations:
  push()
  pop()
  peek()
  isEmpty()
--------------------
      ↓
Implementation (Hidden)
Array / Linked List

In short: An ADT defines data and operations logically, independent of implementation, allowing flexibility and better program design.

Stack Definition and Operations

A stack is a linear data structure that follows the principle LIFO (Last In, First Out). Insertion and deletion of elements are performed only at one end, called the TOP.

Example: Stack of books, plates, coins.

Operations on Stack

1. Push: Adds an element to the top of the stack. Causes overflow if the stack is full.
2. Pop: Removes the top element from the stack. Causes underflow if the stack is empty.
3. Peek / Top: Returns the top element without removing it.
4. isEmpty: Checks whether the stack has no elements.
5. isFull: Checks whether the stack is completely filled (in array implementation).

In short: A stack allows data access from one end only and is widely used in function calls, recursion, expression evaluation, and undo/redo operations.

Doubly Linked List Traversal Algorithms

Below are both traversal algorithms and programs for a Doubly Linked List:

1. Forward traversal
2. Backward traversal

Forward Traversal Algorithm (Left → Right)

START
If head = NULL
   Print "List is empty"
   STOP
Set temp = head
While temp ≠ NULL
   Print temp->data
   temp = temp->next
STOP

Backward Traversal Algorithm (Right → Left)

START
If head = NULL
   Print "List is empty"
   STOP
Set temp = head
While temp->next ≠ NULL
   temp = temp->next
While temp ≠ NULL
   Print temp->data
   temp = temp->prev
STOP

C / C++ Program for Doubly Linked List Traversal

#include <iostream>
using namespace std;

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

void forwardTraversal(Node* head) {
    Node* temp = head;
    cout << "Forward Traversal: ";
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

void backwardTraversal(Node* head) {
    Node* temp = head;
    if (temp == NULL) return;

    // Move to last node
    while (temp->next != NULL) {
        temp = temp->next;
    }

    cout << "Backward Traversal: ";
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->prev;
    }
    cout << endl;
}

In short: Forward traversal uses the next pointer. Backward traversal uses the prev pointer. Doubly linked lists allow two-way traversal, unlike singly linked lists.

If you want, I can also give exam-oriented short answers or only algorithms without code.

Linear Data Structure Definition and Operations

A linear data structure is a type of data structure in which data elements are arranged sequentially in a linear order, where each element is connected to its previous and next element (except the first and last).

Examples: Array, Linked List, Stack, Queue

Operations on Linear Data Structures

1. Insertion: Adding a new element at a specific position (beginning, middle, or end).
2. Deletion: Removing an existing element from a specific position.
3. Traversal: Accessing each element one by one to process or display data.
4. Searching: Finding the location of a particular element in the structure.
5. Sorting: Arranging elements in a particular order (ascending or descending).
6. Merging: Combining two linear data structures into one.
7. Updating: Modifying the value of an existing element.

In short: Linear data structures store data sequentially, making them easy to implement and traverse, and they support basic operations like insertion, deletion, searching, and traversal.

Properties of the Array Data Type

An array is a collection of homogeneous elements (same data type) stored in contiguous memory locations and accessed using a common name with an index.

Main Properties of an Array

1. Homogeneous elements: All elements of an array must be of the same data type (int, float, char, etc.).
2. Contiguous memory allocation: Array elements are stored in adjacent memory locations, which allows fast access.
3. Fixed size: The size of an array is decided at the time of declaration and cannot be changed dynamically (in static arrays).
4. Index-based access: Each element is accessed using an index number, usually starting from 0.
5. Random access: Any element can be accessed directly using its index in O(1) time.
6. Ordered collection: Elements are stored in a sequence, maintaining their order.

Is Array a Structured Data Type?

Yes, an array is a structured data type because: It groups multiple data items under one name. All elements are logically related. It allows data to be processed as a single unit.

Important Features of an Array

• Stores multiple values of the same type.
• Fast access using index.
• Efficient for searching and sorting operations.

Sequential and Binary Searching Techniques

1. Sequential Searching (Linear Search)

Sequential searching is a method of searching in which each element of the list is checked one by one until the required element is found or the list ends.

• Working: Start from the first element and compare it with the key. Continue sequentially.
• Advantages: Simple and easy to implement, works on unsorted data, suitable for small data sets.
• Disadvantages: Slow for large data sets, time complexity is O(n), inefficient compared to binary search.

2. Binary Searching

Binary searching is a fast searching technique that works by dividing the search space into two halves repeatedly.

• Condition: Data must be sorted.
• Working: Compare the key with the middle element and eliminate half of the data each time.
• Advantages: Very fast searching method, time complexity is O(log n), efficient for large data sets.
• Disadvantages: Requires sorted data, more complex to implement, not suitable for linked lists (inefficient access).

Bubble Sort and Selection Sort Implementation

Below are two sorting techniques explained in detail with algorithm and program (exam-oriented).

1. Bubble Sort

Bubble sort is a simple sorting technique in which adjacent elements are compared and swapped if they are in the wrong order. This process is repeated until the list is sorted.

Algorithm (Bubble Sort)

START
Read n elements into array A
For i = 0 to n-1
   For j = 0 to n-i-2
      If A[j] > A[j+1]
         Swap A[j] and A[j+1]
STOP

C++ Program (Bubble Sort)

#include <iostream>
using namespace std;

int main() {
    int n, a[50];
    cout << "Enter number of elements: ";
    cin >> n;

    cout << "Enter elements:\n";
    for(int i = 0; i < n; i++)
        cin >> a[i];

    for(int i = 0; i < n-1; i++) {
        for(int j = 0; j < n-i-1; j++) {
            if(a[j] > a[j+1]) {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }

    cout << "Sorted array:\n";
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";

    return 0;
}

Time Complexity: Best case: O(n), Worst case: O(n²)

2. Selection Sort

Selection sort works by selecting the smallest element from the unsorted part of the array and placing it at the beginning. This process continues until the array is sorted.

Algorithm (Selection Sort)

START
Read n elements into array A
For i = 0 to n-1
   Set min = i
   For j = i+1 to n-1
      If A[j] < A[min]
         min = j
   Swap A[i] and A[min]
STOP

C++ Program (Selection Sort)

#include <iostream>
using namespace std;

int main() {
    int n, a[50];
    cout << "Enter number of elements: ";
    cin >> n;

    cout << "Enter elements:\n";
    for(int i = 0; i < n; i++)
        cin >> a[i];

    for(int i = 0; i < n-1; i++) {
        int min = i;
        for(int j = i+1; j < n; j++) {
            if(a[j] < a[min])
                min = j;
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
    return 0;
}

Time Complexity: Best case: O(n), Worst case: O(n²)

Selection Sort (Repeated Entry)

Selection sort works by selecting the smallest element from the unsorted part of the array and placing it at the beginning. This process continues until the array is sorted.

Algorithm (Selection Sort)

START
Read n elements into array A
For i = 0 to n-1
   Set min = i
   For j = i+1 to n-1
      If A[j] < A[min]
         min = j
   Swap A[i] and A[min]
STOP

C++ Program (Selection Sort)

#include <iostream>
using namespace std;

int main() {
    int n, a[50];
    cout << "Enter number of elements: ";
    cin >> n;

    cout << "Enter elements:\n";
    for(int i = 0; i < n; i++)
        cin >> a[i];

    for(int i = 0; i < n-1; i++) {
        int min = i;
        for(int j = i+1; j < n; j++) {
            if(a[j] < a[min])
                min = j;
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }

    cout << "Sorted array:\n";
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";

    return 0;
}

Time Complexity: Best case: O(n²), Worst case: O(n²)

Comparison (Short)

Graph Representations: Adjacency Lists and Matrices

Graphs are a fundamental data structure in computer science, and there are several ways to represent them. Two common methods are adjacency lists and adjacency matrices.

Adjacency List

An adjacency list is a data structure used to represent a graph, where each index in the list corresponds to a vertex in the graph, and the value at that index is a list of adjacent vertices.

Example: Suppose we have a graph with 5 vertices (A, B, C, D, E) and the following edges: A -> B, A -> C, B -> D, C -> E, D -> E.

The adjacency list representation would be:

• A -> [B, C]
• B -> [D]
• C -> [E]
• D -> [E]
• E -> []

Diagram:

A -> B -> C
B -> D
C -> E
D -> E
E ->

Adjacency Matrix

An adjacency matrix is a square matrix used to represent a graph, where the entry at row i and column j is 1 if there is an edge between vertex i and vertex j, and 0 otherwise.

Example:

Using the same graph as above, the adjacency matrix representation would be:

  A B C D E
A 0 1 1 0 0
B 0 0 0 1 0
C 0 0 0 0 1
D 0 0 0 0 1
E 0 0 0 0 0

Diagram:

  A B C D E
A 0 1 1 0 0
B 0 0 0 1 0
C 0 0 0 0 1
D 0 0 0 0 1
E 0 0 0 0 0

Comparison

In general, adjacency lists are more efficient for sparse graphs (i.e., graphs with few edges), while adjacency matrices are more efficient for dense graphs (i.e., graphs with many edges).

Code Representation (Python)

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [[] for _ in range(num_vertices)]
        self.adj_matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]

    def add_edge(self, v, w):
        self.adj_list[v].append(w)
        self.adj_matrix[v][w] = 1

    def print_adj_list(self):
        for i in range(self.num_vertices):
            print(i, "->", self.adj_list[i])

Linked List Types and Algorithms

Linked List: A linked list is a dynamic data structure where elements are stored in separate objects, called “nodes.” Each node contains two items:

1. Data: The actual data stored in the node.
2. Next: A reference (or link) to the next node in the sequence.

Types of Linked Lists

• Singly Linked List: Each node has a reference to the next node.
• Doubly Linked List: Each node has references to both the previous and next nodes.
• Circularly Linked List: The last node points back to the first node.

Algorithm (Singly Linked List)

Insertion:

1. Create a new node with given data.
2. If list is empty, set head to new node.
3. Else, traverse to the end of the list and set last node’s next to new node.

Deletion:

1. Find the node to be deleted.
2. Update previous node’s next to skip the node to be deleted.
3. Free the node’s memory.

Traversal:

1. Start at the head node.
2. Process the node’s data.
3. Move to the next node until end of list.

Example (Singly Linked List)

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

// Insert node at end
void insertNode(Node** head, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = NULL;
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* last = *head;
        while (last->next != NULL) {
            last = last->next;
        }
        last->next = newNode;
    }
}

// Print list
void printList(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

Tree and Binary Tree Traversal Methods

Tree: A tree is a non-linear data structure consisting of nodes, where each node has a value and zero or more child nodes. The topmost node is called the root, and the nodes below it are called child nodes or subtrees. Trees are used to represent hierarchical relationships between data.

Binary Tree: A binary tree is a type of tree where each node has at most two child nodes, referred to as the left child and the right child. Binary trees are used in many applications, such as file systems, database indexing, and compiler design.

Binary Tree Traversal Methods

There are three primary binary tree traversal methods:

1. Inorder Traversal (Left-Root-Right): Traverse the left subtree, visit the root node, then traverse the right subtree.
2. Preorder Traversal (Root-Left-Right): Visit the root node, traverse the left subtree, then traverse the right subtree.
3. Postorder Traversal (Left-Right-Root): Traverse the left subtree, traverse the right subtree, then visit the root node.

Example Binary Tree:

     1
    / \
   2   3
  / \   \
 4   5   6

Traversal Examples:

• Inorder Traversal: 4, 2, 5, 1, 3, 6
• Preorder Traversal: 1, 2, 4, 5, 3, 6
• Postorder Traversal: 4, 5, 2, 6, 3, 1

C++ Code for Binary Tree Traversal

#include <iostream>

struct Node {
    int data;
    Node* left;
    Node* right;
};

void inorderTraversal(Node* root) {
    if (root) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

void preorderTraversal(Node* root) {
    if (root) {
        std::cout << root->data << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

void postorderTraversal(Node* root) {
    if (root) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        std::cout << root->data << " ";
    }
}

int main() {
    Node* root = new Node{1};
    root->left = new Node{2};
    root->right = new Node{3};
    root->left->left = new Node{4};
    root->left->right = new Node{5};
    root->right->right = new Node{6};

    std::cout << "Inorder Traversal: ";
    inorderTraversal(root);
    std::cout << std::endl;

    std::cout << "Preorder Traversal: ";
    preorderTraversal(root);
    std::cout << std::endl;

    std::cout << "Postorder Traversal: ";
    postorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

Output:
Inorder Traversal: 4 2 5 1 3 6
Preorder Traversal: 1 2 4 5 3 6
Postorder Traversal: 4 5 2 6 3 1

Graph Theory: Directed, Connected, and Complete Graphs

Graph: A graph is a non-linear data structure consisting of nodes or vertices connected by edges. Graphs are used to represent relationships between objects or entities.

Directed Graph (Digraph): A directed graph is a graph where edges have direction, represented by arrows. Each edge has a direction and can be traversed only in one direction.

Example: A -> B, B -> C, C -> A

Connected Graph: A connected graph is a graph where there is a path between every pair of vertices. In other words, it is possible to reach any vertex from any other vertex by traversing the edges.

Example: A — B, | / |, C — D

Complete Graph: A complete graph is a graph where every vertex is connected to every other vertex. In other words, every vertex is adjacent to every other vertex.

Example: A — B, | / |, B — A, | \ |, C — C

Key Characteristics

• Vertices (Nodes): Represented by circles or points.
• Edges: Represented by lines or arrows.
• Direction: Edges can be directed (one-way) or undirected (two-way).
• Weight: Edges can have weights or labels associated with them.

Types of Graphs

• Simple Graph: No multiple edges between vertices.
• Multigraph: Multiple edges between vertices allowed.
• Weighted Graph: Edges have weights or labels.
• Unweighted Graph: Edges do not have weights or labels.

Graph Terminology

• Vertex (Node): A point in the graph.
• Edge: A connection between two vertices.
• Adjacent: Two vertices are adjacent if they are connected by an edge.
• Degree: The number of edges incident on a vertex.
• Path: A sequence of vertices and edges.
• Cycle: A path that starts and ends at the same vertex.

cout << a[i] << " ";
return 0; }

Time Complexity: Best case: O(n²), Worst case: O(n²)

Comparison (Short)

Graph Representations: Adjacency Lists and Matrices

Graphs are a fundamental data structure in computer science, and there are several ways to represent them. Two common methods are adjacency lists and adjacency matrices.

Adjacency List

An adjacency list is a data structure used to represent a graph, where each index in the list corresponds to a vertex in the graph, and the value at that index is a list of adjacent vertices.

Example: Suppose we have a graph with 5 vertices (A, B, C, D, E) and the following edges: A -> B, A -> C, B -> D, C -> E, D -> E.

The adjacency list representation would be:

• A -> [B, C]
• B -> [D]
• C -> [E]
• D -> [E]
• E -> []

Diagram:

A -> B -> C
B -> D
C -> E
D -> E
E ->

Adjacency Matrix

An adjacency matrix is a square matrix used to represent a graph, where the entry at row i and column j is 1 if there is an edge between vertex i and vertex j, and 0 otherwise.