Linked Structures

Introduction

A linked structure stores a collection of elements in separate memory objects connected by references, commonly called links or pointers. Unlike an array, whose elements normally occupy consecutive memory locations, a linked structure can grow, shrink, and reorganize without moving an entire block of elements. This flexibility makes linked structures important in operating systems, compilers, network software, databases, graph representations, memory managers, and many application-level libraries.

The central design problem is not merely creating a node. It is maintaining correct relationships among nodes while respecting memory allocation, ownership, lifetime, and performance requirements. A single incorrect pointer assignment can disconnect part of a structure, create a cycle unintentionally, or cause access to released memory.

This chapter examines singly linked lists, doubly linked lists, circular lists, and sentinel-based lists. It also compares their complexity and application trade-offs and develops systematic techniques for safe pointer manipulation.

Learning Objectives

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

• Explain the representation and invariants of linked structures.
• Design singly, doubly, circular, and sentinel-based linked lists.
• Insert, delete, search, and traverse nodes safely.
• Analyze time and space complexity for common operations.
• Explain memory allocation, ownership, aliasing, and lifetime issues.
• Select an appropriate linked structure for a practical application.
• Diagnose common pointer and reference errors.

1. Fundamental Model

A linked list consists of nodes. Each node contains data and one or more links to other nodes. In a singly linked list, a node has the conceptual form:

Node {
    data
    next
}

The list itself usually stores a reference called head, which identifies the first node. An empty list has head = null. The final node has next = null in a non-circular list.

A list can be described as a sequence:

L = (n₁, n₂, ..., n_k)

where n_i is a node and k is the number of nodes. The sequence order is determined by links, not by physical memory addresses.

Essential invariants

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

1. head is either null or refers to a valid node owned by the list.
2. Every reachable node is well-formed.
3. In a linear singly linked list, exactly one reachable node has next = null.
4. No node is unintentionally reachable more than once unless sharing is explicitly designed.
5. A stored size value equals the number of reachable nodes.

For a doubly linked list, additional conditions apply:

• If x.next = y, then y.prev = x.
• If x.prev = y, then y.next = x.
• The first node has no predecessor, and the last node has no successor, unless the list is circular.

These invariants are more important than any particular implementation language because they define correctness.

2. Memory, References, and Ownership

A linked node is normally allocated dynamically. Allocation reserves storage, while deallocation returns it to the memory manager. The exact operations depend on the language: C uses functions such as malloc and free, C++ may use new and delete, and managed languages use object allocation with automatic garbage collection.

Three concepts must be distinguished:

• Reference or pointer: a value identifying another object or memory location.
• Aliasing: two or more references identify the same node.
• Ownership: responsibility for determining how long an object remains valid and who eventually releases it.

Consider two list variables that point to the same first node. They are aliases, not independent copies. Deleting through one list may invalidate the other in a manually managed language. A deep copy creates new nodes; a shallow copy duplicates references only.

A robust interface should state whether an operation transfers ownership, borrows nodes temporarily, or copies data. In modern software engineering, ownership may be enforced through smart pointers, borrowing rules, or garbage collection, but the conceptual obligation remains: a link must never be used after its target has ceased to exist.

Memory overhead

If each singly linked node stores data requiring d bytes and a link requiring p bytes, the payload-independent node size is approximately d + p bytes, ignoring alignment and allocator metadata. A doubly linked node requires two links, approximately d + 2p bytes before alignment. Thus, linked structures trade additional memory overhead for structural flexibility.

3. Singly Linked Lists

Representation

A singly linked list supports movement in one direction. A typical implementation stores head and optionally tail and size.

head → [data | next] → [data | next] → [data | null]

A tail reference is useful when append operations are frequent. Without it, appending requires traversal from the head.

Traversal

Traversal begins at head and repeatedly follows next until null is reached.

current = head
while current ≠ null:
    process(current.data)
    current = current.next

If the list contains n nodes, traversal takes Θ(n) time and O(1) auxiliary space when performed iteratively.

Insertion at the front

To insert node q before the current head:

q.next = head
head = q

The order is essential. Assigning head = q first without saving or linking the old head would disconnect the existing list. The operation takes Θ(1) time.

Insertion after a known node

If p is a valid node in the list and q is new:

q.next = p.next
p.next = q

