From the free course Data Structures and Algorithmic Analysis on Lykke

Linear Data Structures

Key concepts: Singly Linked Lists · Doubly Linked Lists · Circular Linked Lists · Stacks (LIFO) · Queues (FIFO) · Resizing Arrays

Implementation and application of fundamental linear structures including Linked Lists, Stacks, and Queues.

Linear Data Structures

In the study of computer science, data structures are categorized by how they organize and access data. Linear Data Structures are those where data elements are arranged in a sequential order, such that each element is attached to its previous and next adjacent elements. This linear relationship is the simplest form of organization, yet it forms the backbone of nearly every complex system, from operating system schedulers to the "undo" stack in your favorite text editor.

The Fundamental Dichotomy: Arrays vs. Linked Structures

Before diving into specific types, we must understand the two primary ways linear data is stored in memory: Contiguous Allocation (Arrays) and Linked Allocation (Nodes).

  1. Arrays: Elements are stored in adjacent memory locations. This allows for $O(1)$ "random access" because the address of the $i$-th element can be calculated via a simple formula: base_address + i * size_of_element.
  2. Linked Structures: Elements (Nodes) are scattered throughout memory. Each node contains the data and a "pointer" or "reference" to the next node. This sacrifices random access for $O(1)$ insertions and deletions at specific points.
Feature Array-Based Linked-List Based
Access Time $O(1)$ (Random Access) $O(n)$ (Sequential Access)
Insertion/Deletion $O(n)$ (due to shifting) $O(1)$ (if position is known)
Memory Locality Excellent (Cache friendly) Poor (Pointer chasing)
Overhead Minimal (Fixed size) High (Store pointers for every element)

Singly Linked Lists

A Singly Linked List is a collection of nodes where each node points to the next, ending in a null reference. It is the most basic form of a linked structure.

What it is

Mathematically, a Singly Linked List is a directed graph where every node has an out-degree of at most 1. Each node consists of a Data Field (the value) and a Next Field (the reference).

How it works

To manage a list, we typically maintain a reference to the head (the first node). If the list is empty, head is null.

public class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

Operations and Complexity

  • Prepend (Add First): $O(1)$. Create a new node, point its next to the current head, and update head.
  • Append (Add Last): $O(n)$ if only head is known; $O(1)$ if a tail pointer is maintained.
  • Search: $O(n)$. You must traverse from the head until the value is found.
  • Delete: $O(n)$ for a general value because you must find the node before the one you want to delete to update its next pointer.

The "Lost Reference" Pitfall: A common error in Singly Linked Lists is losing the reference to the rest of the list during an insertion or deletion. Always update the next pointer of the new node before breaking the link of the previous node.


Doubly Linked Lists

A Doubly Linked List (DLL) extends the singly linked list by adding a prev pointer to each node, allowing for bidirectional traversal.

Why it matters

While a DLL uses more memory (an extra pointer per node), it solves a critical weakness of the singly linked list: the inability to look backward. In a singly linked list, deleting a node requires a reference to its predecessor. In a DLL, a node "knows" its predecessor, making deletion $O(1)$ if you already have a reference to the node being deleted.

Implementation

public class DoubleNode {
    int data;
    DoubleNode next;
    DoubleNode prev;
}

Comparison of Linked List Variants

Operation Singly Linked Doubly Linked Circular (Singly)
Traverse Forward Yes Yes Yes
Traverse Backward No Yes No (unless full loop)
Memory per Node $Data + 1$ Ptr $Data + 2$ Ptrs $Data + 1$ Ptr
Delete Given Node $O(n)$ $O(1)$ $O(n)$

Circular Linked Lists

In a Circular Linked List, the last node’s next pointer does not point to null; instead, it points back to the head (or some other node in the list).

Mechanics

Circular lists are often implemented with a single tail pointer rather than a head. Why? Because tail.next is effectively the head. This gives you $O(1)$ access to both the start and the end of the list with only one pointer.

Real-World Case: Round-Robin Scheduling

Operating systems use circular lists to manage CPU time slices. Each process is a node. The CPU services the process at the current pointer, then moves to current.next. When it reaches the "end," it naturally loops back to the first process without needing a conditional reset.


Resizing Arrays (Dynamic Arrays)

Standard arrays have a fixed size. To create a "growable" list (like Java's ArrayList or Python's list), we use Resizing Arrays.

The Geometric Resizing Strategy

When the array is full and a new element is added:

  1. Allocate a new array of a larger size (usually $2 \times$ the current capacity).
  2. Copy all elements from the old array to the new one.
  3. Update the reference to the new array.

Why $2N$ and not $N+1$?

If we increase the size by 1 each time, adding $N$ elements takes $1 + 2 + 3 + ... + N$ operations, which is $O(N^2)$. This is catastrophically slow. By doubling the size, we ensure that the "expensive" resize happens infrequently.

Amortized Analysis

Theorem: The amortized time complexity of an insertion in a resizing array (doubling strategy) is $O(1)$.

