Fundamental Data Structures

Introduction

A data structure is an organized representation of data together with operations for accessing and modifying it. In engineering software, the choice of structure affects execution time, memory use, predictability, maintainability, and safety. A sensor logger may require fast append operations; a scheduler may require priority removal; a network model requires vertices and edges. No structure is universally best.

This chapter develops lists, linked structures, stacks, queues, priority queues, trees, hash tables, and graphs. The implementations use Python-like pseudocode, but the algorithms transfer directly to C, C++, Java, and MATLAB. Unless stated otherwise, indexing begins at zero, and an operation's complexity is expressed in terms of n, the number of stored elements.

Learning objectives

After studying this chapter, you should be able to:

• explain the abstract data type (ADT) represented by each structure;
• implement fundamental operations on array-based and linked structures;
• distinguish worst-case, average-case, and amortized complexity;
• select structures using access patterns, memory constraints, and real-time requirements;
• apply trees, hash tables, and graphs to engineering problems; and
• identify safety, correctness, and resource-management risks in implementations.

Complexity and engineering choice

Big-O notation describes how resource requirements grow as input size increases. It does not predict exact execution time. For example, O(1) access may still be slower than another O(1) operation because of cache behavior.

Lists and linked structures

A list is an ordered sequence. An array-backed list stores elements in contiguous logical positions. Its indexed read is O(1), while insertion at position i generally requires shifting approximately n-i elements and is therefore O(n) in the worst case.

A singly linked list stores a value and a link to the next node. Nodes need not be contiguous in memory. A doubly linked list additionally stores a previous link, enabling traversal in both directions at the cost of memory and link-maintenance work.

Complete singly linked-list implementation

class Node:
    value
    next = null

class SinglyList:
    head = null
    tail = null
    size = 0

    append(value):
        node = Node(value)
        if tail == null:
            head = tail = node
        else:
            tail.next = node
            tail = node
        size = size + 1

    prepend(value):
        node = Node(value)
        node.next = head
        head = node
        if tail == null: tail = node
        size = size + 1

    insert_at(index, value):
        if index < 0 or index > size: error "invalid index"
        if index == 0: prepend(value); return
        if index == size: append(value); return
        previous = head
        repeat index - 1 times: previous = previous.next
        node = Node(value)
        node.next = previous.next
        previous.next = node
        size = size + 1

    get(index):
        if index < 0 or index >= size: error "invalid index"
        current = head
        repeat index times: current = current.next
        return current.value

    remove_at(index):
        if index < 0 or index >= size: error "invalid index"
        if index == 0:
            removed = head
            head = head.next
            size = size - 1
            if size == 0: tail = null
            return removed.value
        previous = head
        repeat index - 1 times: previous = previous.next
        removed = previous.next
        previous.next = removed.next
        if removed == tail: tail = previous
        size = size - 1
        return removed.value

    find(value):
        current = head; index = 0
        while current != null:
            if current.value == value: return index
            current = current.next; index = index + 1
        return -1

With both head and tail references, append and prepend are O(1). Indexed access, search, and insertion at an arbitrary position are O(n). Removal is O(1) when the node and its predecessor are already known, but finding them may cost O(n). Correct boundary handling is essential: empty lists, one-element lists, insertion at size, and removal of the tail must all be tested.

Stacks

A stack follows last-in, first-out (LIFO). Its ADT operations are push, pop, peek, and is_empty. Stacks support expression evaluation, function-call management, undo operations, and depth-first search.

class ArrayStack:
    data = new array with capacity 4
    top = 0                 # number of stored items

    push(x):
        if top == length(data):
            new_data = new array of length 2 * length(data)
            copy data[0..top-1] into new_data
            data = new_data
        data[top] = x
        top = top + 1

    pop():
        if top == 0: error "underflow"
        top = top - 1
        x = data[top]
        data[top] = null
        return x

    peek():
        if top == 0: error "underflow"
        return data[top - 1]

Push is O(1) when capacity is available, but a particular push that triggers resizing is O(n). Across a sequence of pushes with geometric doubling, total copying is linear, so push is amortized O(1). Pop and peek are worst-case O(1). A linked stack avoids resizing but allocates one node per item.

Queues and circular buffers

A queue follows first-in, first-out (FIFO). It is used for communication buffers, task dispatch, and discrete-event simulation. Shifting an array after every dequeue is inefficient. A circular buffer uses head and tail indices modulo capacity.

