5. Linked Data Structures

Introduction and Context

Arrays provide direct access to elements because their items occupy consecutive memory locations. That advantage is accompanied by a structural constraint: inserting or removing an item in the middle may require many elements to be shifted, and the array normally needs a predetermined capacity. Linked data structures address these limitations by representing a collection as separately allocated objects connected through pointers.

A linked list is therefore not merely an alternative syntax for an array. It is a different representation strategy. Each element, commonly called a node, stores data and one or more links to other nodes. The links determine the logical order, while the physical locations of nodes in memory may be unrelated. This separation between logical order and physical placement makes linked structures useful when the size of a collection changes frequently or when insertion and deletion are central operations.

This chapter develops singly linked, doubly linked, circular, and sentinel-based lists in C. It also considers algorithmic complexity, generic data representation, memory safety, reversal, merging, testing, and practical design choices. The discussion assumes familiarity with pointers, structures, dynamic memory allocation, and asymptotic analysis.

Learning Objectives

After studying this chapter, a learner should be able to:

1. Explain the representation and invariants of major linked-list variants.

2. Design and implement insertion, deletion, traversal, reversal, and merging operations in C.

3. Compare linked structures with arrays and with one another using time, space, and locality considerations.

4. Develop memory-safe and reusable list implementations, including generic variants.

5. Select an appropriate list representation for a practical software system.

6. Diagnose pointer, ownership, boundary, and lifetime errors through systematic reasoning.

The Node, the Link, and the Representation Invariant

A basic singly linked node can be declared as follows:

```c

#include <stddef.h>

#include <stdlib.h>

typedef struct Node {

int data;

struct Node *next;

} Node;

```

A list is usually represented by a pointer named `head`. If the list is empty, `head == NULL`. Otherwise, `head` points to the first node, whose `next` field points to the second node, and so on. The final node has `next == NULL`.

A useful representation invariant for a non-circular singly linked list is:

• `head` is either `NULL` or points to a valid allocated node.
• Following `next` links eventually reaches `NULL`.
• Every node is reachable from `head` exactly once.
• No link points to a node that has already been freed.

These statements are more important than the code itself. They provide conditions against which every operation can be checked. A pointer assignment that appears syntactically correct may still violate an invariant by losing a sublist, creating a cycle accidentally, or retaining a pointer to released memory.

A list can also maintain metadata such as a tail pointer and a count:

```c

typedef struct {

Node *head;

Node *tail;

size_t size;

} List;

```

The additional fields improve some operations but create additional obligations. For example, an empty list must satisfy `head == NULL`, `tail == NULL`, and `size == 0`; after deletion of the final element, all three fields must again be updated consistently.

Singly Linked Lists: Operations and Reasoning

Construction and Traversal

A node is commonly created by allocating memory, assigning its data, and initializing its link:

```c

Node *node_create(int value) {

Node p = malloc(sizeof p);

if (p != NULL) {

p->data = value;

p->next = NULL;

}

return p;

}

```

A traversal follows links until `NULL` is encountered:

```c

void list_print(const Node *head) {

for (const Node *p = head; p != NULL; p = p->next)

printf("%d ", p->data);

}

```

Traversal takes Θ(n) time for a list of n nodes and Θ(1) auxiliary space when performed iteratively. Unlike array traversal, it does not provide constant-time access to the ith element; finding that element requires following i links.

Insertion at the Front and After a Node

Front insertion is particularly efficient. The new node first points to the current head, and then the head is changed:

```c

int push_front(Node **head, int value) {

Node *p = node_create(value);

if (p == NULL) return 0;

p->next = *head;

*head = p;

return 1;

}

```

The double pointer is necessary because the operation may change the caller's head pointer. If a node `p` is already known and a new node `q` must follow it, the safe order is:

```c

q->next = p->next;

p->next = q;

```

Reversing these assignments can lose the remainder of the list. Insertion itself is Θ(1) after the location has been found, but locating a position by index is Θ(n).

Deletion

To delete the first node, save the successor before freeing the node:

```c

int pop_front(Node *head, int out) {

if (head == NULL || *head == NULL) return 0;

Node old = head;

if (out != NULL) *out = old->data;

*head = old->next;

free(old);

return 1;

}

```

