Data Structures Overview
Data structures can be divided into two broad families: primitive and non-primitive. Primitive data structures are the basic types built into programming l...
A Map of the Major Data Structures
Data structures can be divided into two broad families: primitive and non-primitive. Primitive data structures are the basic types built into programming languages: integers, floating-point numbers, characters, and booleans. Non-primitive structures are built on top of these and are the main focus of DSA study.
Non-primitive structures split further into linear and non-linear categories. Linear structures arrange data sequentially, where each element has at most one predecessor and one successor. Arrays, linked lists, stacks, and queues all fall into this category. Non-linear structures allow elements to connect to multiple others, forming hierarchies or networks. Trees and graphs are the primary non-linear structures.
Arrays store elements in contiguous memory locations and support O(1) random access by index, but inserting or deleting elements in the middle costs O(n) because subsequent elements must shift. Linked lists scatter elements across memory and link them with pointers, allowing O(1) insertion and deletion at a known node but requiring O(n) traversal to reach a specific position.
Stacks enforce a last-in, first-out discipline. The most recently added element is the first to be removed. Stacks model function call management, undo operations in editors, and expression evaluation. Queues enforce first-in, first-out order and model waiting lines, task scheduling, and breadth-first traversal.
Hash tables store key-value pairs and use a hash function to map keys to array indices, achieving O(1) average-case lookup, insertion, and deletion. Collisions, where two keys hash to the same index, require resolution strategies like chaining or open addressing.
Trees are hierarchical structures with a root node and child nodes forming a parent-child relationship. Binary search trees allow O(log n) search in the average case. Heaps support O(log n) insertion and O(1) access to the minimum or maximum element. Graphs generalize trees by allowing cycles and arbitrary connections, modeling networks, maps, and social relationships.
Worked example: choosing between an array and a linked list depends on the workload. If your application reads data far more than it writes, an array is faster due to cache locality and direct indexing. If insertions and deletions at arbitrary positions dominate, a linked list reduces the cost of those operations.
Interview tip: memorize the time complexity of the core operations (access, search, insert, delete) for each major data structure. Interviewers frequently ask you to justify your choice of data structure.