Linked Data Structures

Introduction and Context

A linked data structure stores a collection of elements as separate objects connected by references. Unlike an array, whose elements normally occupy one contiguous region of memory, a linked structure can place its nodes in different locations. Each node stores data and one or more links to other nodes.

Linked structures are fundamental in programming because they illustrate dynamic memory use, reference management, abstraction, and the design of non-contiguous collections. They are used in playlists, browser histories, graph representations, hash-table buckets, undo systems, task queues, and memory-management mechanisms.

The central design question is not simply whether a linked list works. It is whether its operational advantages justify its extra memory, indirect access, and greater implementation complexity when compared with arrays or dynamic array classes such as Java's ArrayList and Python's list.

Learning Objectives

By the end of this chapter, you should be able to:

• explain nodes, references, heads, tails, and links;
• design singly, doubly, and circular linked lists;
• implement traversal, insertion, deletion, reversal, and merging;
• manage empty lists, one-node lists, and boundary references safely;
• compare linked structures with contiguous storage;
• analyse time and space complexity;
• apply linked-list designs to a realistic software problem in Java and Python.

1. Fundamental Concepts

1.1 Nodes and references

A linked list consists of nodes. A node generally contains:

1. a data field, and
2. a reference to another node.

For a singly linked list, the link is conventionally called next. A missing link is represented by null in Java and None in Python. The first node is reached through a reference called head. A list may also maintain a tail reference to its final node and a size field containing the number of nodes.

A singly linked list with values 12, 25, and 31 can be described as:

head → [12 | next] → [25 | next] → [31 | null]

The arrows represent references, not physical adjacency. The nodes may be distributed throughout memory.

1.2 Invariants

An invariant is a condition that must remain true after every public operation. Useful list invariants include:

• An empty list has head == null or head is None.
• If a tail is maintained, an empty list also has tail == null or tail is None.
• The tail's next reference is null in a non-circular singly linked list.
• size equals the number of reachable nodes.
• Following next repeatedly eventually reaches null in a linear list.

Invariants provide a practical method for detecting reference errors. An operation that violates an invariant may produce lost nodes, cycles, incorrect counts, or runtime exceptions.

1.3 Complexity model

Let n denote the number of nodes. In a singly linked list, accessing the element at position i requires following links from the head and therefore takes O(i), or O(n) in the worst case. Inserting immediately after a known node takes O(1), because only a constant number of references must be changed. Searching for a value takes O(n) in the worst case.

These statements assume that reference assignment, comparison, and reading a node field take constant time. They also assume that the list is not augmented with an index structure.

2. Singly Linked Lists

2.1 Structure and design

A singly linked list supports movement in one direction. It uses less memory than a doubly linked list because each node stores only one link. Its main limitation is that a predecessor cannot be reached directly from a node; deletion often requires locating that predecessor first.

A robust implementation normally provides methods such as isEmpty, append, prepend, insertAfter, removeFirst, removeValue, contains, reverse, and toString or an equivalent display operation.

2.2 Node definitions

Java:

class Node<T> {
    T data;
    Node<T> next;

    Node(T data) {
        this.data = data;
    }
}

Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Generics in Java allow the same structure to store different reference types. Python's dynamic typing allows different object types, although professional code should still document intended data types and preserve consistent invariants.

2.3 Traversal

Traversal begins at head and repeatedly follows next until null.

Java:

void traverse() {
    Node<T> current = head;
    while (current != null) {
        System.out.println(current.data);
        current = current.next;
    }
}

Python:

def traverse(self):
    current = self.head
    while current is not None:
        print(current.data)
        current = current.next

The loop is O(n) time and O(1) auxiliary space. It is important to advance current; otherwise the program enters an infinite loop.

2.4 Insertion

To prepend a node, assign its link to the current head and then move the head to the new node:

def prepend(self, value):
    node = Node(value)
    node.next = self.head
    self.head = node
    if self.tail is None:
        self.tail = node
    self.size += 1

This operation is O(1). The order of assignments matters. Setting head first and then trying to use the old head can disconnect the existing list.

Appending is O(1) when a tail reference is maintained:

def append(self, value):
    node = Node(value)
    if self.head is None:
        self.head = self.tail = node
    else:
        self.tail.next = node
        self.tail = node
    self.size += 1

Without a tail reference, append requires traversal and is O(n).

To insert after a known node p, use the sequence:

new.next = p.next
p.next = new

