Data Structures

Learning Objectives

  • Define data structures and their role in algorithm efficiency.
  • Distinguish between linear and non-linear data structures.
  • Understand the characteristics, advantages, and Big O time complexity of arrays and linked lists.
  • Explain the LIFO and FIFO principles of Stacks and Queues.
  • Explore hierarchical organization using Trees and Binary Search Trees.
  • Understand graph representations (Adjacency Matrix/List) and traversals.
  • Learn how Hash Tables map keys to values and handle collisions.

A comprehensive overview of organizing and storing data efficiently using Arrays, Linked Lists, Stacks, Queues, Trees, Graphs, and Hash Tables.

Data Structure

A data structure is a representation for organizing values and supporting operations on them. Each choice has trade-offs in operation cost, memory use, and implementation complexity; the best fit depends on the operations and workload.

Abstract Data Type

An abstract data type (ADT) specifies the values and operations a user can rely on without prescribing the underlying representation. For example, a stack's push and pop rules can be implemented with an array or linked nodes.

1. Introduction to Data Organization

Different tasks require fundamentally different ways to store data. If you need to search a dictionary, you want it alphabetized (sorted). If you need to track the history of web pages you visited, you want to easily go back to the most recent one (a Stack).

Categories of Data Structures

  • Linear Data Structures: Elements have a sequence order, so each position has a predecessor and successor except at the ends. The implementation may provide those relationships through indices, links, or restricted ADT operations (e.g., arrays, linked lists, stacks, queues).

  • Non-Linear Data Structures: Relationships are not limited to one sequence; elements may form a hierarchy or a network with multiple connections (e.g., trees and graphs).

2. Time Complexity and Big O Notation Context

Asymptotic analysis describes how an operation's resource use grows with input size nn under stated assumptions. Big O is an upper-bound notation; it does not by itself mean worst case or report elapsed seconds. Name the operation, implementation, and case being analyzed.

Common Time Complexities

  • O(1) upper bound: The number of primitive steps is bounded independently of nn for the stated operation (e.g., indexed access in a conventional array representation). It does not mean the same measured time on every machine or input.
  • O(log n) upper bound: The work grows with the logarithm of nn when each step reduces the remaining search region by a constant factor (e.g., searching a height-balanced binary search tree).
  • O(n) upper bound: The work can grow proportionally to nn (e.g., scanning an unsorted sequence or following a linked list to a position).

3. Linear Data Structures

The most fundamental ways to store collections of data in a sequential manner.

3.1 Arrays

An array is an indexed collection. In a conventional low-level array representation, fixed-width elements occupy adjacent storage; a language-level array or list may expose indexed behavior while using an implementation-specific representation.

Array Characteristics

  • Fixed or resizable: A built-in array in C or Java has a fixed length after creation. Dynamic-array containers such as C++ std::vector, Java ArrayList, Python list, and JavaScript Array support resizing through language or library operations; their detailed storage behavior differs.

  • Indexed access: A conventional array representation supports indexed access in O(1) time. For a zero-based contiguous array of fixed-width elements, the address of element ii is base + i × elementWidth. This address model does not describe the physical layout of every language-level array.

  • Insertion and deletion: In an array-based list, inserting or removing near the beginning or middle generally shifts later elements and takes O(n) time. Appending to a dynamic array is often amortized O(1) under geometric capacity growth, although a particular append can trigger a resize and cost O(n).

Use the simulation to observe end insertion and removal in an abstract dynamic array, with zero-based positions and a schematic slot layout.

Array Operations

Arrays store elements in contiguous memory locations. Notice how elements are accessed via a zero-based index.

Memory Representation (Array)

[0]
10
0x3E8
[1]
20
0x3EC
[2]
30
0x3F0
[3]
null
0x3F4
[4]
null
0x3F8
[5]
null
0x3FC
[6]
null
0x400
[7]
null
0x404
let arr = [10, 20, 30];

Interpreting the array simulation

The displayed addresses are illustrative slot labels, not measured JavaScript memory addresses. JavaScript specifies indexed array behavior and resizable length, while a runtime's physical storage layout is implementation-dependent.

3.2 Linked Lists

A linked list is a sequence of nodes. A singly linked node stores an element and a link or reference to its successor. Nodes need not occupy adjacent storage; their physical placement is chosen by the runtime or allocator.