class CircularQueue:
    buffer = new array of capacity C
    head = 0; tail = 0; count = 0

    enqueue(x):
        if count == C: error "overflow"
        buffer[tail] = x
        tail = (tail + 1) mod C
        count = count + 1

    dequeue():
        if count == 0: error "underflow"
        x = buffer[head]
        buffer[head] = null
        head = (head + 1) mod C
        count = count - 1
        return x

    front():
        if count == 0: error "underflow"
        return buffer[head]

All shown operations are O(1). The fixed capacity must be selected from a justified worst-case workload. A dynamically growing circular queue can resize, making a resize-triggering enqueue O(n) but enqueue amortized O(1) under geometric growth.

Priority queues

A priority queue removes the item with greatest or smallest priority rather than the oldest item. A binary min-heap stores the smallest key at the root. For zero-based indexing, the parent of index i>0 is ⌊(i-1)/2⌋, and children are 2i+1 and 2i+2.

class MinHeap:
    a = empty array

    push(item):
        append item to a
        i = length(a) - 1
        while i > 0:
            p = (i - 1) // 2
            if a[p].priority <= a[i].priority: break
            swap a[p], a[i]; i = p

    pop_min():
        if length(a) == 0: error "empty heap"
        result = a[0]
        last = remove_last(a)
        if length(a) > 0:
            a[0] = last
            i = 0
            while true:
                left = 2*i + 1; right = left + 1; smallest = i
                if left < length(a) and a[left].priority < a[smallest].priority: smallest = left
                if right < length(a) and a[right].priority < a[smallest].priority: smallest = right
                if smallest == i: break
                swap a[i], a[smallest]; i = smallest
        return result

    peek_min():
        if length(a) == 0: error "empty heap"
        return a[0]

Heap insertion and removal are O(log n); peeking is O(1). Building a heap bottom-up from n items is O(n), whereas inserting n items individually costs O(n log n).

Trees

A tree is a connected, acyclic graph. Equivalently, it is a hierarchical structure in which every pair of vertices has exactly one simple path. A rooted tree designates one vertex as the root; each non-root node has exactly one parent. A binary tree has at most two children per node.

A binary search tree (BST) satisfies: every key in the left subtree is less than the node key, and every key in the right subtree is greater, assuming distinct keys. In-order traversal therefore produces sorted order.

class BSTNode:
    key; left = null; right = null

insert(node, key):
    if node == null: return BSTNode(key)
    if key < node.key: node.left = insert(node.left, key)
    else if key > node.key: node.right = insert(node.right, key)
    return node

contains(node, key):
    while node != null:
        if key == node.key: return true
        node = node.left if key < node.key else node.right
    return false

inorder(node, output):
    if node == null: return
    inorder(node.left, output)
    append node.key to output
    inorder(node.right, output)

Search and insertion cost O(h), where h is tree height. A balanced BST has h = O(log n), but inserting sorted input into an ordinary BST can produce h = n, giving O(n) operations. AVL and red-black trees maintain balance through rotations; they are appropriate when ordered operations and predictable logarithmic performance are required.

Figure: A binary search tree; every left-subtree key is smaller and every right-subtree key is larger.

Hash tables

A hash table maps a key to an array position using a hash function. Since different keys may map to the same position, collision resolution is required. The implementation below uses separate chaining. Let the load factor be α=n/m, where n is the number of entries and m is the number of buckets.

class HashTable:
    buckets = array of m empty lists
    size = 0

    index(key): return nonnegative(hash(key)) mod length(buckets)

    put(key, value):
        b = buckets[index(key)]
        for pair in b:
            if pair.key == key: pair.value = value; return
        append (key, value) to b; size = size + 1
        if size / length(buckets) > 0.75: resize(2 * length(buckets))

    get(key):
        for pair in buckets[index(key)]:
            if pair.key == key: return pair.value
        return NOT_FOUND

    remove(key):
        b = buckets[index(key)]
        for pair in b:
            if pair.key == key: delete pair; size = size - 1; return
        return NOT_FOUND

    resize(new_m):
        old = buckets; buckets = array of new_m empty lists; size = 0
        for b in old:
            for pair in b: put(pair.key, pair.value)

With a well-distributed hash function and controlled load factor, lookup, insertion, and deletion are expected O(1). Their worst case is O(n) if many keys collide. Resizing is O(n) for that operation, but geometric resizing gives amortized constant insertion. Keys must have stable equality and hash behavior while stored. Hash tables do not naturally provide sorted traversal.

Graphs

A graph is G=(V,E), where V is a set of vertices and E is a set of edges. Graphs may be directed or undirected, weighted or unweighted. An undirected edge connects two vertices symmetrically; a directed edge represents an ordered relationship. An acyclic graph contains no cycle; a directed acyclic graph (DAG) is useful for dependency scheduling.