The first assignment preserves the remainder of the list before the second assignment changes the predecessor's link. The operation is O(1) if p is already known; finding p may make the complete operation O(n).

2.5 Deletion

Removing the first node is straightforward:

def remove_first(self):
    if self.head is None:
        raise IndexError("remove from empty list")
    value = self.head.data
    self.head = self.head.next
    self.size -= 1
    if self.head is None:
        self.tail = None
    return value

A safe implementation handles the transition from one node to zero nodes by updating both head and tail.

To remove the first occurrence of a value, maintain both previous and current references:

def remove_value(self, value):
    previous = None
    current = self.head
    while current is not None and current.data != value:
        previous, current = current, current.next
    if current is None:
        return False
    if previous is None:
        self.head = current.next
    else:
        previous.next = current.next
    if current is self.tail:
        self.tail = previous
    self.size -= 1
    return True

Searching and deletion are O(n) in the worst case. The removed node becomes unreachable from the list. Java's garbage collector can later reclaim it; Python's reference-counting and cyclic-garbage mechanisms manage reclamation according to the implementation. Programmers should nevertheless remove unnecessary references and avoid retaining nodes accidentally.

2.6 Reversal

Reversal changes every link so that the final node becomes the first. The iterative method uses three references:

def reverse(self):
    previous = None
    current = self.head
    self.tail = self.head
    while current is not None:
        following = current.next
        current.next = previous
        previous = current
        current = following
    self.head = previous

At each iteration, following preserves the unprocessed suffix before the link is reversed. The time complexity is O(n), and auxiliary space is O(1). A recursive solution is also possible, but it uses call-stack space and may exceed the recursion limit for a long list.

2.7 Merging sorted singly linked lists

Two lists sorted in ascending order can be merged without creating new data nodes. Maintain a dummy node and repeatedly connect the smaller current node:

def merge_sorted(a, b):
    dummy = Node(None)
    tail = dummy
    while a is not None and b is not None:
        if a.data <= b.data:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a if a is not None else b
    return dummy.next

If the lists contain m and n nodes, merging takes O(m + n) time and O(1) additional node space, assuming nodes are relinked rather than copied. The input lists should not be used independently afterward unless the design explicitly permits shared or transferred ownership.

3. Doubly Linked Lists

A doubly linked list stores previous and next references:

null ← [A] ⇄ [B] ⇄ [C] → null

Java node definition:

class DNode<T> {
    T data;
    DNode<T> previous, next;

    DNode(T data) {
        this.data = data;
    }
}

The additional link permits traversal in both directions and allows deletion of a known node in O(1) time. The cost is extra memory and more reference updates.

To insert newNode between left and right, the conceptual assignments are:

newNode.previous = left
newNode.next = right
left.next = newNode
right.previous = newNode

Boundary cases replace left or right with a head or tail update. A common professional technique is to use sentinel nodes. A sentinel head and sentinel tail are permanent, non-data nodes; every real node lies between them. This reduces special cases because insertion and deletion always occur between two nodes.

Deleting a known node x requires:

x.previous.next = x.next
x.next.previous = x.previous

The operation is O(1), provided x belongs to the list and is not a sentinel. Validation is important when nodes can be supplied by external code; otherwise a node from another list may corrupt both structures.

Doubly linked lists are appropriate for browser history, where moving backward and forward is common, and for LRU caches, where a known item must be removed and moved quickly. They are less attractive when memory is constrained or movement is almost exclusively forward.

4. Circular Linked Lists

In a circular list, the final node links back to the first rather than to null. A circular singly linked list can be represented efficiently by a tail reference: the head is tail.next.

For a non-empty circular list:

• tail.next is the head;
• no link is null merely because it is the end;
• traversal must stop when it returns to the starting node.

A safe traversal is:

def traverse_circular(self):
    if self.tail is None:
        return
    start = self.tail.next
    current = start
    while True:
        print(current.data)
        current = current.next
        if current is start:
            break

Using while current is not None would be incorrect and would create an infinite loop. Circular lists are useful for round-robin scheduling, repeated playlists, and token-ring-like processing. They require careful termination conditions and explicit handling of the empty and one-node cases.

Insertion after the tail can be O(1), because the head is tail.next. Inserting a new node into a one-node circular list requires the node to point to itself and the tail to become the new node if the operation is defined as appending.

5. Comparing Linked and Contiguous Storage