Linked List Characteristics

  • Dynamic size: Nodes can be allocated or released as the collection changes, subject to available resources. Links and per-node allocation add memory overhead.

  • Insertion and deletion: Once the required predecessor or link position is known, changing a singly linked list's links takes O(1) time. Finding that position can take O(n); removing a node from a singly linked list normally requires its predecessor.

  • Sequential access: To reach a position by index, follow links from the head; this takes O(n) time in the worst case rather than direct indexed access.

  • Types: Singly Linked (points to next), Doubly Linked (points to next and previous), Circular Linked (last node points back to the first).

Insert after a known node by changing two links

When the predecessor is already known, insertion rewires the predecessor and new node links in constant time. Locating the insertion position is a separate traversal cost.

Before insertion, A links to C. After allocating B, A links to B and B links to C; later nodes do not move.

4. Abstract Data Types (ADTs): Stacks and Queues

ADTs define how data should be accessed logically (the rules of interaction), but not exactly how it's stored physically in memory. Stacks and Queues can be implemented using either Arrays or Linked Lists under the hood.

4.1 Stacks (LIFO)

A Stack follows the Last-In, First-Out (LIFO) principle. Imagine a stack of physical plates: you add plates to the top, and you must remove plates from the top.

Stack Operations

  • Push: Add an element to the top of the stack.
  • Pop: Remove and return the top element from the stack.
  • Peek (Top): View the top element without removing it.

Real-World Stack Uses

The 'Undo' feature in text editors. Browser history (Back button). The Call Stack used by the CPU to manage function calls, local variables, and recursion.

4.2 Queues (FIFO)

A Queue follows the First-In, First-Out (FIFO) principle. Imagine a line of people at a grocery store: the first person to get in line is the first person served.

Queue Operations

  • Enqueue: Add an element to the back (rear) of the queue.
  • Dequeue: Remove and return an element from the front (head) of the queue.
  • Priority Queue: A variation where elements are dequeued based on an assigned priority rather than strictly arrival order.

Real-World Queue Uses

Printer job scheduling, request handling, and network buffers are queue-like uses. Operating systems may use several scheduling policies; a priority or time-sharing scheduler is not necessarily a simple FIFO queue.

The same arrivals leave in different orders

A stack adds and removes at its top; a queue adds at the rear and removes from the front. The structure's access rule determines removal order.

After A, B, and C are added, a stack pops C first under LIFO, while a queue dequeues A first under FIFO.

5. Non-Linear Data Structures

Used when data naturally forms a hierarchy or complex, multi-directional relationships.

5.1 Trees

A Tree is a hierarchical data structure consisting of nodes connected by edges. The topmost node is the Root. Nodes with no children are called Leaves.

Important Tree Types

  • Binary Tree: Each node can have a maximum of two children (typically designated as Left and Right).

  • Binary Search Tree (BST): For unique keys, each node's left subtree contains smaller keys and its right subtree contains larger keys. Search, insertion, and deletion take O(h), where hh is tree height: O(log n) when balanced and O(n) when the tree is skewed. Duplicate-key handling requires a defined policy.

  • Self-balancing trees (AVL, red-black): These maintain height constraints during updates so search-tree operations remain O(log n); an ordinary BST does not guarantee this balance.

  • Heaps: A heap is commonly represented as a complete binary tree and often stored in an array. In a max-heap or min-heap the root holds an extreme value, so peek is O(1); insertion and removal of the root are typically O(log n). Heaps are one implementation for priority queues.

Tree height controls binary-search-tree work

Search follows one root-to-node path, so its cost is proportional to tree height. A balanced BST has logarithmic height; an ordinary skewed BST can have linear height.

Searching for 14 takes three comparisons in a balanced seven-node search tree, but seven comparisons in a degenerate search tree formed by ordered insertion.

Real-World Tree Uses

File systems (directories and subdirectories). Parsing HTML/XML documents (the Document Object Model or DOM Tree). Fast database indexing (B-Trees). Decision logic in AI.

5.2 Graphs

A graph is a set of vertices connected by edges. Edges may be directed or undirected; graphs can contain cycles or disconnected components and need not have a root.