Adjacency lists use O(|V|+|E|) space and are efficient for sparse graphs. An adjacency matrix uses O(|V|²) space and gives constant-time edge testing, making it suitable for dense graphs.

class Graph:
    adj = map from vertex to list of (neighbor, weight)

    add_vertex(v):
        if v not in adj: adj[v] = empty list

    add_edge(u, v, w=1, directed=false):
        add_vertex(u); add_vertex(v)
        append (v, w) to adj[u]
        if not directed: append (u, w) to adj[v]

    breadth_first_search(start):
        visited = set(start); q = CircularQueue(); q.enqueue(start); order = []
        while not q.empty():
            u = q.dequeue(); append u to order
            for (v, w) in adj[u]:
                if v not in visited: add v to visited; q.enqueue(v)
        return order

    depth_first_search(start):
        visited = empty set; order = []
        visit(u):
            add u to visited; append u to order
            for (v, w) in adj[u]:
                if v not in visited: visit(v)
        visit(start); return order

BFS and DFS run in O(|V|+|E|) with adjacency lists. BFS finds minimum edge-count paths in an unweighted graph. Dijkstra's algorithm finds minimum nonnegative-weight paths, commonly in O((|V|+|E|)log|V|) with a binary heap; negative edge weights require other methods, such as Bellman–Ford.

Selection framework

Choose an array when compact storage and indexed access dominate. Choose a linked structure when frequent local insertion and deletion justify pointer overhead. Use a stack for reversal, nesting, and backtracking; a queue for arrival order; and a priority queue for urgency or cost ordering. Use a balanced tree for ordered queries, a hash table for expected direct key lookup, and a graph for many-to-many relationships.

Engineering selection must also consider memory fragmentation, cache locality, maximum occupancy, concurrency, failure behavior, and determinism. In hard real-time systems, amortized guarantees may be unacceptable: preallocation and bounded queues may be preferable. Inputs from outside the system require validation, because malformed keys, excessive graph size, or uncontrolled recursion can cause denial of service or memory exhaustion.

Applied case: illustrative industrial alarm dispatcher

Background. An embedded monitoring controller receives alarms from 2,000 sensors. Each alarm has a sensor identifier, timestamp, severity, and acknowledgement state.

Problem. The controller must retain recent alarms, display them in arrival order, dispatch severe alarms first, and determine sensor status quickly.

Analysis. A bounded circular queue stores incoming events in FIFO order. A min-heap ordered by negative severity and then timestamp selects the next alarm. A hash table maps sensor identifiers to current status. A graph represents dependencies between sensors and physical subsystems; BFS identifies affected components after a failure.

Approach. The queue capacity is selected from the validated maximum burst. Overflow is explicitly reported rather than silently overwriting alarms. Heap entries contain immutable alarm identifiers. Hash-table resizing is performed outside the strict interrupt handler, while the interrupt handler writes to a preallocated queue. Graph traversal is performed in a lower-priority task.

Outcome. Each normal event insertion, status lookup, and priority insertion is expected or amortized constant/logarithmic as appropriate, while memory behavior remains bounded by design. The separation between interrupt-time and background operations improves predictability.

Learning points. Data structures should be selected from operational requirements, not familiarity. Capacity, failure modes, tie-breaking, and timing guarantees are part of correctness.

Limitations, testing, and best practices

Pointer structures increase allocation and corruption risks. Recursive trees may overflow the call stack. Hash tables depend on hash quality and resizing policy. Graph algorithms can revisit vertices unless visited sets are used. Unit tests should cover empty, singleton, full, duplicate, boundary, and adversarial cases. Property-based tests can verify that a queue preserves insertion order, a heap always returns a minimum, and a BST's in-order output is sorted. Profiling should measure realistic workloads rather than relying only on asymptotic notation.

Use explicit ownership rules, immutable keys, checked indices, documented capacity limits, and deterministic tie-breaking where reproducibility matters. In safety-related software, trace data-structure assumptions to requirements and review worst-case execution time, not merely average performance.

Chapter Summary

Data structures implement abstract operations with different time, space, and predictability characteristics. Dynamic arrays provide fast indexing; linked lists provide flexible local changes; stacks and queues enforce LIFO and FIFO disciplines. Circular queues avoid shifting, while binary heaps implement priority queues in logarithmic time. Trees represent hierarchy, and balanced BSTs support ordered operations. Hash tables provide expected constant-time key operations when hashing and load factor are controlled. Graphs model relationships, with adjacency lists suited to sparse networks and BFS/DFS running in linear graph size. Sound engineering selection considers workload, capacity, memory, worst-case behavior, testing, and failure handling.