Big-O notation describes growth as the input becomes large; it does not measure every practical cost. An array may outperform a linked list for traversal because contiguous elements use processor caches effectively. Consequently, a linked list should not be selected merely because insertion is theoretically O(1). The location of the insertion point, memory overhead, workload distribution, and library support must all be considered.

Java's LinkedList provides a general-purpose doubly linked list, while ArrayList is array-backed. Python's built-in list is a dynamic array, not a linked list. Python's collections.deque is usually preferable for efficient insertion and removal at both ends, though its internal representation should be treated as an implementation detail.

6. Safe Reference Management

Reference manipulation is the defining source of both power and danger in linked structures.

Preserve before overwrite. Before changing current.next, save the old successor if it is still needed. Otherwise the remaining suffix may become unreachable.

Update all boundary references. When deleting the head or tail, update head, tail, and size consistently.

Handle empty and singleton lists. Test operations on zero, one, and several nodes. These cases expose most defects.

Avoid accidental cycles. A mistaken assignment such as node.next = node may create a cycle in a linear list. Traversal then fails to terminate.

Define ownership. If a merge relinks nodes from two lists, determine whether the original lists are consumed. If nodes are copied, document the additional memory and object-identity consequences.

Do not compare unrelated references as if they were positions. A node may have equal data to another node without being the same node. Use identity tests where node identity matters.

Use encapsulation. Keep node fields private in Java where appropriate, and expose controlled list methods. In Python, naming conventions and careful interfaces help prevent external code from breaking invariants.

Testing should include empty lists, duplicate values, missing values, insertion at both ends, deletion of the only node, reversal twice, merging with an empty list, and circular traversal termination. Assertions can check that a recorded count agrees with traversal and that a linear list eventually reaches null.

7. Applied Case: A Round-Robin Task Scheduler

Background

Consider an illustrative operating-system training simulator containing tasks that receive a fixed time slice in rotation. When a task uses its slice and remains unfinished, it moves to the end of the queue. Completed tasks leave the queue.

Problem

The scheduler needs frequent removal from the front and insertion at the rear. It must also continue from the first task after the last task without repeatedly searching for the beginning.

Analysis

A circular singly linked list with a tail reference is suitable. The active task is tail.next, and the next task is reached through one link. Removing the front task requires changing tail.next; adding a task after the tail requires changing two links and moving tail.

Approach

For a non-empty queue, the invariant is that tail.next is the front task. To rotate after a time slice, assign tail = tail.next; the new front is then tail.next. To remove the front task when there are at least two nodes, set tail.next = front.next. For a one-node queue, removal sets tail to null.

Outcome

Both rotation and end insertion are O(1). The design avoids shifting a large array and naturally expresses cyclic processing. However, it does not provide priority ordering, and searching for a particular task remains O(n). A production scheduler would additionally need synchronization, cancellation rules, fairness policies, and protection against a task that refuses to yield.

Learning Points

The case demonstrates that structure should follow workload. Circularity is useful because the process is inherently cyclic, while a tail reference makes the required operations constant time. The design remains correct only when the empty and singleton cases preserve the circular invariant.

8. Professional Practice and Contemporary Relevance

Linked structures remain valuable for teaching pointer-like reasoning, implementing adjacency lists, and constructing specialized queues, caches, and allocators. Nevertheless, modern applications often prefer standard library collections because they are tested, optimized, and easier to maintain.

In Java, generic types reduce casting errors, and immutable or unmodifiable views can protect collection boundaries. In Python, iterators and generators can provide traversal without exposing internal nodes. In concurrent systems, ordinary linked-list code is not automatically thread-safe; locks or specialized concurrent structures are required. Reference safety is also a security concern: corrupted links can cause denial of service through infinite traversal or can expose data that should no longer be reachable.

Artificial intelligence does not remove the need to understand these structures. AI-generated code may omit tail updates, mishandle circular termination, or claim an incorrect complexity. Human developers must test invariants, inspect ownership assumptions, and benchmark alternatives under realistic workloads.

Chapter Summary

Linked data structures store nodes connected by references rather than relying on contiguous storage. Singly linked lists support compact forward traversal; doubly linked lists add backward traversal and efficient deletion of known nodes; circular lists connect the final node back to the first and suit repeated rotation. Traversal is generally linear, while insertion can be constant time when the relevant position is already known. Correctness depends on preserving invariants, saving links before overwriting them, updating boundary references, and handling empty and one-node cases. Linked lists offer flexible insertion and deletion but usually have poorer indexed access, cache locality, and memory efficiency than array-backed collections. Selection should therefore reflect the actual workload and the guarantees provided by standard libraries.