Deleting a node after a predecessor `prev` requires bypassing the target, saving its address, and then releasing it:

```c

void delete_after(Node *prev) {

if (prev == NULL || prev->next == NULL) return;

Node *victim = prev->next;

prev->next = victim->next;

free(victim);

}

```

A singly linked list cannot generally delete an arbitrary node in Θ(1) time when given only that node, because its predecessor is needed to repair the incoming link. This is a fundamental consequence of one-directional linkage.

Reversal

Iterative reversal uses three pointers: `previous`, `current`, and `next`.

```c

void reverse(Node **head) {

Node *previous = NULL;

Node current = head;

while (current != NULL) {

Node *next = current->next;

current->next = previous;

previous = current;

current = next;

}

*head = previous;

}

```

At every iteration, `next` preserves access to the unprocessed suffix before `current->next` is changed. The algorithm is Θ(n) in time and Θ(1) in auxiliary space. A recursive version is conceptually elegant but consumes Θ(n) call-stack space and may be unsuitable for very long lists.

Merging Sorted Lists

Two sorted singly linked lists can be merged without allocating new nodes. At each step, the smaller front node is detached from one input and attached to the output. A dummy or sentinel node simplifies the first-insertion case:

```c

Node merge_sorted(Node a, Node *b) {

Node dummy = {0, NULL};

Node *tail = &dummy;

while (a != NULL && b != NULL) {

if (a->data <= b->data) {

tail->next = a; a = a->next;

} else {

tail->next = b; b = b->next;

}

tail = tail->next;

}

tail->next = (a != NULL) ? a : b;

return dummy.next;

}

```

The merge is Θ(m+n), stable when equal values from `a` are selected first, and uses Θ(1) extra space. It transfers ownership of the input nodes to the result; the caller must not later destroy the same nodes through the old list heads.

Doubly Linked Lists

A doubly linked node contains both successor and predecessor links:

```c

typedef struct DNode {

int data;

struct DNode *prev;

struct DNode *next;

} DNode;

```

For a non-circular doubly linked list, the invariants include `head->prev == NULL`, `tail->next == NULL`, and, for every adjacent pair, `x->next == y` if and only if `y->prev == x`. These bidirectional relationships make deletion and reverse traversal easier, but every insertion or deletion must update more pointers.

To insert `x` between `left` and `right`, where either boundary may be absent, the general link changes are:

```c

x->prev = left;

x->next = right;

if (left != NULL) left->next = x;

if (right != NULL) right->prev = x;

```

A list object should then update `head` if `left` is absent and `tail` if `right` is absent. Deleting node `x` similarly reconnects its neighbors:

```c

if (x->prev != NULL) x->prev->next = x->next;

else list->head = x->next;

if (x->next != NULL) x->next->prev = x->prev;

else list->tail = x->prev;

free(x);

```

Given a valid node pointer, deletion is Θ(1), unlike ordinary singly linked deletion. The cost is an additional pointer per node, more writes, and greater risk of inconsistent links. Doubly linked lists are useful for browser history, editor undo/redo chains, LRU caches, and deques, especially when nodes are frequently removed from known positions.

Circular Lists and Sentinel-Based Design

In a circular singly linked list, the last node points back to the first rather than to `NULL`. A representation using a tail pointer is often convenient: the head is `tail->next`. An empty circular list has `tail == NULL`. A one-node list satisfies `tail->next == tail`.

Traversal must use a stopping condition based on returning to the starting node:

```c

if (tail != NULL) {

Node *start = tail->next;

Node *p = start;

do {

printf("%d ", p->data);

p = p->next;

} while (p != start);

}

```

Testing `p != NULL` would never terminate. Circular structures are appropriate for round-robin scheduling, cyclic buffers, repeated playlists, and Josephus-type algorithms.

A sentinel is a permanent dummy node used to remove special cases at boundaries. In a singly linked list with a dummy head, the actual first node is `sentinel.next`; insertion after the sentinel is the same kind of operation as insertion after any other node. In a circular doubly linked list, one sentinel can represent both ends:

• an empty list has `sentinel.next == &sentinel` and `sentinel.prev == &sentinel`;
• the first data node is `sentinel.next`;
• the last data node is `sentinel.prev`.

