Essential Data Structures and Algorithms Reference: DSA Core Concepts

Posted on Dec 22, 2025 in Computer Engineering

Lesson 2: Object-Oriented Programming and Linked Lists

OOP Fundamentals

  • Class: The blueprint for creating objects. Object: An instance of a class.
  • Attribute: A variable stored within an object. Method: A function defined within a class.
  • The self keyword refers to the object instance. __init__ is the constructor method.

OOP Example (Python)

class Car:
    def __init__(self, make, model, year):
        self.make = make; self.model = model; self.year = year
    def info(self):
        return f"{self.year} {self.make} {self.model}"

Linked Lists

  • A collection of nodes, where each node stores data and a pointer to the next node.
  • The Head is the first node. The last node’s next pointer is None.
  • Types: Singly (next pointer only), Doubly (next and previous pointers).

Node Class Structure

class Node:
    def __init__(self, data):
        self.data = data; self.next = None

Traversal Operation

cur = head
while cur: 
    print(cur.data)
    cur = cur.next

Insertion Operations

  • At Head: new.next = head → head = new
  • After a Node: new.next = prev.next → prev.next = new
  • At Tail: Traverse to the last node, then last.next = new

Deletion Operations

  • Head: head = head.next
  • Middle: prev.next = target.next
  • Last: Set the second-to-last node’s next pointer to None.

Performance Characteristics

  • Pros: O(1) insertion/deletion at the head or a known node.
  • Cons: O(n) search/traversal time complexity.

Lesson 3: Stacks and Queues

Stack (LIFO: Last-In, First-Out)

  • Operations: push, pop, top (peek), is_empty, size.
  • Common Uses: Function call stack, implementing undo functionality.
class Stack:
    def __init__(self): self.items = []
    def push(self, x): self.items.append(x)
    def pop(self): return self.items.pop() if self.items else None
  • Time Complexity: push and pop are O(1).

Queue (FIFO: First-In, First-Out)

  • Operations: enqueue, dequeue, is_empty, size.
  • Common Uses: Task scheduling, Breadth-First Search (BFS).
class Queue:
    def __init__(self): self.items = []
    def enqueue(self, x): self.items.append(x)
    def dequeue(self): return self.items.pop(0) if self.items else None
  • Performance Note: Using Python’s built-in list pop(0) for dequeue is O(n). Use collections.deque for O(1) performance.

Lesson 4: Recursion and Binary Search Trees (BST)

Recursion

  • A function calls itself repeatedly.
  • Requires a base case to stop execution.
  • Pros: Provides clean solutions for tree problems. Cons: Higher memory usage, slower execution, stack limit risk.

Binary Search Trees (BST)

  • Structure where Left Subtree < Node < Right Subtree. No duplicates allowed.
  • Performance depends on height (balanced: O(log n), skewed: O(n)).

BST Insertion

def insert(root, key):
    if not root: return BSTNode(key)
    if key < root.key: 
        root.left = insert(root.left, key)
    elif key > root.key: 
        root.right = insert(root.right, key)
    return root

BST Deletion Cases

  • Leaf Node: Simply remove the node.
  • Node with 1 Child: Replace the node with its child.
  • Node with 2 Children: Replace with the minimum node in the right subtree (in-order successor), then delete that successor node.

BST Traversal Methods

  • In-order (LNR): Visits nodes in sorted order.
  • Pre-order (NLR): Useful for copying the tree structure.
  • Post-order (LRN): Useful for deleting the tree bottom-up.

Lesson 5: Hashing and Sorting Algorithms

Hash Tables (Dictionaries)

  • Map a key to a value via a hash function; average O(1) operations.
  • Keys must be immutable.
  • Core Operations: Access (d[key]), Assignment (d[key] = v), Deletion (del d[key]).

Sorting Algorithms

Insertion Sort

  • Builds a sorted left side by shifting elements.
  • Time Complexity: O(n²). Good for small or nearly sorted lists.

Selection Sort

  • Repeatedly finds the minimum element and swaps it to the front.
  • Time Complexity: O(n²). Not a stable sorting algorithm.

Merge Sort

  • Splits the list, sorts recursively, then merges the results.
  • Time Complexity: O(n log n). Requires extra space, but is stable.

Quicksort

  • Selects a pivot, partitions the array, and recurses.
  • Average Time Complexity: O(n log n). Worst-case complexity is O(n²).

Lesson 6: Graphs, Search Algorithms, and Dijkstra’s

Graph Fundamentals

  • Composed of Nodes (Vertices) and Edges.
  • Types: Directed, Undirected, Weighted.
  • Representations:
    • Adjacency List: Space-efficient.
    • Adjacency Matrix: O(V²) space complexity.

Depth-First Search (DFS)

  • Explores deeply along branches using a stack or recursion.
  • Uses: Path finding, cycle detection.
def dfs(g, v, vis=set()):
    if v in vis: return
    vis.add(v)
    for n in g.adj[v]: dfs(g, n, vis)

Breadth-First Search (BFS)

  • Explores level by level using a queue.
  • Uses: Finding the shortest path in unweighted graphs.
from collections import deque
def bfs(g, start):
    vis = {start}; q = deque([start])
    while q:
        u = q.popleft()
        for n in g.adj[u]:
            if n not in vis:
                vis.add(n); q.append(n)

Dijkstra’s Algorithm (Weighted Shortest Path)

  • A greedy algorithm: picks the smallest distance node, then relaxes edges. Requires non-negative weights.
  • Time Complexity (with heap): O((V + E) log V).
import heapq
def dijkstra(g, src):
    dist = {v:inf for v in g.adj}; dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]: continue
        for v, w in g.adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w; heapq.heappush(pq, (dist[v], v))

If you want, I can shrink font and remove spacing even more for a printable 1-page version.