04

Essential Data Structures

Chapter 4 • Intermediate

150 min

Essential Data Structures

Overview

Data structures are ways of organizing and storing data to enable efficient operations. Choosing the right data structure is crucial for algorithm efficiency.

Arrays

Properties

  • Access: O(1) - direct indexing
  • Search: O(n) - linear search
  • Insertion: O(n) - shift elements
  • Deletion: O(n) - shift elements
  • Space: O(n)

Use Cases

  • When you need random access
  • When size is known and fixed
  • When memory efficiency matters
python.js
class Array:
    def __init__(self, size):
        self.data = [None] * size
        self.length = 0
    
    def get(self, index):
        if 0 <= index < self.length:
            return self.data[index]
        raise IndexError("Index out of range")
    
    def set(self, index, value):
        if 0 <= index < len(self.data):
            self.data[index] = value
            if index >= self.length:
                self.length = index + 1
        else:
            raise IndexError("Index out of range")

Linked Lists

Properties

  • Access: O(n) - must traverse
  • Search: O(n)
  • Insertion: O(1) at head, O(n) at position
  • Deletion: O(1) at head, O(n) at position
  • Space: O(n)

Use Cases

  • When size is unknown
  • When frequent insertions/deletions at beginning
  • When memory is fragmented
python.js
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_head(self, val):
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node
    
    def delete_at_head(self):
        if self.head:
            self.head = self.head.next

Stacks

Properties

  • Push: O(1)
  • Pop: O(1)
  • Peek: O(1)
  • Space: O(n)

Use Cases

  • Function call management
  • Expression evaluation
  • Undo/redo operations
  • Backtracking algorithms
python.js
class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        self.items.append(item)
    
    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items.pop()
    
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self.items[-1]
    
    def is_empty(self):
        return len(self.items) == 0

Queues

Properties

  • Enqueue: O(1)
  • Dequeue: O(1)
  • Front: O(1)
  • Space: O(n)

Use Cases

  • BFS traversal
  • Task scheduling
  • Request handling
  • Print queue management
python.js
from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        self.items.append(item)
    
    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items.popleft()
    
    def front(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self.items[0]
    
    def is_empty(self):
        return len(self.items) == 0

Trees

Binary Tree

python.js
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Binary Search Tree (BST)

Properties:

  • Left subtree < root < right subtree
  • Search: O(log n) average, O(n) worst
  • Insert: O(log n) average, O(n) worst
  • Delete: O(log n) average, O(n) worst

Balanced Trees (AVL, Red-Black)

  • Maintain height balance
  • All operations: O(log n) guaranteed

Hash Tables

Properties

  • Insert: O(1) average, O(n) worst
  • Search: O(1) average, O(n) worst
  • Delete: O(1) average, O(n) worst
  • Space: O(n)

Use Cases

  • Fast lookups
  • Counting frequencies
  • Caching
  • Set operations
python.js
class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def insert(self, key, value):
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                pair[1] = value
                return
        self.table[index].append([key, value])
    
    def get(self, key):
        index = self._hash(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        raise KeyError("Key not found")

Choosing the Right Data Structure

OperationArrayLinked ListStackQueueBSTHash Table
Access by indexO(1)O(n)----
SearchO(n)O(n)O(n)O(n)O(log n)O(1)
Insert at beginningO(n)O(1)O(1)O(1)O(log n)O(1)
DeleteO(n)O(n)O(1)O(1)O(log n)O(1)

Practice Problems

  1. Implement a stack using two queues
  2. Implement a queue using two stacks
  3. Design a hash table with collision handling
  4. Implement BST with insert, delete, search
  5. Convert array to balanced BST
Previous
Growth Rates and Asymptotic Analysis
Next
Priority Queues and Heaps

Related Tutorials