Data Structures & Algorithms

Overview: Data Structures and Algorithms at a Glance

An abstract data type defines what operations are available, while a data structure defines how they are implemented. A stack, for example, is defined by push, pop and peek; it can be implemented with an array or a linked list, and the implementation changes the cost of overflow handling but not the last-in first-out rule. This distinction matters in examinations because a question may ask about the abstract behaviour, such as the output order of a queue, or about the implementation cost, such as the cost of inserting at the front of an array.

Two costs dominate analysis: time and space. Time is usually counted in elementary operations as a function of input size n, and space counts extra memory beyond the input. An algorithm that is fast but needs a second copy of the data may be rejected where memory is tight, and an in-place sort is therefore valued even when its worst case is worse than a method that needs auxiliary storage. Always check whether a stated complexity is best, average or worst case, and whether it counts comparisons, swaps, or total steps, because the same algorithm can carry different labels under different counting rules.

Arrays, stacks, queues, linked lists

An array stores elements in contiguous memory, so the address of element i is base plus i times element size, and access by index takes constant time. That strength is also its weakness: inserting or deleting in the middle shifts all later elements, which costs linear time, and a fixed-size array can overflow or waste space. A dynamic array grows by allocating a larger block and copying elements, so individual insertions are occasionally expensive but the amortised cost of appending is constant, because expensive doublings are rare. Searching an unsorted array is linear, while a sorted array supports binary search.

A stack allows insertion and deletion only at one end, called the top, giving last-in first-out order. Push adds an element, pop removes the top element, and peek reads it without removing it. Stack overflow occurs when pushing onto a full bounded stack, and underflow when popping from an empty one. Applications follow directly from the order: the call stack saves return addresses and local state, undo operations reverse the most recent action first, and expression evaluation uses stacks to handle operators and parentheses. To evaluate a postfix expression, scan left to right, push operands, and on meeting an operator pop two operands, apply the operator, and push the result. Infix to postfix conversion uses an operator stack together with precedence and associativity rules, with parentheses forcing subexpressions to be completed first.

A queue allows insertion at the rear and deletion at the front, giving first-in first-out order. Enqueue adds at the rear and dequeue removes from the front. A simple array queue wastes the space left by dequeued elements, so a circular queue wraps the rear and front indices around with modulo arithmetic: the next position is computed as (index plus 1) modulo capacity. A circular queue is full when the next rear position equals the front, and empty when front equals rear under the chosen convention, so one slot is often sacrificed or a separate count is kept to distinguish the two states. A deque allows insertion and deletion at both ends, and a priority queue orders removal by priority rather than arrival time, which is normally implemented with a heap. Queues appear in process scheduling, print spooling, buffering between producers and consumers, and breadth-first traversal.

A singly linked list is a chain of nodes, each holding data and a pointer to the next node, with the last node pointing to null. Insertion or deletion at a known node takes constant time once the node is located, because only pointers change, but reaching position i requires walking from the head, which costs linear time. A doubly linked list adds a previous pointer to each node, so deletion of a known node and backward traversal are easy, at the cost of extra memory and more pointer updates. A circular linked list links the last node back to the first, which suits round-robin scheduling. The classic examination traps are losing the rest of the list by overwriting a pointer before saving it, forgetting to update the head on insertion or deletion at the front, and creating a cycle by linking a node to itself.

Trees, heaps, graphs & traversal

A tree is a connected acyclic graph with a root, where every node except the root has exactly one parent and nodes with no children are leaves. The height of a tree is the number of edges on the longest root-to-leaf path, and a binary tree allows at most two children per node, conventionally called left and right. A full binary tree has either zero or two children at every node, a complete binary tree fills levels left to right except possibly the last, and a perfect binary tree has all leaves at the same depth. Traversals define visit order: preorder visits node, left subtree, right subtree; inorder visits left subtree, node, right subtree; postorder visits left subtree, right subtree, node; level order visits level by level using a queue. Inorder traversal of a binary search tree yields keys in sorted order, which is a favourite examination fact.

A binary search tree maintains the invariant that every key in the left subtree is smaller than the node key and every key in the right subtree is larger. Search, insertion and deletion walk down comparing keys, so each costs time proportional to height. In the worst case a degenerate tree that is really a chain costs linear time, while a balanced tree costs logarithmic time. Deleting a leaf removes it directly, deleting a node with one child replaces it by that child, and deleting a node with two children replaces it by its inorder successor or predecessor and then deletes that successor or predecessor. An AVL tree restores balance after insertion or deletion by maintaining a balance factor, the height of the left subtree minus the height of the right subtree, in the range minus one to plus one at every node. When the factor leaves this range, one of four rotations applies: left-left is fixed by a single right rotation, right-right by a single left rotation, left-right by a left rotation on the child followed by a right rotation on the node, and right-left by the mirror image. Rotations preserve the inorder sequence while changing heights, which is why they preserve the search-tree property.

