Overview of Common Data Structures and Algorithms

Recently I decided to practice algorithms and realized I needed to refresh my data‑structure fundamentals, so this article revisits common data structures and related algorithms.

Algorithms play a crucial role in computer science; a well‑designed algorithm improves execution efficiency, reduces memory usage, and enhances readability and maintainability. Because algorithms rely on data structures, mastering basic structures is essential before tackling algorithmic problems.

Array

An array is a linear data structure that stores elements of the same type in contiguous memory locations, accessed via a unique index. It is easy to understand and implement, but insertions and deletions can be costly because they may require shifting many elements.

Linked List

A linked list is a non‑linear structure composed of nodes, each containing data and a pointer to the next node. It simplifies insertion and deletion by adjusting pointers, though random access is slower because traversal must start from the head.

Dynamic memory allocation avoids waste and overflow.

Insertion and deletion are convenient, requiring only pointer updates.

Insertion can achieve O(1) complexity, but searching for a specific element costs O(n).

Stack and Queue

A stack is a LIFO (last‑in‑first‑out) structure supporting push, pop, and peek operations, useful for function calls, puzzle solving, etc. Variants include sequential stack, linked stack, and recursive stack.

A queue is a FIFO (first‑in‑first‑out) linear structure where insertion occurs at the rear and deletion at the front. Variants include sequential queue, linked queue, and circular queue.

Hash Table

Hash tables provide O(1) average‑case insertion and lookup by mapping keys to array indices via a hash function. Common types include array hash tables, chained hash tables, open‑addressing hash tables, binary hash tables, compressed hash tables, and bitmap hash tables.

Tree

Trees are non‑linear structures consisting of a root, internal nodes, and leaves. Common forms are binary trees, AVL trees, red‑black trees, and other balanced or unbalanced variants, often used to represent hierarchical relationships.

Sorting Algorithms

Sorting arranges unordered data elements into a defined order. Examples of unstable sorts: quick sort, shell sort, heap sort, selection sort. Stable sorts include radix sort, bubble sort, insertion sort, binary insertion sort, and merge sort.

Search Algorithms

Search algorithms systematically explore a problem’s solution space, either partially or completely, to find a solution. Types include enumeration, depth‑first search, breadth‑first search, A*, backtracking, Monte Carlo tree search, and hash‑based methods.

Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step, aiming for a globally optimal solution in certain problem domains. Typical examples are the 0/1 knapsack problem, knight’s tour, and equal‑distribution card games.

Divide‑and‑Conquer

This strategy splits a problem of size N into K smaller independent sub‑problems, solves each recursively, and combines the results. Classic examples are merge sort, heap sort, quick sort, counterfeit‑coin detection, and chessboard covering.

Dynamic Programming

Dynamic programming solves optimization problems by breaking them into overlapping sub‑problems and building up solutions. It includes linear DP (e.g., missile interception), regional DP (e.g., stone merging), tree DP (e.g., triangle number problems), and knapsack DP (e.g., 0/1 knapsack, complete knapsack).

Useful algorithm visualization links:

Algorithm Visualizer

Visualgo

Algorithm Visualizer (English)

GitHub – Algorithm Resources