Key Terms

Node: An object containing data and one or more references.

Reference: A value that identifies or points to another object.

Head: Reference to the first node of a linear list.

Tail: Reference to the final node, when maintained.

Link: A node field that refers to another node.

Singly linked list: A list whose nodes contain a forward link.

Doubly linked list: A list whose nodes contain forward and backward links.

Circular linked list: A list whose final node links back to the first.

Traversal: Visiting nodes by following links.

Invariant: A condition that must remain true throughout operations.

Sentinel: A non-data boundary node used to simplify algorithms.

Predecessor: The node immediately before a specified node.

Contiguous storage: Storage in adjacent memory locations.

Identity: The fact that two references designate the same object.

Amortized complexity: Average cost per operation over a sequence of operations.

Ownership: Responsibility for managing or interpreting nodes and their links.

Cache locality: The performance benefit of accessing nearby memory locations.

Garbage collection: Automatic reclamation of unreachable objects.

Review Questions

Short Answer Questions

1. What information is normally stored in a node of a singly linked list?
2. Why is a tail reference useful when appending to a list?
3. What is the principal structural difference between singly and doubly linked lists?
4. Why must circular-list traversal use a stopping condition other than null?
5. State two invariants of a non-circular singly linked list.

Long Answer Questions

1. Explain the insertion and deletion operations of a singly linked list, including their boundary cases and time complexities.
2. Compare linked lists with dynamic arrays in terms of access, insertion, memory use, and cache behaviour.
3. Describe how reversal of a singly linked list works using previous, current, and following references.
4. Explain sentinel nodes in doubly linked lists and show how they reduce special cases.
5. Discuss the design, advantages, and risks of a circular linked list used for round-robin scheduling.

Analytical / Application Questions

1. Design a linked structure for a browser history that supports moving backward and forward and removing the current page. Justify whether a singly or doubly linked list is preferable.
2. A program appends 10,000 values to a singly linked list without maintaining a tail reference. Analyse the resulting time cost and propose an improvement.
3. A merge operation relinks nodes from two sorted lists. Explain what happens to the original lists and identify an ownership policy that would make the API safe.

Multiple Choice Questions with Answers

Question 1

Which reference identifies the first node in a conventional linear linked list?

A. tail

B. head

C. previous

D. sentinel

Correct Answer: B. head

Question 2

What is the worst-case time complexity of accessing position i in a singly linked list by starting at the head?

A. O(1)

B. O(log n)

C. O(i), and O(n) in the worst case

D. O(n²)

Correct Answer: C. O(i), and O(n) in the worst case

Question 3

Why can appending be O(1) in a singly linked list?

A. The list stores all nodes contiguously

B. A tail reference identifies the final node

C. The list automatically sorts its nodes

D. Indexing skips directly to the final node

Correct Answer: B. A tail reference identifies the final node

Question 4

Which links are required in a doubly linked-list node?

A. Only a data field

B. A parent and child link

C. Previous and next links

D. A head and tail field only

Correct Answer: C. Previous and next links

Question 5

During iterative reversal of a singly linked list, why is the successor saved before changing current.next?

A. To count the nodes

B. To preserve access to the unprocessed suffix

C. To sort the list

D. To allocate a new tail

Correct Answer: B. To preserve access to the unprocessed suffix

Question 6

In a non-empty circular singly linked list represented by tail, where is the head found?

A. tail.next

B. tail.next.next.next only

C. null

D. The node before tail

Correct Answer: A. tail.next

Question 7

What is the time complexity of merging sorted lists containing m and n nodes when existing nodes are relinked?

A. O(1)

B. O(log(m+n))

C. O(m+n)

D. O(mn)

Correct Answer: C. O(m+n)

Question 8

Which structure usually provides O(1) indexed access?

A. Singly linked list

B. Doubly linked list

C. Circular linked list

D. Array-backed dynamic array

Correct Answer: D. Array-backed dynamic array

Question 9

What must be updated when deleting the only node from a list that maintains head and tail?

A. Only size

B. Only head

C. Head, tail, and size

D. Only the node's data

Correct Answer: C. Head, tail, and size

Question 10

Which application is especially well suited to a circular linked list?

A. Binary search by index

B. Round-robin processing

C. Constant-time random access

D. Contiguous matrix storage

Correct Answer: B. Round-robin processing