Essential Concepts in Data Structures and Algorithms

Posted on May 29, 2025 in Computer Engineering

Data Structures and Abstract Data Types

A data structure is a specialized format for organizing, processing, and storing data in a computer so that it can be accessed and modified efficiently. Data structures are essential for managing large amounts of data and are fundamental to computer science and programming. They provide a way to manage data in a way that enables efficient algorithms to operate on that data.

Abstract Data Type (ADT) Explained

An Abstract Data Type (ADT) is a theoretical concept that defines a data type purely in terms of its behavior (operations) from the point of view of a user, without specifying how these operations are implemented. An ADT specifies the data and the operations that can be performed on that data, but it does not dictate how these operations are to be executed. This abstraction allows for flexibility in implementation while providing a clear interface for users.

Stack: A Classic ADT Example

A Stack is a classic example of an ADT. It is a collection of elements that follows the Last In, First Out (LIFO) principle. The main operations associated with a stack are:

  1. Push: Add an element to the top of the stack.
  2. Pop: Remove the element from the top of the stack.
  3. Peek/Top: Retrieve the element at the top of the stack without removing it.
  4. IsEmpty: Check if the stack is empty.

Time Complexity and Big O Notation

Time complexity describes how the runtime of an algorithm grows as the input size increases. Big O notation is a standard way to express this, focusing on the worst-case scenario. Essentially, it provides an upper bound on the algorithm’s performance.

Big O notation is a way to represent the growth rate of an algorithm’s runtime. It’s not about the exact time it takes to run the algorithm, but rather how the runtime changes as the input size increases. We focus on the worst-case scenario because we want to ensure the algorithm performs well even when dealing with the largest possible input.

Common Big O Notations Explained

  • O(1) – Constant Time: The algorithm takes the same amount of time regardless of the input size.
  • O(log n) – Logarithmic Time: The runtime increases as the logarithm of the input size.
  • O(n) – Linear Time: The runtime increases proportionally to the input size.
  • O(n log n) – Log-Linear Time: The runtime increases linearly with the logarithm of the input size.
  • O(n²) – Quadratic Time: The runtime increases with the square of the input size.
  • O(2^n) – Exponential Time: The runtime doubles with each increase in the input size.

Understanding Linked List Types

Linked lists are a fundamental data structure in computer science that consist of a sequence of elements, where each element points to the next one. There are several types of linked lists, each with its own characteristics and use cases. Here are the main types:

Singly Linked List

In a singly linked list, each node contains data and a pointer to the next node in the sequence. It allows traversal in one direction (from head to tail).

Doubly Linked List

A doubly linked list contains nodes that have pointers to both the next and the previous nodes. This allows traversal in both directions.

Circular Linked List

In a circular linked list, the last node points back to the first node, forming a circle. This can be implemented as either a singly or doubly linked list.

Circular Doubly Linked List

A circular doubly linked list combines the features of both circular and doubly linked lists. Each node points to both its next and previous nodes, and the last node points back to the first node.

Linear Search Algorithm Implementation

#include <iostream>
#include <vector>

using namespace std;

int search(vector<int>& arr, int x) {
    for (int i = 0; i < arr.size(); i++)
        if (arr[i] == x)
            return i;
    return -1;
}

int main() {
    vector<int> arr = {2, 3, 4, 10, 40};
    int x = 10;
    int res = search(arr, x);
    if (res == -1)
        cout << "Not Present";
    else
        cout << "Present at Index " << res;
    return 0;
}

Tower of Hanoi Problem and Solution

The Tower of Hanoi (TOH) is a classic mathematical puzzle involving three rods and a set of disks of different sizes, stacked in decreasing order of size on one rod. The objective is to move the entire stack to another rod, following specific rules: only one disk can be moved at a time, and a larger disk cannot be placed on top of a smaller disk. The solution involves a recursive algorithm that can be broken down into smaller, similar subproblems.

Tower of Hanoi Problem Definition

  • Three rods (A, B, C) and N disks of different sizes.
  • All disks are initially on rod A, stacked in decreasing order of size.
  • Goal: Move all disks from rod A to rod C, following the rules.

Tower of Hanoi Rules

  • Only one disk can be moved at a time.
  • A disk can only be moved if it’s the topmost disk on a stack.
  • No disk can be placed on top of a smaller disk.

Tower of Hanoi Recursive Solution

The TOH problem can be solved using a recursive algorithm. Here’s the breakdown:

  1. Base Case:
    If there’s only one disk, move it directly from the source rod to the destination rod.
  2. Recursive Step:
    If there are N disks:
    • Move the top (N-1) disks from the source rod to the auxiliary rod using the destination rod as the auxiliary.
    • Move the largest disk (Nth disk) from the source rod to the destination rod.
    • Move the (N-1) disks from the auxiliary rod to the destination rod using the source rod as the auxiliary.