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 adjacent memory locations, a linked structure can grow and shrink without relocating all existing elements. Each element is called a node. A node contains data and one or more links to other nodes.

Linked structures are important in application development because they support dynamic collections, queues, stacks, playlists, browser histories, graph representations, memory managers, and hash-table collision chains. Their flexibility comes with a cost: links require extra memory, and accessing an arbitrary position generally requires sequential traversal.

This chapter focuses on three forms:

• singly linked lists, in which each node points forward to one successor;
• doubly linked lists, in which each node points to both a predecessor and a successor; and
• circular linked lists, in which the final node links back to the first node.

The examples use Python and Java-style reasoning. The same algorithms can be implemented in either language, although Python references and Java object references have different memory-management details.

Learning objectives

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

1. Explain the structure and purpose of linked lists.
2. Construct singly linked, doubly linked, and circular lists.
3. Traverse, insert, delete, search, and update nodes safely.
4. Compare linked lists with arrays and dynamic-array collections.
5. Analyse the time and space costs of common operations.
6. Select an appropriate linked structure for an application.
7. Apply defensive programming to avoid lost references, invalid links, and infinite traversal.

1. The node-and-link model

A linked list consists of nodes and an entry reference, commonly called head. A node stores a value and a link. In a singly linked list, the last node's link is None in Python or null in Java. The empty list is represented by head = None or head = null.

For a list containing A, B, and C, the logical structure is:

head → [A | next] → [B | next] → [C | None]

The arrows represent references, not copies of the stored values. Reassigning a link changes the structure of the list. It does not automatically copy the target node.

Important terminology includes:

• head: reference to the first node;
• tail: reference to the last node, if maintained;
• successor: node reached by following a next link;
• predecessor: node immediately before a node;
• null link: a link that points to no node;
• traversal: visiting nodes in link order;
• invariant: a condition that should remain true after every public operation.

Typical list invariants are that head is null exactly when the list is empty, every reachable node is visited at most once in a non-circular list, and a maintained size value equals the number of reachable nodes.

2. Singly linked lists

Construction

A minimal Python implementation is:

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

The tail and size fields are optional. They improve some operations but must be updated consistently. In Java, the corresponding fields would normally be declared as references such as private Node head; and private int size;.

Traversal

Traversal starts at head and repeatedly follows next until the null link is reached.

def values(self):
    result = []
    current = self.head
    while current is not None:
        result.append(current.value)
        current = current.next
    return result

If the list contains n nodes, traversal takes Θ(n) time and uses Θ(1) auxiliary space when values are processed directly. The returned Python list in this example requires Θ(n) additional storage because it copies the values.

Insertion at the front

To insert a node at the front, point the new node at the old head and then move head to the new node.

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

The order of assignments matters. Setting head before saving the old head can lose access to the existing list.

Insertion at the end

If no tail reference is maintained, insertion at the end requires traversal and takes Θ(n) time. With a tail reference, it takes Θ(1) time.