The new node must first receive the old successor. Otherwise the old suffix may be lost. Given p, the operation is Θ(1); finding p by value may require Θ(n) time.

Deletion after a known predecessor

If p.next is the node to remove:

victim = p.next
p.next = victim.next
deallocate(victim)

The predecessor is crucial. A singly linked list cannot move backward from a node to its predecessor without additional information.

To delete the first node:

victim = head
head = head.next
deallocate(victim)

The operation must handle the empty-list case and, if a tail is stored, update tail when the final node is removed.

Complexity

These are asymptotic bounds. They describe growth as n increases and do not predict exact running time on a particular machine.

4. Doubly Linked Lists

A doubly linked node contains prev, data, and next.

null ← [prev | data | next] ⇄ [prev | data | next] → null

The additional backward link supports reverse traversal and deletion when a node itself is known.

Insertion between two nodes

To insert q between a and b, where a.next = b and b.prev = a:

q.prev = a
q.next = b
a.next = q
b.prev = q

All four assignments are necessary. A useful practice is to establish the new node's links before changing the surrounding nodes, reducing the chance of losing access to the original successor or predecessor.

Deleting a known node

For a node q with predecessor a and successor b:

q.prev.next = q.next
q.next.prev = q.prev
deallocate(q)

Boundary cases require special handling when q is the first or last node. Sentinel nodes, discussed later, can eliminate many such tests.

Doubly linked lists use more memory and require more pointer updates than singly linked lists. Their benefit is that deletion of a known node is constant time and traversal can proceed in either direction. Searching still takes linear time.

5. Circular Linked Lists

In a circular list, the final node links back to the first. There is no null link marking the end.

A circular singly linked list can be represented efficiently by a tail reference. The head is then tail.next.

┌──────────────────────────────┐
        ↓                              │
head → [data|next] → [data|next] → [data|next]

Traversal must stop when the starting node is encountered again, not when a null reference appears:

if tail ≠ null:
    start = tail.next
    current = start
    repeat:
        process(current.data)
        current = current.next
    until current = start

An empty circular list has tail = null. A one-node list has tail.next = tail.

Circular structures are useful for round-robin scheduling, cyclic buffers, repeated playlists, and token-passing systems. They also introduce a major hazard: an incorrect loop condition can become infinite. Debugging and validation should therefore include a traversal limit or node-count invariant when appropriate.

A circular doubly linked list has both next and prev links. The first node's predecessor is the last node, and the last node's successor is the first node.

6. Sentinel-Based Lists

A sentinel is a distinguished node that does not represent an ordinary data element. It serves as a permanent boundary or anchor. A common design uses a dummy head sentinel:

sentinel ⇄ first data node ⇄ ... ⇄ last data node

In a circular doubly linked list with one sentinel, an empty list has:

sentinel.next = sentinel
sentinel.prev = sentinel

Insertion and deletion can then use uniform logic. To insert q immediately before b:

q.prev = b.prev
q.next = b
b.prev.next = q
b.prev = q

This works whether b is an ordinary node or the sentinel. To remove q:

q.prev.next = q.next
q.next.prev = q.prev

The sentinel itself must never be removed. Sentinel-based designs reduce boundary-condition code, which often improves reliability, although they consume a small amount of additional memory and require programmers to understand that the sentinel is not data.

7. Correctness Through Pointer Discipline

Pointer manipulation is best understood as a sequence of local transformations. Before changing links, identify the nodes whose references will be overwritten. Preserve every needed reference before it is lost.

A practical procedure is:

1. State the precondition, such as “p belongs to this list.”
2. Draw the local neighborhood before modification.
3. Save successor and predecessor references if they will be overwritten.
4. Connect the new or bypassing links.
5. Update head, tail, or size when required.
6. Deallocate or release removed nodes only after they are unreachable from the list.
7. Check invariants.

Example: inserting at the front

Suppose the original structure is head → A → B. To insert Q, first set Q.next = head, producing Q → A → B, and then set head = Q. The old sequence remains reachable throughout the transformation.

Common failures

• Lost suffix: assigning p.next = q before storing the old p.next.
• Dangling reference: freeing a node while another live reference still points to it.
• Broken backward link: updating a.next but not the corresponding b.prev.
• Incorrect empty case: dereferencing null when the list has no nodes.
• Stale tail: removing the final node but leaving tail pointing to released storage.
• Accidental cycle: linking a node to an earlier node when a linear list is intended.
• Infinite traversal: looking for null in a circular list.