Every insertion and deletion occurs between two existing nodes. This uniformity substantially reduces branches and makes correctness proofs clearer. The sentinel is not data and must never be freed as if it were an ordinary node.

Circular and sentinel-based designs are related but not identical. A circular list describes the link topology; a sentinel describes a boundary-management technique. They may be used separately or together.

Generic Linked Lists in C

An integer-specific list is simple but not reusable. A generic list can store a `void *` payload:

```c

typedef struct GNode {

void *data;

struct GNode *next;

} GNode;

typedef void (DestroyFn)(void );

typedef int (CompareFn)(const void , const void *);

```

The list must define ownership clearly. Under borrowed ownership, the list stores addresses but does not free the payloads. Under owned ownership, the list invokes a destructor when a node is removed or the list is destroyed. Mixing these policies causes leaks or double frees.

A generic destructor might be:

```c

void gnode_destroy(GNode *p, DestroyFn destroy) {

if (p != NULL) {

if (destroy != NULL) destroy(p->data);

free(p);

}

}

```

A generic comparison function allows sorting or searching without embedding assumptions about the payload type. Caution is required with `void *`: it removes compile-time type checking, so the programmer must ensure that each payload is interpreted according to the correct type and remains alive for as long as the list references it.

An alternative is to embed a flexible byte array or use macros to generate type-specific lists. Type-specific code is often safer and faster, whereas `void *` offers a common interface. In modern C projects, generic interfaces should document ownership, nullability, mutation, thread-safety, and error behavior explicitly.

Complexity and Design Trade-offs

The following asymptotic view assumes a maintained tail pointer where relevant and a node pointer is already available for local insertion or deletion.

| Operation | Singly linked | Doubly linked | Typical array |

|---|---:|---:|---:|

| Access by index | Θ(n) | Θ(n) | Θ(1) |

| Insert at front | Θ(1) | Θ(1) | Θ(n) |

| Delete at front | Θ(1) | Θ(1) | Θ(n) |

| Insert at known node | Θ(1) after predecessor | Θ(1) | Θ(n) |

| Delete at known node | Usually needs predecessor | Θ(1) | Θ(n) |

| Search | Θ(n) | Θ(n) | Θ(n), often better locality |

| Merge sorted lists | Θ(m+n) | Θ(m+n) | Usually requires movement or new storage |

Big-O notation alone does not settle the choice. Linked lists allocate each node separately, producing allocator overhead and poor cache locality. Arrays often traverse faster despite occasional expensive insertions because neighboring elements are cache-friendly. Linked lists are justified when stable node addresses, frequent local modifications, unbounded incremental growth, or splicing operations matter more than indexed access and locality.

Correctness, Memory Safety, and Testing

The most common linked-list faults are losing a successor before reconnecting links, dereferencing `NULL`, freeing a node and then reading it, freeing a payload that the list does not own, and failing to update head, tail, or size metadata. Boundary cases deserve deliberate tests: empty list, one-node list, insertion at both ends, deletion of the only node, repeated deletion, duplicate values, and reversal of an empty or singleton list.

A practical test strategy combines ordinary assertions with dynamic analysis. After each mutating operation, a debug validator can count nodes, verify bidirectional links, check that a recorded tail is reachable, and detect cycles using Floyd's tortoise-and-hare algorithm when a cycle is not expected. Tools such as AddressSanitizer and UndefinedBehaviorSanitizer can reveal use-after-free, buffer errors, invalid shifts, and related defects during testing.

A list destructor should repeatedly remove nodes and free them exactly once. It should be safe for an empty list and should reset the list object to its empty invariant. In multithreaded systems, a list is not automatically thread-safe merely because pointer operations are small. External locking, ownership protocols, or specialized lock-free algorithms are required; lock-free reclamation introduces advanced hazards such as ABA and premature memory reclamation.

Applied Case: A Round-Robin Job Scheduler

Background

Consider an illustrative operating-system laboratory scheduler that maintains jobs in cyclic order. Each job has an identifier, required service time, and a remaining-time field. After receiving a fixed time quantum, an unfinished job goes to the back of the cycle; a completed job is removed.

Situation and Analysis

