Core Data Structures You Should Know

Data structures are organized ways to store and manage data so you can use it efficiently. The core ones you should know are arrays, linked lists, stacks, queues, hash tables, trees, and graphs. An array stores elements in contiguous memory, allowing fast access by index. A linked list stores elements in nodes that point to each other, allowing fast insertion and deletion. A stack follows last-in, first-out (LIFO), while a queue follows first-in, first-out (FIFO). A hash table maps keys to values using a hash function. A tree is a hierarchical structure with a root and child nodes; a binary search tree keeps left children smaller and right children larger. A graph is a set of vertices connected by edges, which can be directed or undirected. Each structure has trade-offs in time and space complexity for operations like access, search, insertion, and deletion. Understanding these trade-offs helps you choose the right tool for a given problem.

Choosing the right data structure can make the difference between a program that runs in milliseconds and one that takes minutes. For example, searching an unsorted array takes O(n) time, but searching a balanced binary search tree takes O(log n). Inserting into the middle of an array is O(n) because elements must shift, while inserting into a linked list at a known position is O(1). Hash tables provide average O(1) lookup, insertion, and deletion, but degrade to O(n) in the worst case if many keys collide. Stacks and queues are essential for managing order of operations, such as function calls, undo mechanisms, and breadth-first search. Trees power file systems, databases, and compilers. Graphs model networks, social connections, and routing. By understanding these structures, you can write code that scales, avoid performance bottlenecks, and reason about algorithmic complexity. Most technical interviews and real-world systems rely on this knowledge.

Arrays allocate a fixed-size block of memory. The address of element i is base + i * element_size, so access is O(1). Insertion or deletion at an arbitrary position requires shifting elements, costing O(n). Dynamic arrays (like Python's list or C++'s vector) resize by allocating a larger block and copying elements, giving amortized O(1) append. Linked lists consist of nodes with a value and one or more pointers. Singly linked lists have a next pointer; doubly linked lists also have a prev pointer. Access is O(n) because you must traverse from the head. Insertion and deletion are O(1) if you have a reference to the node. Stacks and queues can be implemented with arrays or linked lists. A stack uses push and pop at one end; a queue uses enqueue at the rear and dequeue at the front. Hash tables use an array of buckets. A hash function converts a key to an index. Collisions are resolved by chaining (linked lists) or open addressing (probing). Trees store nodes with parent-child relationships. Binary search trees maintain order; balanced variants like AVL or red-black trees keep height O(log n). Graphs are represented as adjacency lists or adjacency matrices.

Suppose you need to check whether a string has balanced parentheses. A stack is ideal because the most recent opening bracket must match the next closing bracket. Here is a Python implementation:

def is_balanced(s):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in '([{':
            stack.append(char)
        elif char in ')]}':
            if not stack or stack.pop() != pairs[char]:
                return False
    return len(stack) == 0

This function iterates through each character once, so time complexity is O(n). Space complexity is O(n) in the worst case (all opening brackets). The stack stores opening brackets; when a closing bracket appears, it must match the top of the stack. If the stack is empty or the top does not match, the string is unbalanced. At the end, the stack must be empty. This example shows how a simple data structure solves a common parsing problem elegantly.

A frequent mistake is using the wrong structure for the access pattern. For example, using a linked list when you need fast random access, or using an array when you need frequent insertions at the front. Another error is forgetting that hash table iteration order is not guaranteed in many languages (e.g., Python's dict preserves insertion order since 3.7, but that is not universal). Assuming O(1) for hash table operations in all cases is wrong; worst-case is O(n) due to collisions. In trees, forgetting to balance can lead to O(n) height and degraded performance. With stacks, popping from an empty stack causes an error; always check for emptiness. With queues, using a list and popping from the front is O(n) in Python; use collections.deque instead. In graphs, confusing directed and undirected edges can lead to incorrect algorithms. Also, mixing up BFS and DFS: BFS uses a queue, DFS uses a stack (or recursion). Finally, not considering memory overhead: linked lists and trees have extra pointer storage, while arrays are compact.

Use arrays when you need fast random access and know the size in advance, or when you mostly append and iterate. Use linked lists when you need frequent insertions and deletions at arbitrary positions and do not need random access. Use stacks for last-in, first-out scenarios: function call management, undo/redo, expression evaluation, and depth-first search. Use queues for first-in, first-out scenarios: task scheduling, breadth-first search, and buffering. Use hash tables when you need fast key-based lookup, insertion, and deletion, such as dictionaries, caches, and sets. Use trees when data is hierarchical or when you need ordered operations, such as binary search trees for sorted data, heaps for priority queues, and tries for prefix matching. Use graphs when modeling relationships between entities, such as social networks, road maps, and dependency graphs. Always consider the operations you need most frequently and their required time complexity. In practice, many languages provide built-in implementations: Python's list, dict, set, and collections.deque; Java's ArrayList, HashMap, HashSet, and LinkedList; C++'s vector, unordered_map, set, and list.

Which data structure should I learn first? Start with arrays and hash tables because they are the most commonly used in everyday programming. Then learn stacks and queues, followed by trees and graphs. Do I need to implement them from scratch? For learning, implementing a linked list, stack, queue, and hash table once is valuable. In real projects, use built-in libraries unless you have a specific reason. How do I choose between a hash table and a tree? If you only need key-based lookup and do not care about order, a hash table is usually faster (average O(1)). If you need ordered traversal, range queries, or predictable worst-case performance, a balanced tree is better (O(log n)). What about sets? A set is a collection of unique elements, often implemented with a hash table or tree. Use a hash set for fast membership tests; use a tree set when you need sorted order. Remember that no single structure is best for all cases; analyze your operations and pick accordingly.