Assertions and invariant-checking functions are valuable during development. For example, a doubly linked list checker can verify every adjacent pair in both directions and compare the counted nodes with the stored size.

8. Complexity and Application Trade-offs

Linked lists provide constant-time insertion or deletion only when the relevant position or neighboring node is already known. They do not provide constant-time random access. An array can access position i directly in constant time, whereas a linked list must follow links from an endpoint.

Cache behavior is also important. Arrays often outperform linked lists in traversal because array elements are contiguous and make better use of processor caches. Therefore, asymptotic complexity alone should not determine a design. Memory overhead, locality, allocation cost, concurrency requirements, and operation patterns must be considered.

9. Worked Design Example: A Task Scheduler

Consider a cooperative operating-system simulation in which tasks receive a fixed time slice in round-robin order. After a task runs, it moves to the next task; when the final task runs, control returns to the first.

A circular singly linked list is a natural representation. Store a tail pointer. The next task to run is tail.next. To remove the current task, locate its predecessor, redirect the predecessor's next to the current task's successor, and update tail if the removed task was the tail. If only one task remains, removal sets tail = null.

Background

The scheduler needs repeated cycling, insertion of newly ready tasks, and removal of completed tasks.

Problem

A linear list would require returning from the final node to the head through a separate conditional branch. It could work, but the cycle is conceptually central and should be represented directly.

Approach

Use a circular singly linked list with a tail pointer. The empty state is tail = null; the one-task state is tail.next = tail.

Appending a new task after the tail requires constant time:

new.next = tail.next
 tail.next = new
tail = new

The spaces in the pseudocode are illustrative; the critical order is that the new node first points to the old head, then the old tail points to the new node, and finally the tail reference advances.

Outcome

Appending is Θ(1), and obtaining the next task is Θ(1). Removing an arbitrary task remains Θ(n) in a singly linked design because its predecessor must be found. If task handles directly identify nodes and constant-time arbitrary removal is required, a circular doubly linked list may be preferable.

Learning points

The representation should reflect the application’s natural progression. The design also illustrates that one optimization may create another cost: a tail pointer makes append efficient, but singly linked deletion still requires a predecessor search.

10. Professional, Ethical, and Contemporary Considerations

Linked structures are foundational in production systems, but unsafe memory handling can create security vulnerabilities. Use-after-free, double-free, buffer-adjacent corruption, and memory leaks may lead to crashes or arbitrary code execution. Secure development practices include ownership documentation, automated memory checking, sanitizers, code review, defensive assertions, and tests for empty, singleton, and repeated-operation cases.

Managed languages reduce some lifetime errors but do not eliminate logical errors such as accidental cycles, unbounded retention, or unintended aliasing. In concurrent systems, pointer updates require synchronization or specialized lock-free techniques. A naïve multi-threaded insertion can lose updates even if each individual assignment is correct in a single-threaded context.

Modern implementations often use standard library containers rather than hand-written lists. The professional skill is knowing when a specialized structure is justified and when a tested library abstraction is safer. AI-assisted programming can generate plausible pointer code, but generated code must be reviewed against invariants, ownership rules, complexity requirements, and language-specific memory semantics. Confidence in output is not evidence of correctness.

Best Practices

• Define empty, singleton, and multi-node behavior explicitly.
• Keep ownership rules clear and document whether operations copy or transfer nodes.
• Prefer sentinel nodes when they substantially simplify boundary logic.
• Maintain size only if its update cost and invariant can be controlled.
• Use a tail pointer when append is common.
• Test every operation after insertion and deletion at each boundary.
• Avoid exposing internal nodes unnecessarily.
• Use library containers unless a custom structure provides a demonstrated benefit.
• Measure practical performance, including allocation and cache effects.

Chapter Summary

Linked structures represent sequences through dynamically allocated nodes and links. Singly linked lists use one forward link and are economical, but backward movement and deletion by node are limited. Doubly linked lists add a predecessor link, enabling reverse traversal and constant-time deletion of a known node at the cost of memory and update complexity. Circular lists connect the final node to the first and are effective for repeated cyclic processing, but traversal must use a stopping condition other than null. Sentinel nodes provide permanent boundary objects that simplify insertion and deletion and reduce special cases.