A linear list would require a special operation to move from the final job back to the first. A circular singly linked list with a tail pointer naturally represents the schedule: the next job is `tail->next`. Removing the next job requires changing the tail's successor, while moving a completed or serviced job to the end can be achieved by advancing the tail pointer when the node remains in the cycle.

The scheduler must distinguish three states: no jobs, one job, and multiple jobs. In a one-node cycle, removal sets the tail to `NULL`; it must not leave a pointer to freed memory. Since the scheduler visits each active job once per round, a circular traversal must stop after returning to its starting node or after processing a known count of jobs.

Approach and Outcome

The design stores the tail pointer and an active-job count. Insertion into an empty queue makes the new node point to itself. Insertion into a nonempty queue places the node after the tail and then makes it the new tail. Processing uses `tail->next`, the logical front. If the job completes, the front node is bypassed and freed; otherwise, the tail advances to the processed node. Each local update is constant time, and one complete round costs Θ(n).

Learning Points

The case demonstrates that topology should follow behavior. Circularity eliminates end-of-list special handling for repeated rotation, while a tail pointer gives constant-time access to both the next job and the insertion position. It also shows why ownership, termination conditions, and singleton handling must be specified before implementation.

Professional and Emerging Considerations

Linked structures remain important in operating-system queues, memory allocators, graph adjacency representations, compilers, caches, event systems, and embedded software. Production implementations increasingly consider allocator behavior, cache locality, memory pools, and intrusive lists. An intrusive list stores link fields inside the application object, avoiding a separate node allocation; it is efficient but couples the object to a particular list organization and requires careful lifetime management.

Security and governance concerns are also relevant. Corrupted links can produce denial of service, arbitrary memory access, or data-structure traversal outside intended bounds. Input-derived sizes and payloads must be validated, allocation failures must be handled, and cleanup paths must be tested. In safety-critical or regulated software, ownership rules, invariants, review evidence, and static-analysis results should be documented rather than left implicit.

Current practice favors hybrid structures when workloads demand both locality and flexible updates. Examples include unrolled linked lists, chunked lists, intrusive containers, and pooled nodes. These designs reduce per-node allocation overhead while preserving some insertion flexibility. The correct choice remains empirical: measure access patterns, allocation cost, mutation frequency, memory limits, and concurrency requirements rather than selecting a linked list solely because insertion is theoretically constant time.

Best-Practice Checklist

• State the ownership policy for nodes and payloads.
• Define empty, singleton, head, tail, and size invariants.
• Save successor pointers before overwriting links.
• Use double pointers when an operation may change the head.
• Update all affected metadata on every mutation.
• Prefer sentinels when boundary cases dominate the code.
• Use explicit termination logic for circular structures.
• Free each allocation exactly once and never access it afterward.
• Test structural edge cases and run sanitizers.
• Choose lists for their workload characteristics, not for asymptotic notation alone.

Chapter Summary

Linked data structures represent logical order through pointers rather than contiguous storage. Singly linked lists provide economical forward traversal and constant-time front operations; doubly linked lists support reverse traversal and constant-time deletion when a node is known. Circular lists encode repeated successor relationships, while sentinel nodes simplify boundary operations by replacing absent neighbors with a permanent dummy node. Core algorithms include traversal, insertion, deletion, reversal, and stable sorted merging. Their correctness depends on preserving representation invariants and their safety depends on disciplined allocation, ownership, and reclamation. Generic `void *` designs improve reuse but require explicit type and lifetime contracts. In professional systems, cache behavior, allocator overhead, concurrency, security, and testing are as important as asymptotic complexity.

Key Terms

Node: An allocated record containing data and one or more links.

Link: A pointer field connecting one node to another.

Head: The pointer identifying the first node of a list.

Tail: The pointer identifying the final node, when maintained.

Singly linked list: A list whose nodes contain links in one direction.

Doubly linked list: A list whose nodes contain both successor and predecessor links.

Circular list: A list in which the final link returns to the first node.

Sentinel: A permanent dummy node used to simplify boundary operations.

Traversal: Systematic visitation of nodes by following links.

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

Ownership: The responsibility for managing the lifetime and release of an object.

Payload: The application data stored or referenced by a node.