Proof (Aggregate Method): Consider $N$ insertions into an array starting at size 1.

  • The total number of copies due to resizing is $1 + 2 + 4 + 8 + ... + N/2$.
  • This is a geometric series that sums to approximately $N-1$.
  • Total work = $N$ (for the insertions) + $N-1$ (for the copies) $\approx 2N$.
  • Average work per insertion = $2N / N = 2$, which is $O(1)$.

Common Pitfall: Thrashing

If you resize up when the array is full and resize down immediately when it is 49% full, a sequence of alternating add and remove operations at the threshold could cause $O(N)$ resizing every single time. To prevent this, we typically wait until the array is 1/4 full before shrinking it to 1/2 size.


Stacks (LIFO)

A Stack is a restricted linear data structure that follows the Last-In-First-Out (LIFO) principle. Think of a stack of physical plates: you can only add to the top and take from the top.

Key Operations

  1. push(item): Add an item to the top.
  2. pop(): Remove and return the top item.
  3. peek(): Return the top item without removing it.

Implementation Strategies

  • Linked List: push is addFirst(), pop is removeFirst(). Both are $O(1)$ guaranteed.
  • Resizing Array: push adds to the end of the array. $O(1)$ amortized.

Application: Dijkstra’s Two-Stack Algorithm

Stacks are essential for parsing mathematical expressions. Consider ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ).

  • Value Stack: Stores operands (1, 2, 3...).
  • Operator Stack: Stores operators (+, *).
  • When a right parenthesis ) is encountered, pop an operator and two values, apply the operator, and push the result back onto the value stack.

Queues (FIFO)

A Queue follows the First-In-First-Out (FIFO) principle. It models a line at a grocery store: the first person to join the line is the first to be served.

Key Operations

  1. enqueue(item): Add an item to the back (tail).
  2. dequeue(): Remove and return the item from the front (head).

The Circular Buffer (Array Implementation)

Implementing a queue with an array is trickier than a stack. If we simply remove the element at index 0, we must shift all other elements left, making dequeue $O(n)$. To achieve $O(1)$, we use a Circular Buffer:

  • Maintain head and tail indices.
  • When tail reaches the end of the array, it wraps around to index 0.
  • The queue is full when (tail + 1) % capacity == head.
Feature Stack (LIFO) Queue (FIFO)
Top/Front Operation pop() dequeue()
Bottom/Back Operation push() enqueue()
Primary Use Case Backtracking, Recursion Buffering, Scheduling
Search/Access Not allowed (theoretically) Not allowed (theoretically)

Summary of Complexity

Understanding the performance characteristics is vital for choosing the right structure for a specific algorithm.

Data Structure Access Search Insertion (at end) Deletion (at end)
Array (Fixed) $O(1)$ $O(n)$ $N/A$ $N/A$
Resizing Array $O(1)$ $O(n)$ $O(1)$ amortized $O(1)$ amortized
Singly Linked List $O(n)$ $O(n)$ $O(1)$ (w/ tail) $O(n)$
Doubly Linked List $O(n)$ $O(n)$ $O(1)$ $O(1)$

Advanced Pitfalls and Considerations

1. Memory Overhead

In high-performance computing, the memory overhead of linked lists is a significant deterrent. On a 64-bit system, every Node in a singly linked list carries an 8-byte pointer. If you are storing 4-byte integers, you are using 12 bytes of memory per 4 bytes of data—a 200% overhead. Arrays have near-zero overhead.

2. Cache Locality

Modern CPUs use a hierarchy of caches (L1, L2, L3). When the CPU accesses a memory address, it loads a "cache line" (usually 64 bytes) into the fast cache.

  • Arrays benefit from this: accessing arr[0] likely loads arr[1] through arr[15] into the cache.
  • Linked Lists suffer from "pointer chasing": each node could be anywhere in memory, forcing the CPU to wait for a slow RAM fetch for every single element.

3. Loitering (Java/Managed Languages)

In a resizing array implementation of a stack, when you pop an element, you simply decrement the index.

public Object pop() {
    return array[--N]; // The reference array[N] still exists!
}

The reference to the object remains in the array, preventing the Garbage Collector from reclaiming that memory. This is called loitering. To fix this, you must explicitly null out the reference:

public Object pop() {
    Object item = array[--N];
    array[N] = null; // Prevent loitering
    return item;
}
Linear Data Structures - Data Structures and Algorithmic Analysis - image 1
Linear Data Structures - Data Structures and Algorithmic Analysis - image 1
Linear Data Structures - Data Structures and Algorithmic Analysis - diagram 1
Linear Data Structures - Data Structures and Algorithmic Analysis - diagram 1
Linear Data Structures - Data Structures and Algorithmic Analysis - diagram 2
Linear Data Structures - Data Structures and Algorithmic Analysis - diagram 2

Source Materials

Study Data Structures and Algorithmic Analysis on Lykke

This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.

Add the free extensionSign in to open every section

All sections of Data Structures and Algorithmic Analysis · Browse more course pages