Data Structures and Algorithms: Definitions and Analysis

Posted on Nov 18, 2025 in Computers

Data Structures: Definition and Categories

A data structure is a specialized way of organizing, storing, and managing data in a computer to enable efficient access, manipulation, and operations. It defines how data is stored and the relationships between data elements.

Data structures are categorized into two main types:

• Primitive Data Structures: These are basic building blocks like integers, floats, characters, and booleans, which handle simple data types directly supported by the programming language.
• Non-Primitive Data Structures: These are complex structures built from primitives, divided into:
  • Linear Data Structures: Data elements are arranged sequentially (e.g., arrays, linked lists, stacks, queues).
  • Non-Linear Data Structures: Data elements are organized in a hierarchical or interconnected way (e.g., trees, graphs).

These categories help in choosing the right structure based on the problem’s requirements for time and space efficiency.

Types of Data Structures

A data structure is a systematic format for storing and organizing data to allow efficient operations like insertion, deletion, and traversal.

Different types of data structures include:

• Array: A fixed-size collection of elements of the same type, accessed via indices (e.g., [1, 2, 3]).
• Linked List: A dynamic collection where elements (nodes) are connected via pointers; types include singly, doubly, and circular linked lists.
• Stack: A LIFO (Last In, First Out) structure; operations are limited to one end (the top).
• Queue: A FIFO (First In, First Out) structure; operations occur at the front and rear.
• Tree: A hierarchical structure with nodes having child nodes (e.g., binary tree, binary search tree).
• Graph: A non-linear structure with nodes (vertices) connected by edges, representing networks.
• Hash Table: Uses hashing for key-value pairs, enabling O(1) average-time lookups.

Types are chosen based on the operations needed, such as search speed or memory usage.

Algorithms: Definition and Characteristics

An algorithm is a finite sequence of well-defined, step-by-step instructions or rules designed to solve a problem or perform a computation, typically taking input and producing output.

Characteristics of an Algorithm

• Finiteness: It must terminate after a finite number of steps; there should be no infinite loops.
• Definiteness: Each step must be precisely defined, unambiguous, and executable.
• Input: It can have zero or more well-specified inputs.
• Output: It must produce at least one well-specified output (a solution or result).
• Effectiveness: Every step must be basic enough to be carried out in a finite time, usually by a computer.

Algorithms are foundational in programming, ensuring problems are solved efficiently and correctly.

Algorithm Complexity and Efficiency Analysis

Complexity of an algorithm refers to the resources (time or space) required for its execution as a function of the input size (n). It measures efficiency, often using Big O notation to describe worst-case behavior.

Different Types of Complexity

• Time Complexity: Measures the amount of time (number of operations) needed. E.g., O(1) constant, O(n) linear, O(n²) quadratic, O(log n) logarithmic.
• Space Complexity: Measures the memory (extra space) used, excluding input. This includes auxiliary space for variables and the recursion stack. E.g., O(1) constant space, O(n) linear space.
• Best-Case Complexity: Minimum resources required for the easiest input (e.g., O(1) for a sorted array in binary search).
• Average-Case Complexity: Expected resources required over random inputs (e.g., O(n log n) for quicksort).
• Worst-Case Complexity: Maximum resources required for the hardest input (most commonly analyzed, e.g., O(n²) for bubble sort).

Analysis helps select optimal algorithms for large datasets.

Rate of Growth in Algorithm Analysis

Rate of growth in algorithm analysis describes how an algorithm’s resource usage (time or space) increases as the input size (n) grows, focusing on the dominant term in the complexity function. It is analyzed using asymptotic notation like Big O, which ignores constants and lower-order terms to predict scalability for large n.

Key Aspects of Rate of Growth

• Asymptotic Notations:
  • Big O (O): Upper bound; worst-case growth rate. E.g., if time = 3n² + 2n + 1, the complexity is O(n²) as n² dominates.
  • Omega (Ω): Lower bound; best-case growth. E.g., Ω(n) means the algorithm takes at least linear time.
  • Theta (Θ): Tight bound; exact growth. E.g., Θ(n log n) for merge sort.
• Common Growth Rates (from slowest to fastest):
  • Constant: O(1) – Independent of n (e.g., array access).
  • Logarithmic: O(log n) – Halves the search space each step (e.g., binary search).
  • Linear: O(n) – Proportional to n (e.g., linear search).
  • Linearithmic: O(n log n) – Common in sorting (e.g., quicksort average).
  • Quadratic: O(n²) – Nested loops (e.g., bubble sort).
  • Exponential: O(2ⁿ) – Grows rapidly, impractical for large n (e.g., brute-force Traveling Salesperson Problem).