Correct design depends on invariants, careful assignment order, memory lifetime, ownership, and aliasing. Linked lists offer flexible structural modification but poor indexed access and often inferior cache locality compared with arrays. Selecting a representation therefore requires analysis of operation patterns, memory constraints, safety requirements, and application semantics.

Key Terms

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

Link: A reference or pointer connecting one node to another.

Head: Reference to the first node of a list.

Tail: Reference to the final node, when maintained.

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

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

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

Sentinel: A dummy boundary node that does not represent ordinary data.

Traversal: Visiting nodes according to their links.

Invariant: A condition that remains true for a valid structure.

Aliasing: The existence of multiple references to the same object.

Ownership: Responsibility for an object’s lifetime and release.

Dangling reference: A reference to an object that is no longer valid.

Memory leak: Allocated storage that is no longer reachable but has not been released.

Deep copy: A copy that creates independent nodes or objects.

Shallow copy: A copy that duplicates references rather than target objects.

Asymptotic complexity: A description of resource growth as input size increases.

Cache locality: The tendency of related data to be stored near one another in memory.

Review Questions

Short Answer Questions

1. What is the purpose of a head reference in a linked list?
2. Why must a circular list use a different traversal stopping condition from a linear list?
3. State two invariants of a doubly linked list.
4. What is the difference between aliasing and deep copying?
5. Why can insertion after a known node be constant time in a singly linked list?

Long Answer Questions

1. Explain the representation, operations, advantages, and limitations of a singly linked list.
2. Compare singly and doubly linked lists with respect to memory use, traversal, insertion, and deletion.
3. Describe how a one-sentinel circular doubly linked list represents empty and non-empty states.
4. Explain the main memory-management risks in manually implemented linked structures.
5. Discuss why asymptotic complexity alone is insufficient when choosing between arrays and linked lists.

Analytical / Application Questions

1. Design a data structure for a music player that repeatedly cycles through tracks while supporting insertion and removal. Justify whether you would use a circular singly or circular doubly linked list.
2. A list loses all nodes after an insertion operation. Identify the likely pointer-assignment error and give a safe assignment sequence.
3. An application frequently deletes items when it already holds direct references to those items, and it must also traverse backward. Select an appropriate list design and analyze its time and space trade-offs.

Multiple Choice Questions with Answers

Question 1

Which operation is Θ(1) in a singly linked list when the relevant node is already known?

A. Accessing the element at position n/2

B. Inserting a node after the known node

C. Searching for a value

D. Finding the predecessor of an arbitrary node

Correct Answer: B. Inserting a node after the known node

Question 2

What link does the final node of a non-circular singly linked list contain?

A. A reference to the head

B. A reference to the tail

C. A null reference

D. A reference to a sentinel only

Correct Answer: C. A null reference

Question 3

Which additional capability does a doubly linked list provide?

A. Constant-time indexed access

B. Backward traversal

C. Automatic sorting

D. Contiguous memory allocation

Correct Answer: B. Backward traversal

Question 4

In a circular list, why is testing for null generally not a valid traversal stopping condition?

A. Circular lists cannot store data

B. The final node points back to an earlier node

C. The head is always null

D. Every node has two successors

Correct Answer: B. The final node points back to an earlier node

Question 5

What is the principal purpose of a sentinel node?

A. To store the largest data value

B. To eliminate all memory allocation

C. To simplify boundary cases

D. To provide random access

Correct Answer: C. To simplify boundary cases

Question 6

If a singly linked list has n nodes and no tail reference, what is the time complexity of appending a node?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: C. Θ(n)

Question 7

What is a dangling reference?

A. A reference to a valid head node

B. A reference to an object that is no longer valid

C. A reference used for backward traversal

D. A reference stored in a sentinel

Correct Answer: B. A reference to an object that is no longer valid

Question 8

When inserting q between a and b in a doubly linked list, which condition must hold afterward?

A. a.next = null

B. b.prev = null

C. a.next = q and q.prev = a

D. q.next = a and q.prev = b

Correct Answer: C. a.next = q and q.prev = a

Question 9

What is the typical auxiliary-space complexity of iterative traversal of a linked list?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: A. Θ(1)

Question 10

Which representation is especially natural for round-robin scheduling?

A. A circular linked list

B. A binary search tree

C. A fixed scalar variable

D. An unordered matrix

Correct Answer: A. A circular linked list