Splicing: Transferring or reconnecting a sequence of nodes without copying them.

Stable merge: A merge that preserves the relative order of equal-key elements.

Intrusive list: A list whose link fields are embedded in application objects.

Dangling pointer: A pointer referring to memory whose lifetime has ended.

Cache locality: The tendency of accessed data to be located near recently accessed data.

Generic list: A list designed to handle values of different types through an abstraction such as `void *`.

Review Questions

Short Answer Questions

1. Why does insertion at the front of a singly linked list require a pointer to the head pointer?

2. State two representation invariants for a non-circular singly linked list.

3. Why can a doubly linked list delete a known node in constant time?

4. What termination condition should be used when traversing a circular list?

5. Distinguish borrowed ownership from owned ownership in a generic list.

Long Answer Questions

1. Explain and implement the iterative reversal of a singly linked list, including its invariant and complexity.

2. Compare singly linked, doubly linked, circular, and sentinel-based lists in terms of structure, operations, and suitable applications.

3. Describe the stable merge of two sorted linked lists and explain why it can be performed without allocating new data nodes.

4. Design the insertion and deletion operations for a circular doubly linked list with one sentinel node.

5. Discuss the memory-safety obligations of a generic `void *` linked list implementation.

Analytical / Application Questions

1. A list maintains `head`, `tail`, and `size`. After deleting its only node, which fields must change, and what invariant should be restored?

2. A scheduler repeatedly selects the next job and moves unfinished jobs to the end. Choose a suitable list representation and justify the choice, including the singleton case.

3. A workload performs millions of indexed reads and occasional middle insertions. Evaluate whether a linked list is appropriate, considering both asymptotic complexity and cache locality.

22. Multiple Choice Questions with Answers

Question 1

Which operation fundamentally requires access to the predecessor in an ordinary singly linked list?

A. Reading the first node

B. Deleting a node when only the target node is known

C. Traversing from the head

D. Inserting a new first node

Correct Answer: B. Deleting a node when only the target node is known

Question 2

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

A. To preserve access to the unprocessed suffix

B. To calculate the list size

C. To identify the tail permanently

D. To prevent allocation failure

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

Question 3

For a non-circular doubly linked list, which condition must hold at the head?

A. head->next == NULL

B. head->prev == head

C. head->prev == NULL

D. head->next == head

Correct Answer: C. head->prev == NULL

Question 4

What is the correct general stopping condition for a traversal of a circular list beginning at start?

A. p == NULL

B. p->next == NULL

C. p == start after at least one visit

D. p->prev == NULL

Correct Answer: C. p == start after at least one visit

Question 5

What is the principal purpose of a sentinel node?

A. To store the largest data value

B. To eliminate many boundary special cases

C. To guarantee constant-time indexed access

D. To replace dynamic allocation entirely

Correct Answer: B. To eliminate many boundary special cases

Question 6

Two sorted singly linked lists contain m and n nodes. What is the time complexity of merging them by relinking existing nodes?

A. Θ(1)

B. Θ(log(m+n))

C. Θ(mn)

D. Θ(m+n)

Correct Answer: D. Θ(m+n)

Question 7

A generic list stores payloads using void pointers. Which issue must its interface explicitly define?

A. The CPU instruction set

B. Whether the list owns and frees payloads

C. The array index of every node

D. That all payloads are integers

Correct Answer: B. Whether the list owns and frees payloads

Question 8

Which representation is especially suitable for a round-robin scheduler that repeatedly moves to the next job?

A. A circular list with a tail pointer

B. A singly linked list whose last link is always NULL

C. A sorted array only

D. A binary search tree

Correct Answer: A. A circular list with a tail pointer

Question 9

What is a likely result of freeing a node and then reading its next field?

A. Automatic list reversal

B. A guaranteed NULL value

C. Use-after-free and undefined behavior

D. A valid tail update

Correct Answer: C. Use-after-free and undefined behavior

Question 10

Why might an array outperform a linked list even when the list has theoretically efficient insertion?

A. Arrays never require memory

B. Arrays generally provide better cache locality

C. Linked lists always use Θ(n²) insertion

D. Arrays cannot be traversed

Correct Answer: B. Arrays generally provide better cache locality