Why It Matters: For n=10⁶, O(n) might take seconds, but O(n²) could take years. Rate of growth helps compare algorithms; a lower rate is better for scalability. Empirical testing (profiling) complements theoretical analysis, but Big O assumes ideal hardware.

Array vs. Linked List Comparison

Arrays are faster for access but rigid; linked lists are flexible but slower for searching.

Linked Lists and Traversal Algorithm

A linked list is a linear data structure where elements (nodes) are stored non-contiguously in memory, each containing data and a pointer to the next node. It supports dynamic size and efficient insertions/deletions. A singly linked list has pointers only in the forward direction.

Algorithm to Traverse a Singly Linked List

This algorithm prints all elements in the list.

1. Start with a pointer current set to the head of the list.
2. While current is not NULL:
   • Output (print) the data in the current node.
   • Set current = current.next.
3. End when current becomes NULL.

Pseudocode for Traversal

TRAVERSE(head):
    current = head
    while current != NULL:
        print current.data
        current = current.next

Time complexity: O(n), Space complexity: O(1).

Deletion in a Singly Linked List

Deletion in a singly linked list involves updating pointers to remove a node and freeing its memory. We assume access to the head pointer.

• Deletion at the Beginning (Delete First Node)

  1. If the list is empty, return.
  2. Set temp = head.
  3. Set head = head.next.
  4. Free temp (the original head node).

  Time: O(1).

• Deletion at the End (Delete Last Node)

  1. If empty, return.
  2. If only one node exists, free head and set head = NULL.
  3. Else, traverse the list using two pointers (current and prev) until current reaches the last node. Alternatively, traverse to the second-last node (prev).
  4. Set prev.next = NULL.
  5. Free the last node.

  Time: O(n).

• Deletion at a Specific Position (k-th node, 1-based index)

  1. If k=1, use the beginning deletion algorithm.
  2. Traverse to the (k-2)th node (prev).
  3. If the position is invalid (prev or prev.next is NULL), return.
  4. Set toDelete = prev.next.
  5. Set prev.next = toDelete.next.
  6. Free toDelete.

  Time: O(n).

Arrays: Definition and Operations

An array is a fixed-size, homogeneous collection of elements stored in contiguous memory locations, accessed via indices (starting from 0). It allows O(1) random access but resizing is costly.

Array Insertion Algorithm

This algorithm inserts newElement at pos, shifting existing elements to the right. Assume the array has a maximum size max and current size n.

1. If n >= max, resize the array or report an overflow error.
2. For index i starting from n-1 down to pos: set arr[i+1] = arr[i]. (Shift elements right)
3. Set arr[pos] = newElement.
4. Increment n.

Pseudocode for Insertion

INSERT(arr, n, max, pos, element):
    if n >= max: resize or error
    for i = n-1 downto pos:
        arr[i+1] = arr[i]
    arr[pos] = element
    n = n + 1

Time complexity: O(n) worst-case (insertion at index 0). Space: O(1) extra space.

Linear Search Algorithm

Linear search sequentially scans the array from the start to find an element.

1. Start from index 0.
2. For each index i from 0 to n-1:
   • If arr[i] == key, return i (element found).
3. If the loop finishes without finding the element, return -1 (not found).

Pseudocode for Linear Search

LINEAR_SEARCH(arr, n, key):
    for i = 0 to n-1:
        if arr[i] == key:
            return i
    return -1  // not found

Time complexity: O(n) worst/average, O(1) best. Used when data is unsorted.

Stacks: LIFO Principle and Operations

A stack is a linear data structure following the LIFO (Last In, First Out) principle, analogous to a stack of plates. Elements are added and removed only from the top. Stacks are used in recursion, expression evaluation, and backtracking.

Stack Operations

• Push (Insertion)

  Adds an element to the top of the stack.

  • If the stack is full, an overflow error occurs.
  • Increment the top index; set stack[top] = element.
  • Time: O(1).

• Pop (Deletion)

  Removes and returns the top element.

  • If the stack is empty, an underflow error occurs.
  • item = stack[top]; decrement top; return item.
  • Time: O(1).

• Peek (or Top)

  Views the top element without removing it.

  • If the stack is empty, an error occurs.
  • Return stack[top].
  • Time: O(1).