def add_last(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

The empty-list case is essential: both head and tail must refer to the new node.

Insertion after a known node

If a reference to the predecessor node is already available, insertion is constant time:

def insert_after(node, value):
    new_node = Node(value)
    new_node.next = node.next
    node.next = new_node

The new link must first preserve the old successor. If node.next is overwritten without saving it, the remainder of the list may become unreachable.

Deletion

Deleting the first node is straightforward:

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

To delete a later node, a singly linked list normally requires the predecessor. The predecessor's next is changed to bypass the target.

def remove_after(predecessor):
    target = predecessor.next
    if target is None:
        raise IndexError("no node to remove")
    predecessor.next = target.next
    target.next = None
    return target.value

Removing by value requires a search. If duplicate values are allowed, the algorithm must specify whether it removes the first occurrence, all occurrences, or a particular node.

Searching and updating

A sequential search compares each node's value with the target. Its worst-case time is Θ(n), and its best case is Θ(1) when the first node matches. Updating a node after locating it does not require shifting other elements, unlike an array.

3. Doubly linked lists

A doubly linked node stores prev, value, and next.

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

The two-way links support backward traversal and make deletion easier when a reference to the target node is available.

class DNode:
    def __init__(self, value):
        self.value = value
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

Insertion at the front and rear

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

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

Each insertion has several references to update. A robust implementation handles the empty, one-node, and multi-node cases explicitly or uses sentinel nodes to reduce special cases.

Insertion before a known node

For a target node current, the new node belongs between current.prev and current:

def insert_before(self, current, value):
    node = DNode(value)
    node.prev = current.prev
    node.next = current
    if current.prev is None:
        self.head = node
    else:
        current.prev.next = node
    current.prev = node
    self.size += 1

The operation is Θ(1) when current is already known. Finding current by value remains Θ(n).

Deleting a known node

def remove_node(self, node):
    if node.prev is None:
        self.head = node.next
    else:
        node.prev.next = node.next

    if node.next is None:
        self.tail = node.prev
    else:
        node.next.prev = node.prev

    node.prev = None
    node.next = None
    self.size -= 1
    return node.value

Both neighbouring links must be repaired. Failing to update one direction creates a list that behaves differently when traversed forward and backward.

Doubly linked lists use more memory than singly linked lists because every node stores an additional reference. In return, they support reverse traversal and convenient deletion of a known node.

4. Circular linked lists

In a circular list there is no null link at the logical end. The last node points back to the first node. A circular singly linked list can be represented efficiently by a tail reference: the head is tail.next.

For an empty list, tail = None. For a one-node list, tail.next points to tail itself.

class CircularList:
    def __init__(self):
        self.tail = None
        self.size = 0

Insertion at the front

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

Insertion at the rear

def add_last(self, value):
    self.add_first(value)
    self.tail = self.tail.next

After add_first, the inserted node is the head. Moving tail to its successor makes that node the new tail while preserving the circular order.

Traversal

A circular list must not be traversed using while current is not None, because no node contains None as its successor. Instead, stop when the traversal returns to the starting node.

def values(self):
    if self.tail is None:
        return []
    result = []
    start = self.tail.next
    current = start
    while True:
        result.append(current.value)
        current = current.next
        if current is start:
            break
    return result

An alternative is to repeat exactly size times. A size counter can therefore improve safety, particularly if the list might be temporarily malformed during debugging.

Use cases

Circular lists are appropriate when processing repeats continuously: round-robin scheduling, multiplayer turns, cyclic buffers, and recurring service queues. They simplify moving from the final item to the first item. They are less suitable when an explicit end marker is important or when programmers are likely to forget the stopping condition.

5. Complexity and design comparison

The following complexities assume that head and tail references are maintained where shown, and that an operation requiring a position does not already have a node reference unless stated.

Here, Θ(n) describes a tight asymptotic growth rate as the number of nodes n increases. It does not predict exact execution time, which also depends on hardware, language implementation, cache behaviour, and allocation overhead.

Arrays and dynamic arrays offer Θ(1) indexed access and good locality of reference, but insertion or deletion in the middle generally requires shifting Θ(n) elements. Linked lists avoid shifting but require pointer chasing and do not provide fast indexed access. In practical Python programs, the built-in list is a dynamic array and is often faster than a custom linked list for ordinary sequences. In Java, ArrayList and LinkedList should be selected according to access and update patterns rather than by assuming that linked lists are always faster.

6. Correctness, safety, and implementation practice

Preserve links before overwriting them

When inserting, connect the new node to the old successor before replacing the predecessor's link. When deleting, bypass the target before clearing its links. This ordering prevents accidental loss of the remaining chain.

Handle boundary cases

Every public operation should be tested for:

• an empty list;
• a one-node list;
• insertion or deletion at the head;
• insertion or deletion at the tail;
• duplicate values; and
• an invalid node, index, or absent value.

Maintain one source of truth

If both size and tail are stored, every mutation must update them. A stale size counter can cause incorrect loops; a stale tail can attach new nodes to the wrong place. A validate() method is useful during development.

Avoid unsafe exposure of internal nodes

Returning internal node references allows calling code to alter links without updating size, head, or tail. Public APIs should generally return values or controlled iterator objects unless node-level access is an intentional design feature.

Memory management

Python's reference counting and garbage collector, and Java's garbage collector, reclaim unreachable nodes automatically. Nevertheless, references can keep nodes reachable unnecessarily. Clearing removed node links helps debugging and prevents accidental use of detached structures. In manual-memory languages, failure to release removed nodes can cause memory leaks.

Iterators and concurrent modification

A list iterator should define what happens if the list changes during iteration. Java collection classes commonly detect some structural modifications and throw an exception. Application code should not modify a collection unexpectedly while traversing it unless the API explicitly supports that operation.

7. Worked example: removing duplicate values

Consider a singly linked list containing 4 → 7 → 4 → 9 → 7. To retain only the first occurrence of each value, maintain a set called seen and a predecessor pointer.

def remove_duplicates(self):
    seen = set()
    previous = None
    current = self.head

    while current is not None:
        if current.value in seen:
            previous.next = current.next
            if current is self.tail:
                self.tail = previous
            self.size -= 1
            current = previous.next
        else:
            seen.add(current.value)
            previous = current
            current = current.next

The final sequence is 4 → 7 → 9. Each node is inspected once, so traversal takes Θ(n) expected time assuming average constant-time set membership. The set requires Θ(u) auxiliary space, where u is the number of distinct values. Without a set, a nested search can remove duplicates using Θ(1) extra space but may take Θ(n²) time in the worst case.

The example illustrates a central design trade-off: additional memory can reduce execution time.

8. Applied case: a round-robin support queue

Background

This illustrative case concerns a help-desk application in which support agents receive tickets in repeating order. A ticket should be assigned to the next available agent, and after assignment the rotation should continue with the following agent.

Problem

An ordinary linear queue can add and remove tickets efficiently, but the application needs a rotating sequence of agents. After the last agent is considered, processing must continue with the first agent without rebuilding the collection.

Analysis

A circular singly linked list with a current reference is suitable. Each node contains an agent identifier and a link to the next agent. The invariant is that following links eventually returns to the starting node and that current always identifies the next agent to consider.

To select an agent, read current, then advance current = current.next. If an agent is unavailable, advance again until an available agent is found. The application must include a termination rule—for example, after checking at most the number of registered agents—so that a system in which all agents are unavailable does not loop forever.

Approach and solution

Adding an agent after a known node is Θ(1). Removing a known agent from a singly circular list requires its predecessor, so the implementation can either retain the predecessor during traversal or use a doubly circular list. A doubly circular structure is preferable if agents frequently leave the rotation and the application already holds direct node references.

The scheduler should not expose raw links to unrelated modules. Instead, it should provide operations such as add_agent, remove_agent, next_available_agent, and count_agents. Each operation should validate the circular invariant in development tests.

Outcome

The circular structure eliminates special end-of-list logic and supports constant-time advancement to the next node. Its principal risks are infinite loops, stale references after removal, and unclear behaviour when no agent is available.

Learning points

1. Data-structure choice follows the access pattern, not fashion.
2. Circular structures require explicit stopping conditions.
3. A documented invariant is a practical tool for correctness.
4. Encapsulation prevents callers from corrupting links.
5. Availability and failure cases belong in the algorithm design, not as afterthoughts.

9. Applications and contemporary practice

Linked structures remain useful in operating-system queues, graph adjacency lists, undo/redo histories, browser navigation, memory allocators, and separate chaining in hash tables. In high-performance systems, however, contiguous arrays and packed representations are often preferred because modern processors benefit from cache locality. A theoretically constant-time linked-list operation may be slower than a short array operation in real workloads.

In concurrent systems, updating links requires synchronization or atomic algorithms. A naïve concurrent insertion can cause lost updates or inconsistent traversal. Certificate-level applications should normally use well-tested library collections and synchronization mechanisms rather than implementing lock-free lists.

AI-generated code should also be reviewed carefully. Common generated errors include forgetting to update tail, using a null-termination loop on a circular list, and deleting a node without preserving its successor. Tests and invariant checks remain necessary regardless of the source of the code.

10. Best-practice checklist

• Define whether duplicate values are permitted.
• Specify whether deletion removes the first match, all matches, or a known node.
• Maintain head, tail, and size consistently.
• Document whether indexes are zero-based and how invalid indexes are handled.
• Test empty and one-node cases first.
• Use clear names such as current, previous, successor, and target.
• Do not use null-based traversal for circular lists.
• Prefer library collections in production unless custom link behaviour is required.
• Measure real workloads before choosing a linked list for performance reasons.
• Encapsulate structural mutation and validate invariants during development.

Challenges and limitations

Linked lists do not provide efficient random access. Each traversal may involve many object references, increasing latency and reducing cache efficiency. Nodes also require allocation and link storage. Bugs can be difficult to diagnose because a single incorrect reference can disconnect an entire suffix or create a cycle in a supposedly linear list.

Doubly linked lists consume additional memory and have more invariants. Circular lists reduce end-case handling but make termination less obvious. These limitations do not make linked lists obsolete; they clarify the situations in which their flexibility is valuable.

Chapter Summary

Linked data structures represent collections as nodes connected by references. A singly linked list stores a successor link and is simple and memory-efficient. A doubly linked list stores predecessor and successor links, enabling reverse traversal and efficient deletion of a known node. A circular list connects its final node to its first and is useful for repeated rotation, but traversal requires an explicit stopping condition.

Front insertion and deletion are generally Θ(1), while search and indexed access are Θ(n). Rear operations depend on whether a tail reference is maintained and on the list type. Linked lists avoid element shifting but use extra references and usually have poorer locality than arrays. Reliable implementations preserve links before overwriting them, handle empty and one-node cases, maintain structural invariants, and encapsulate mutation. Appropriate applications include queues, schedulers, histories, graph representations, and cyclic processing systems.

Key Terms

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

Reference: A value identifying another object in memory.

Head: Reference to the first node.

Tail: Reference to the last node.

Singly linked list: A list whose nodes contain forward links only.

Doubly linked list: A list whose nodes contain previous and next links.

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

Traversal: Systematic visiting of nodes in link order.

Successor: The node reached through a next link.

Predecessor: The node immediately before a given node.

Invariant: A condition that must remain true for a valid structure.

Null link: A reference that points to no node.

Sentinel node: A dummy node used to simplify boundary cases.

Random access: Direct access to an element by position.

Asymptotic complexity: Analysis of how resource use grows with input size.

Pointer chasing: Following references through separate nodes.

Round-robin scheduling: Repeatedly serving items in cyclic order.

Iterator: An object or protocol used to traverse a collection.

Review Questions

Short Answer Questions

1. What information does a node in a singly linked list normally contain?
2. Why is a tail reference useful in a linked list?
3. How does a doubly linked list differ from a singly linked list?
4. Why must circular-list traversal use a special stopping condition?
5. State one advantage and one disadvantage of linked lists compared with arrays.

Long Answer Questions

1. Explain the algorithm for inserting a node after a known node in a singly linked list. Include the order in which references should be changed.
2. Describe deletion of a known node from a doubly linked list, including all boundary cases.
3. Compare singly linked, doubly linked, and circular lists for a round-robin scheduling application.
4. Explain how head, tail, and size invariants support reliable list implementation.
5. Discuss why asymptotic complexity alone is insufficient when comparing linked lists with dynamic arrays.

Analytical / Application Questions

1. Design a data structure for browser back-and-forward navigation. Justify whether a doubly linked list, singly linked list, or another structure is most appropriate.
2. A circular list contains one node and its tail.next does not refer to tail. Identify the violated invariant and describe a repair strategy.
3. A system frequently deletes known items and traverses in both directions but rarely accesses by index. Choose a structure and explain the time and memory trade-offs.

Multiple Choice Questions with Answers

Question 1

Which reference identifies the first node in a linked list?

A. head

B. tail

C. prev

D. size

Correct Answer: A. head

Question 2

What is the time complexity of inserting at the front of a singly linked list when the head is known?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: A. Θ(1)

Question 3

Which additional link is stored by each ordinary doubly linked-list node?

A. A link to the array index

B. A predecessor link

C. A link to the list size

D. A link to the next list

Correct Answer: B. A predecessor link

Question 4

Why can a null-based loop fail when traversing a circular list?

A. Circular nodes contain no values

B. The list always has zero nodes

C. No successor link reaches null

D. The head cannot be stored

Correct Answer: C. No successor link reaches null

Question 5

With a maintained tail reference, what is the time complexity of inserting at the rear of a singly linked list?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: A. Θ(1)

Question 6

What must normally be known to delete a later node from a singly linked list efficiently?

A. The list capacity

B. The target's predecessor

C. The array index of the target

D. The node's memory size

Correct Answer: B. The target's predecessor

Question 7

Which structure is most suitable for repeated movement from the last item directly to the first?

A. A circular linked list

B. A sorted array only

C. A singly linked list with a null tail

D. An isolated node

Correct Answer: A. A circular linked list

Question 8

A list contains values 4 → 7 → 4 → 9 → 7. After retaining only the first occurrence of each value, what is the result?

A. 4 → 7 → 9

B. 7 → 4 → 9

C. 4 → 4 → 7 → 7 → 9

D. 9 → 7 → 4

Correct Answer: A. 4 → 7 → 9

Question 9

What is a major practical disadvantage of linked lists compared with dynamic arrays?

A. They cannot store duplicate values

B. They require contiguous memory for every node

C. They usually have poorer cache locality

D. They cannot grow after construction

Correct Answer: C. They usually have poorer cache locality

Question 10

Which action helps prevent losing the remainder of a list during insertion?

A. Clear the head first

B. Save or assign the new node's successor before overwriting the predecessor link

C. Set every link to null

D. Change the size before creating the node

Correct Answer: B. Save or assign the new node's successor before overwriting the predecessor link