Sefism.Programming foundations: C#

Tauseef Fayyaz

Chapter 06

Data structures and Big-O

The handful of structures most code is built from, and how to reason about the time and memory a solution costs as the input grows.

Big-O notation

Also called time complexity, space complexity, asymptotic analysis, Big-O

What: Big-O describes how the running time or memory of an algorithm grows as the input size n grows, ignoring constants. Common classes, fastest first: O(1), O(log n), O(n), O(n log n), O(n²), O(2^n).
Why: It predicts whether code that is fine on 100 rows will still work on a million, and lets you compare solutions before writing them.
Example: Checking whether a list contains duplicates with two nested loops is O(n²). Adding each item to a set and checking membership first is O(n) time and O(n) extra space.

Watch out

Ignoring hidden loops: in on a list, indexOf, contains and string concatenation inside a loop are each O(n).

Arrays and amortised growth

Also called amortized, dynamic array, contiguous memory

What: An array stores items side by side in memory, so reading by index is O(1). A dynamic array doubles its capacity when full, so appending is O(1) on average (amortised) even though an occasional append copies everything.
Why: It is why appending to a list is cheap but inserting or deleting at the front is O(n): every later item has to shift.

Watch out

Inserting at the start of a list in a loop, turning an O(n) job into O(n²).

Linked lists

Also called singly linked list, doubly linked list, nodes

What: A chain of nodes where each node holds a value and a pointer to the next (and, in a doubly linked list, the previous) node.
Why: Inserting or removing next to a node you already hold is O(1), which suits queues and LRU caches. Finding an item by position is O(n).

Watch out

Choosing a linked list for general storage: poor cache locality makes it slower than a dynamic array for almost every everyday task.

Stacks

Also called LIFO, push, pop

What: A last-in, first-out collection: you push onto the top and pop from the top, both O(1).
Why: Stacks model undo history, matching brackets, depth-first search and the call stack itself.

static bool Balanced(string text)
{
  var pairs = new Dictionary<char, char>
    { [')'] = '(', [']'] = '[', ['}'] = '{' };
  var stack = new Stack<char>();
  foreach (var ch in text)
    if ("([{".Contains(ch)) stack.Push(ch);
    else if (pairs.TryGetValue(ch, out var open) &&
      (!stack.TryPop(out var top) || top != open)) return false;
  return stack.Count == 0;
}

Watch out

Popping from an empty stack without checking, which throws or returns nothing depending on the language.

Queues and deques

Also called FIFO, double-ended queue, enqueue, dequeue

What: A queue is first-in, first-out: add at the back, remove from the front, both O(1). A deque (double-ended queue) allows O(1) adds and removes at both ends.
Why: Queues model waiting lines, job processing and breadth-first search.

var queue = new Queue<string>();
queue.Enqueue("ada");
queue.Enqueue("grace");
string first = queue.Dequeue(); // "ada"

Watch out

Using a plain list as a queue: removing from the front shifts every element, O(n) per call (Python list.pop(0), JavaScript shift).

How hash tables work

Also called hashing, hash function, collisions, buckets, hash map

What: A hash table turns a key into a number with a hash function, uses it to pick a bucket in an array, and stores the entry there. Keys that land in the same bucket (collisions) are handled by chaining or probing.
Why: It is how dictionaries and sets get O(1) average lookups. The worst case is O(n) when many keys collide.

Watch out

Changing an object after using it as a key, or defining equality without a matching hash, so the entry can no longer be found.

Trees and binary search trees

Also called BST, binary tree, root, leaf

What: A tree is a hierarchy of nodes with one root, where each node has children and no cycles. In a binary search tree, left children are smaller and right children larger than their parent.
Why: Trees model folders, HTML and org charts. A balanced search tree keeps data sorted with O(log n) lookup, insert and delete; TreeMap and std::map are built this way.

Watch out

Inserting sorted data into a plain BST, which degrades it into a linked list with O(n) operations.

Graphs

Also called vertices, edges, adjacency list, BFS, DFS, breadth-first search, depth-first search

What: A graph is a set of nodes (vertices) connected by edges, which may have directions or weights. It is usually stored as an adjacency list: a map from each node to its neighbours.
Why: Road maps, social networks, dependencies and web links are graphs. Breadth-first search finds shortest paths in unweighted graphs; depth-first search explores and detects cycles.

Watch out

Traversing a graph without tracking visited nodes, which loops forever on the first cycle.

Recursion

Also called base case, recursive case

What: A function that calls itself on a smaller version of the problem, with a base case that stops the calls.
Why: Recursion fits naturally shaped problems: trees, nested folders, divide and conquer sorts and backtracking.

static long Factorial(int n)
{
  if (n <= 1) return 1;
  return n * Factorial(n - 1);
}

Watch out

A missing or unreachable base case, which recurses until the stack overflows.

Binary search

Also called bisection, O(log n) search

What: Searching a sorted array by checking the middle element and discarding the half that cannot contain the target, until it is found or the range is empty.
Why: It finds an item among a million in about 20 steps instead of up to a million, and the same halving idea solves many "smallest value that works" problems.

static int BinarySearch(int[] items, int target)
{
  int lo = 0, hi = items.Length - 1;
  while (lo <= hi)
  {
    int mid = lo + (hi - lo) / 2;
    if (items[mid] == target) return mid;
    if (items[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Watch out

Running it on unsorted data, or off-by-one errors in the loop bounds that skip the last element or loop forever.

Go deeper