Key Terms

Abstract data type: A specification of values and operations independent of implementation.

Amortized analysis: Average cost per operation over a sequence, including occasional expensive operations.

Array-backed list: An ordered collection stored in indexable array positions.

Binary heap: A complete tree satisfying a parent-priority ordering.

Binary search tree: A binary tree ordered by key comparisons.

Circular buffer: An array whose indices wrap around at its capacity boundary.

Collision: Two distinct hash keys mapping to one table position.

DAG: A directed acyclic graph.

Depth-first search: Graph traversal that explores a path before alternatives.

Edge: A relationship connecting graph vertices.

FIFO: First-in, first-out processing order.

Graph: A set of vertices and edges.

Hash table: A key-value structure using a hash function for indexing.

LIFO: Last-in, first-out processing order.

Load factor: The ratio of stored entries to hash buckets.

Node: A record containing data and one or more links.

Priority queue: An ADT that removes an item according to priority.

Stack: An ADT supporting insertion and removal at one end.

Tree: A connected, acyclic graph, often organized hierarchically.

Vertex: A graph element representing an entity or state.

Review Questions

Short Answer Questions

1. Why is a dynamic-array push only amortized O(1)?
2. State the difference between FIFO and LIFO.
3. What condition defines a binary search tree?
4. Why are collisions unavoidable in many hash tables?
5. When is an adjacency matrix preferable to an adjacency list?

Long Answer Questions

1. Compare array-backed and singly linked lists for insertion, deletion, access, memory locality, and engineering use.
2. Explain circular-queue indexing and show why enqueue and dequeue are constant time when the buffer is not resized.
3. Describe binary-heap insertion and removal, including their complexity.
4. Explain how an ordinary BST can become unbalanced and compare it with a balanced BST.
5. Discuss expected versus worst-case hash-table complexity and the role of load factor.

Analytical / Application Questions

1. Design structures for a robotic controller that needs bounded event storage, urgent fault handling, and rapid lookup by device identifier. Justify each choice.
2. A road network has 50,000 intersections and 120,000 roads. Choose a representation and traversal method for finding the fewest-road route in an unweighted network. Explain complexity.
3. An alarm system receives events in bursts and cannot allocate memory inside an interrupt handler. Redesign the queue and processing architecture, stating capacity and failure-policy decisions.

Multiple Choice Questions with Answers

Question 1

Which operation on the implemented circular queue is constant time when the queue is not resized?

A. enqueue

B. Sort all elements

C. Search for an arbitrary value

D. Rebuild the buffer with half the capacity

Correct Answer: A. enqueue

Question 2

A dynamic-array push that triggers capacity doubling has what cost for that individual operation?

A. O(1) worst-case

B. O(log n) worst-case

C. O(n) worst-case

D. O(n²) worst-case

Correct Answer: C. O(n) worst-case

Question 3

Which structure removes the item with the smallest priority efficiently?

A. FIFO queue

B. Min-heap priority queue

C. Singly linked list without ordering

D. Stack

Correct Answer: B. Min-heap priority queue

Question 4

What is the formal graph property that distinguishes a tree?

A. It is disconnected and cyclic

B. It is connected and acyclic

C. It must be directed and weighted

D. It must contain equal numbers of vertices and edges

Correct Answer: B. It is connected and acyclic

Question 5

For a balanced binary search tree, search is typically:

A. O(1)

B. O(log n)

C. O(n log n)

D. O(n²)

Correct Answer: B. O(log n)

Question 6

In separate chaining, a collision is handled by:

A. Deleting the earlier key

B. Storing colliding entries in the same bucket structure

C. Making every table index unique without a hash function

D. Sorting the entire application

Correct Answer: B. Storing colliding entries in the same bucket structure

Question 7

For an adjacency-list graph, BFS has complexity:

A. O(|V| + |E|)

B. O(|V|²|E|)

C. O(log |V|)

D. O(1)

Correct Answer: A. O(|V| + |E|)

Question 8

Which structure is most appropriate for undoing nested operations?

A. Stack

B. Priority queue

C. Hash table

D. Adjacency matrix

Correct Answer: A. Stack

Question 9

If a hash table has n entries and m buckets, its load factor is:

A. m/n

B. n+m

C. n/m

D. n−m

Correct Answer: C. n/m

Question 10

BFS finds shortest paths by number of edges in which type of graph?

A. Any graph with negative weights

B. An unweighted graph

C. Only a complete weighted graph

D. Only a cyclic graph

Correct Answer: B. An unweighted graph