Data Structures
Learn how programs organize and store data efficiently using arrays, linked lists, trees, graphs, and more.
The Logic of Organization: Why Data Structures Matter
In computer programming, data is more than just raw numbers and characters; it represents relationships, structures, and systems. A data structure is a specialized format for organizing, managing, and storing data in a computer's memory so that it can be accessed, searched, and modified efficiently. Choosing the wrong data structure can cause a program to slow to a crawl, run out of memory, or become impossible to maintain. Conversely, the correct structure can turn a sluggish task into an instantaneous operation.
Data structures are closely linked with **algorithms**. While data structures provide the physical or logical organization of information, algorithms provide the step-by-step instructions to process that information. Together, they form the foundation of all software engineering.
Classifying Data Structures
Data structures are broadly divided into two main categories based on how their elements are organized and linked in memory:
- Linear Data Structures: Elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements. Examples include Arrays, Linked Lists, Stacks, and Queues.
- Non-Linear Data Structures: Elements are not arranged sequentially. Instead, elements are connected hierarchically or in complex networks, where an element can be linked to multiple other elements. Examples include Trees, Graphs, and Hash Tables.
Linear Data Structures: Sequential Layouts
1. Arrays
An **array** is the simplest and most common linear data structure. It stores elements of the same data type in contiguous (adjacent) blocks of physical memory. Because memory is contiguous, the computer can calculate the exact memory address of any element using its index number. This makes accessing an element by index extremely fast—an **O(1)** time complexity operation. However, because arrays have a fixed size declared at the start, inserting or deleting elements in the middle requires shifting all subsequent elements, making those operations slow—**O(n)** time complexity.
2. Linked Lists
A **linked list** is a dynamic linear structure where elements (called **nodes**) are not stored in contiguous memory. Instead, each node consists of two parts: the actual data, and a reference (pointer) to the next node in the list. This allows the list to grow or shrink dynamically without needing a large, unbroken block of memory. The trade-off is that you cannot access an element directly by index; you must traverse the list node-by-node starting from the head, resulting in an **O(n)** search time.
- Singly Linked List: Each node points only to the next node.
- Doubly Linked List: Each node points to both the next node and the previous node, allowing bidirectional traversal.
- Circular Linked List: The last node points back to the first node, forming a loop.
3. Stacks (LIFO)
A **stack** is a restricted linear structure that follows the **LIFO (Last In, First Out)** principle. Think of a stack of plates in a cafeteria: you can only add a plate to the top, and you can only take a plate off the top. Stacks have three core operations:
- Push: Adds an element to the top of the stack.
- Pop: Removes the top element from the stack.
- Peek (or Top): Views the top element without removing it.
Stacks are critical for managing function calls in programming (the **Call Stack**), executing Undo/Redo features, and parsing mathematical expressions.
4. Queues (FIFO)
A **queue** follows the **FIFO (First In, First Out)** principle, operating exactly like a line of customers at a store. The first customer to join the line is the first to be served. Queues use two primary operations:
- Enqueue: Adds an element to the tail (end) of the queue.
- Dequeue: Removes an element from the head (front) of the queue.
Queues are used in scenarios where resources are shared among multiple files or tasks, such as printer spooling, network packet buffering, and CPU process scheduling.
Non-Linear Data Structures: Hierarchies and Connections
1. Trees
A **tree** is a hierarchical data structure consisting of nodes connected by edges. It starts with a single **root node**, and every node can have zero or more **child nodes**. The most common type of tree is the **Binary Tree**, where each node can have a maximum of two children (left and right). A specialized variant is the **Binary Search Tree (BST)**, which maintains a strict sorting property: the value of the left child must be less than the parent, and the value of the right child must be greater. This sorting enables incredibly fast search, insertion, and deletion operations, typically requiring **O(log n)** time.
2. Hash Tables (Hash Maps)
A **hash table** is a structure that stores data in key-value pairs. It uses a mathematical formula called a **hash function** to translate a key (like a username) into a numeric index in an array. This allows the computer to find, insert, or delete the value associated with a key almost instantly, with an average time complexity of **O(1)**. If two different keys generate the same index, a **collision** occurs. Hash tables resolve collisions using methods like **chaining** (creating linked lists at each index) or **open addressing** (searching for the next empty slot).
3. Graphs
A **graph** is a network of nodes (called **vertices**) connected by pathways (called **edges**). Unlike trees, graphs do not have a root node or hierarchical parent-child relationships; nodes can connect in any pattern, including loops. Graphs are classified as:
- Directed vs. Undirected: Directed graphs have edges with arrows indicating one-way paths (like a Twitter follow relation). Undirected graphs have bidirectional edges (like a Facebook friendship).
- Weighted vs. Unweighted: Weighted graphs have values assigned to edges (like the mileage between two cities on a map).
Data Structure Complexity & Use Case Reference
The table below summarizes the average-case time complexities of core operations across different data structures, along with their ideal real-world applications:
| Data Structure | Access | Search | Insertion | Deletion | Ideal Real-World Use Case |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Storing a fixed list of lookup coordinates or months of the year. |
| Linked List | O(n) | O(n) | O(1) | O(1) | Implementing undo histories or photo playlist queues. |
| Stack | O(n) | O(n) | O(1) | O(1) | Browser back-button history navigation. |
| Queue | O(n) | O(n) | O(1) | O(1) | Print job scheduling queues, network packet routing. |
| BST (Balanced) | O(log n) | O(log n) | O(log n) | O(log n) | Autocompletion dictionaries, database indexes. |
| Hash Table | N/A | O(1) | O(1) | O(1) | Caching web pages, phonebooks, dictionary structures. |
Frequently Asked Questions
What is the difference between a static and a dynamic data structure?
Static data structures (like standard arrays) have a fixed size allocated in memory at compile time; their capacity cannot change during program execution. Dynamic data structures (like linked lists or dynamic arrays/vectors) can grow or shrink in size during runtime, allocating memory dynamically as elements are added or removed.
What is a hash collision, and how is it resolved?
A hash collision occurs when two distinct keys are fed into a hash function and produce the exact same array index. It is resolved using **Chaining** (each index of the hash table points to a linked list of entries sharing that index) or **Open Addressing** (the table searches neighboring indices using a probe sequence until an empty slot is found).
When would you use a linked list instead of an array?
You should use a linked list when you do not know how many elements your list will hold, when you expect to perform constant insertions and deletions at the head or tail, and when you do not need index-based random access. If you need immediate index access and know the collection size beforehand, an array is much more efficient.
Why is a Stack referred to as LIFO?
LIFO stands for Last In, First Out. It means that the last element added to the stack (via the push operation) is mathematically guaranteed to be the first element removed (via the pop operation). This operates like a stack of trays in a cafeteria.
What's Next?
Now that you know how data is structured in memory, the next step is to understand the logic used to manipulate these structures. Read our guide on Algorithms & Complexity to explore search, sorting, and Big O notation.