Stacks can be implemented using arrays (fixed size) or linked lists (dynamic size).

Queues: FIFO Principle and Operations

A queue is a linear data structure following the FIFO (First In, First Out) principle, like a line at a ticket counter. Elements are added at the rear and removed from the front. Queues are used in scheduling and Breadth-First Search (BFS).

Queue Operations

• Enqueue (Insertion)

  Adds an element to the rear of the queue.

  • If the queue is full, an overflow error occurs.
  • If empty, set front = rear = 0.
  • Else, update rear (often using modulo arithmetic for circular queues: rear = (rear + 1) % size).
  • Set queue[rear] = item.
  • Time: O(1).

• Dequeue (Deletion)

  Removes and returns the element at the front of the queue.

  • If the queue is empty, an underflow error occurs.
  • item = queue[front]; update front (front = (front + 1) % size).
  • Return item.
  • Time: O(1).

Queues are typically implemented via circular arrays or linked lists. Variants include priority queues and deques.

Infix to Postfix Conversion

Postfix (Reverse Polish Notation) eliminates parentheses by placing operators after their operands. This conversion typically uses a stack to manage operator precedence.

• Expression a) A*(B+C/D)

  Infix: A*(B+C/D)

  Postfix: ABCD/+*

  Steps: A (output), * (push), B (output), C (output), / (push, higher precedence than +), D (output), pop / (output CD/), + (push), pop + (output BCD/+), pop * (output ABCD/+*).

• Expression b) ((A+B)*(C+D))/E

  Infix: ((A+B)*(C+D))/E

  Postfix: AB+CD+*E/

  Steps: Process operands and operators, using the stack to handle parentheses and precedence rules.

Postfix Conversion and Stack Evaluation

Convert and Evaluate: I = (6+2)*5-8/4

Infix to Postfix Conversion

Infix: (6+2)*5-8/4

Postfix: 6 2 + 5 * 8 4 / -

Evaluation Using Stack

The postfix expression 6 2 + 5 * 8 4 / - is evaluated using a stack:

1. Push 6.
2. Push 2.
3. +: Pop 2 and 6. Compute 6+2=8. Push 8. (Stack: [8])
4. Push 5. (Stack: [8, 5])
5. *: Pop 5 and 8. Compute 8*5=40. Push 40. (Stack: [40])
6. Push 8. (Stack: [40, 8])
7. Push 4. (Stack: [40, 8, 4])
8. /: Pop 4 and 8. Compute 8/4=2. Push 2. (Stack: [40, 2])
9. –: Pop 2 and 40. Compute 40-2=38. Push 38. (Stack: [38])

Result: I = 38. Time complexity: O(n) for both conversion and evaluation.

Recursion: Concepts and Factorial Example

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem, breaking it down until a simple case is reached. It relies on the call stack for execution. While elegant for problems involving trees or graphs, it carries the risk of stack overflow and often has higher space complexity than iterative solutions.

Defining Recursion: Base Case and Recursive Step

• Base Case: This is the simplest instance of the problem that returns a result directly without making further recursive calls. It is essential to stop infinite recursion. E.g., if n=0, return a fixed value.
• Recursive Step: This step assumes the function works correctly for smaller inputs (the inductive hypothesis) and uses that result to solve the current problem. It must ensure progress toward the base case.

Example: Sum of First n Natural Numbers

int sum(int n) {
    if (n == 0) {  // Base case
        return 0;
    } else {       // Recursive step
        return n + sum(n-1);
    }
}

For n=3: sum(3) = 3 + sum(2) = 3 + (2 + sum(1)) = 3 + 2 + (1 + sum(0)) = 3+2+1+0 = 6.

Factorial Calculation using Recursion

The Factorial of n (denoted n!) is defined as n × (n-1) × … × 1, with 0! = 1. Recursion defines this relationship as n! = n × (n-1)!.

Recursive Algorithm for Factorial

• Base Case: If n ≤ 1, return 1.
• Recursive Step: Return n * factorial(n-1).

FACTORIAL(n):
    if n <= 1:  // Base case
        return 1
    else:       // Recursive step
        return n * FACTORIAL(n-1)

Example: factorial(4) = 4 * factorial(3) = 4 * (3 * factorial(2)) = 4*3*(2*factorial(1)) = 4*3*2*1 = 24. The calls unwind from the base case back up to the initial call.