A heap is a complete binary tree with the heap property: in a max-heap every parent is at least as large as its children, so the maximum sits at the root, and in a min-heap every parent is at most as large as its children. Heaps are stored in arrays without pointers: for a node at index i using zero-based indexing, its children are at 2i plus 1 and 2i plus 2, and its parent is at floor of (i minus 1) divided by 2. Insertion places the new element at the end and bubbles it up while it violates the heap property, and deletion of the root replaces the root with the last element and bubbles it down, both in logarithmic time. Building a heap by repeated insertion costs n log n, but the bottom-up heapify method costs linear time because most nodes are near the leaves and move only a short distance. Heap sort repeatedly extracts the root to obtain sorted order. Huffman coding builds an optimal prefix code by repeatedly merging the two least frequent symbols into a new node whose frequency is their sum, so frequent symbols get short codes and no code is a prefix of another, which guarantees unambiguous decoding.

A graph consists of vertices and edges, which may be directed or undirected and may carry weights. It is stored as an adjacency matrix, which answers edge existence in constant time but uses quadratic space, or as adjacency lists, which use space proportional to vertices plus edges and suit sparse graphs. Breadth-first search uses a queue, visits vertices in increasing distance from the source in an unweighted graph, and naturally finds shortest paths in edges. Depth-first search uses a stack or recursion, explores as far as possible along each branch before backtracking, and is the basis for cycle detection, connected components and topological sorting. Dijkstra algorithm finds shortest paths from a source when all edge weights are non-negative: it maintains tentative distances, repeatedly finalises the unfinalised vertex with the smallest tentative distance, and relaxes its outgoing edges. It fails with negative weights because a finalised vertex could later be improved through a negative edge. A minimum spanning tree connects all vertices with minimum total weight: Prim algorithm grows one tree by repeatedly adding the cheapest edge to a vertex outside the tree, while Kruskal sorts all edges and adds them unless they form a cycle, using a disjoint-set structure. Topological sort orders vertices of a directed acyclic graph so that every edge goes from earlier to later, and it is impossible when a cycle exists.

Sorting, searching & complexity

Sorting rearranges elements into order, and the methods differ in cost, extra space and stability. A stable sort preserves the relative order of equal elements, which matters when records are sorted by one key and ties should keep an earlier order. Bubble sort repeatedly compares adjacent pairs and swaps out-of-order pairs, so the largest element bubbles to the end each pass; it costs quadratic time in the worst and average cases and linear time on an already sorted array if an early-exit flag is used. Selection sort repeatedly selects the minimum of the unsorted part and swaps it into place, always costing quadratic comparisons but only linear swaps. Insertion sort inserts each element into its correct place among the earlier sorted elements, costing quadratic time in the worst case but linear time on nearly sorted data, which makes it the method of choice for small or nearly sorted inputs.

Merge sort divides the array into halves, sorts each half recursively, and merges the sorted halves in linear time, giving n log n time in all cases at the cost of linear extra space. Quick sort chooses a pivot, partitions the array so smaller elements go left and larger elements go right, and recurses on both sides; it is fast in practice and in-place, with average n log n time, but degrades to quadratic time when the pivot is repeatedly the smallest or largest element, as on already sorted data with a first-element pivot. Choosing a median-of-three pivot or random pivot reduces that risk. Heap sort builds a heap and repeatedly extracts the root, giving n log n time in all cases with constant extra space, but it is not stable.

Searching mirrors the same trade-offs. Linear search scans in order and costs linear time, but works on unsorted data. Binary search repeatedly halves a sorted interval: compare the middle element, discard the half that cannot contain the target, and repeat, giving logarithmic time. It requires random access and sorted data. A hash table maps keys to bucket indices with a hash function and aims for constant average lookup. Collisions are handled by chaining, where each bucket holds a list of entries, or by open addressing, where probing searches for another slot using linear probing, quadratic probing or double hashing. The load factor is the number of stored elements divided by the number of buckets, and performance degrades as it grows, so tables rehash into a larger table when the load factor passes a threshold. Clustering is the tendency of linear probing to form long runs of occupied slots.

Asymptotic notation describes growth for large n, ignoring constant factors and lower-order terms. Big-O gives an upper bound, Omega gives a lower bound, and Theta gives a tight bound when upper and lower bounds match. A recurrence describes a recursive algorithm in terms of smaller inputs, and the master theorem solves recurrences of the form T of n equals a times T of n divided by b plus f of n, where a subproblems of size n divided by b are solved and f of n is the divide and combine cost. If f of n grows more slowly than n to the power log base b of a, the subproblems dominate; if it grows at the same rate, an extra log factor appears; if it grows faster and satisfies a regularity condition, the divide and combine cost dominates. Divide and conquer splits, solves and combines, as in merge sort and quick sort. Dynamic programming solves overlapping subproblems once and reuses results: the Fibonacci recurrence recomputes the same values exponentially often without memoisation, but becomes linear with a table; the zero-one knapsack and longest common subsequence problems build tables where each cell depends on smaller subproblems, trading space for the avoidance of repeated work.

Stack versus queue

Sorting algorithm comparison

BFS versus DFS

Collision resolution methods