Graph Types & Terminology

  • Directed graph: Each edge has an orientation, and a path follows that orientation. A graph may still contain separate edges in both directions.

  • Undirected Graph: The edges have no direction, meaning the relationship is mutual and travel is two-way (like Facebook friends).

  • Weighted Graph: Each edge has a numerical value (weight/cost) associated with it, representing physical distance, financial cost, or travel time.

Graph Representation in Memory

  • Adjacency matrix: A V × V table records whether each ordered vertex pair has an edge (or records its weight). It uses O(V²) space and supports direct edge lookup in O(1), but can use much more space than needed for a sparse graph.

  • Adjacency list: Each vertex stores its incident or outgoing neighbors, often in a list or collection. It uses O(V + E) space; enumerating neighbors takes O(degree(v)), and checking for one edge may require scanning that vertex's neighbors.

One graph can use a matrix or a neighbor list

The matrix reserves a cell for every possible vertex pair; the adjacency list stores the neighbors that actually exist. The choice changes space use and neighbor lookup cost.

The same undirected graph A-B, A-C, B-C, and C-D is shown as a symmetric four-by-four adjacency matrix and as one neighbor list per vertex.

5.3 Graph Traversal

A traversal visits vertices reachable from a starting vertex. Breadth-first search (BFS) explores in layers using a queue; depth-first search (DFS) follows an unexplored neighbor before backtracking, using a stack or recursion. A visited set prevents revisiting vertices in cyclic graphs. With adjacency lists, traversing one reachable component takes O(Vᵣ + Eᵣ); a full traversal across all components takes O(V + E). The order among same-depth or same-level neighbors depends on the chosen neighbor order.

BFS and DFS visit the same graph in different orders

The two traces share a graph and starting vertex but apply different frontier rules. Neighbor ordering is fixed for this example; another ordering can produce a different valid traversal.

Starting from A in a small graph, breadth-first search visits nearby vertices first using a queue, while depth-first search follows one branch before returning, using a stack or recursion.

Real-World Graph Uses

Social and computer networks model relationships as graphs. Routing models can attach distance, cost, or time to edges and select an algorithm suited to the graph and its weight assumptions.

6. Hash Tables (Hash Maps / Dictionaries)

A hash table implements key-to-value lookup by using a hash function to help select a table location. Collisions still need to be resolved, and performance depends on the hash function, table load, collision policy, and implementation.

How Hashing Works

  • Hash function: Maps a key to a hash value; the table maps that value to a bucket or home slot. A useful hash function is efficient and distributes the keys in the intended workload well, but cannot prevent every collision.

  • Buckets: A table uses the hash value to choose a bucket or home slot for the key-value entry.

  • Collisions: Sometimes the hash function inevitably generates the exact same index for two completely different keys. This collision must be handled.

  • Collision resolution: With separate chaining, a bucket holds a collection of entries that map there. With open addressing, entries stay in the table and a probe sequence searches for an available slot. Insertion and search must use compatible rules.

Different keys can share a home bucket

A collision is expected when different keys map to one home slot. Chaining and open addressing are different collision-resolution families; the shown function and keys are only an example.

The illustrative function h(k)=k mod 5 sends keys 12, 17, and 22 to slot 2; chaining keeps them in one bucket collection, while linear probing uses slots 2, 3, and 4.

Hash Table Performance

Lookup, insertion, and deletion are commonly expected or average O(1) under assumptions about hash distribution, load, and implementation. Collisions can make an operation O(n) in the worst case, and resizing can make an individual update more expensive.

Key Takeaways
  • An ADT specifies operations independently from the data structure that implements them.
  • Choose a structure based on required operations and workload; complexity claims depend on implementation, input size, and analyzed case.
  • Array-based lists support indexed access; middle insertion or deletion shifts elements, while dynamic-array append is commonly amortized O(1).
  • Linked lists follow links sequentially; rewiring can be O(1) once the required position is known, but locating it can take O(n).
  • Stacks remove the newest item first (LIFO); queues remove the oldest item first (FIFO).
  • BST operations depend on height: balanced trees have logarithmic height, while a skewed ordinary BST can require linear work.
  • Graph matrices use O(V²) space; adjacency lists use O(V + E) space and make neighbor scans proportional to degree.
  • Hash tables resolve collisions; O(1) operation costs are expected or average under stated assumptions, not guaranteed in every case.

References