Linked Lists: short notes (Data Structures)

Revision mode

Introduction

A linked list stores a sequence as separate nodes, each holding an element and a pointer to the next node. Unlike an array, the nodes need not be contiguous, the length can change one node at a time, and inserting or deleting at a known position needs no shifting. The price is that there is no indexing: reaching the $k$ -th element means following $k$ pointers.

This note covers pointer manipulation on linked lists (what a short C function does to a list, and which assignments are needed, in which order, to insert or delete a node) and the cost of operations in singly, doubly and circular lists. It treats all three forms, the standard operations and algorithms, and their costs.

Conventions: C11; NULL ends a list; positions count from 1 at the head.

Prerequisites

Pointers: pointers to pointers.
Structures, Unions and Enumerations: self-referential structures, ->.
Dynamic Memory Allocation: malloc and free per node.

Core concepts

Node and list

struct node { int val; struct node *next; };   /* self-referential: pointer to the same type */
struct node *head = NULL;                      /* empty list */

A list is identified by a pointer to its first node. Functions that may change the first node (insert at front, delete the head) must receive struct node **, the address of the head pointer, or return the new head. Passing struct node *head by value and assigning to head inside the function changes only the local copy (Functions and Parameter Passing).

Kinds of linked list

Kind	Each node has	Last node	Typical use
Singly linked	`next`	`next == NULL`	stacks, adjacency lists
Doubly linked	`prev`, `next`	`next == NULL`; first has `prev == NULL`	deletion given a node pointer; deques; LRU lists
Circular singly	`next`	`next` points to the first node	round-robin; queue with one tail pointer
Circular doubly	`prev`, `next`	links back to first, first's `prev` to last	general-purpose lists with a sentinel

A sentinel (dummy header) node that is always present removes the special cases for the empty list and for the first node.

How it works: operations

Insertion

void push_front(struct node **head, int v) {       /* O(1) */
    struct node *n = malloc(sizeof *n);            /* allocation checks omitted for brevity */
    n->val = v; n->next = *head; *head = n;
}
void insert_after(struct node *p, int v) {         /* O(1), p != NULL */
    struct node *n = malloc(sizeof *n);
    n->val = v;
    n->next = p->next;                             /* 1: new node points to p's successor */
    p->next = n;                                   /* 2: p points to the new node */
}

Order matters. Doing step 2 before step 1 makes n->next = p->next read the new value, so n points to itself and the rest of the list is lost.

Inserting at the tail takes $O(n)$ unless a tail pointer is maintained. A compact way to walk to the end uses a pointer to the link field, which also handles the empty list:

void push_back(struct node **head, int v) {
    struct node **pp = head;
    while (*pp) pp = &(*pp)->next;                 /* pp: address of the NULL link at the end */
    *pp = malloc(sizeof **pp);
    (*pp)->val = v; (*pp)->next = NULL;
}

Deletion

To delete a node from a singly linked list you need its predecessor, because the predecessor's next must change. The pointer-to-link technique avoids a special case for the head:

int delete_val(struct node **head, int v) {        /* O(n): search, then O(1) unlink */
    struct node **pp = head;
    while (*pp && (*pp)->val != v) pp = &(*pp)->next;
    if (*pp == NULL) return 0;                     /* not found */
    struct node *dead = *pp;
    *pp = dead->next;                              /* bypass the node */
    free(dead);                                    /* then release it */
    return 1;
}

Freeing before saving dead->next would read freed memory, which is undefined behaviour.

In a doubly linked list a node can be removed given only a pointer to it, in $O(1)$ :

void dremove(struct dnode **head, struct dnode *x) {
    if (x->prev) x->prev->next = x->next; else *head = x->next;
    if (x->next) x->next->prev = x->prev;
    free(x);
}

Given only a pointer to a node $x$ in a singly list, $x$ can be "deleted" in $O(1)$ by copying the successor's value into $x$ and unlinking the successor; this fails when $x$ is the last node.

Costs compared with an array

The table gives worst-case upper bounds unless an amortised or sorted-input bound is explicitly marked. Use constant-time pointer, array-index and key-comparison operations; allocation/deallocation costs are excluded. For valid operations on nonempty lists, front insertion/deletion and insertion after a supplied node are constant time in every case. With a tail pointer, insertion at the end is also constant time; a doubly linked list additionally deletes a supplied node or the tail in constant time. A traversal to position $k$ costs $\Theta(k)$ from the head, or $\Theta(1+\min(k-1,n-k))$ from the nearer end of a doubly linked list. Under a uniformly selected position, these average $\Theta(n)$ , with best $\Theta(1)$ and worst $\Theta(n)$ . A value search stops at the first match: best $\Theta(1)$ , worst $\Theta(n)$ , and average $\Theta(n)$ for a uniformly located successful match (also $\Theta(n)$ for an unsuccessful search). Head-only end insertion and singly linked tail deletion traverse the list: $\Theta(n)$ in every case for a given nonempty size $n$ . Deleting a supplied node in a singly linked list has best $\Theta(1)$ at the head and worst $\Theta(n)$ , averaging $\Theta(n)$ under a uniformly selected target. These iterative list operations use $O(1)$ auxiliary space.

Operation	Array (size $n$ )	Singly list (head only)	Singly list (head and tail)	Doubly list (head and tail)
Access $k$ -th element, $1\le k\le n$ (one-based)	$O(1)$	$O(k)$	$O(k)$	$O(1+\min(k-1,n-k))$
Insert / delete at front	$O(n)$	$O(1)$	$O(1)$	$O(1)$
Insert at end	$O(1)$ amortised	$O(n)$	$O(1)$	$O(1)$
Delete at end	$O(1)$	$O(n)$	$O(n)$ (needs predecessor)	$O(1)$
Insert after a given node	$O(n)$	$O(1)$	$O(1)$	$O(1)$
Delete a given node	$O(n)$	$O(n)$ (find predecessor)	$O(n)$	$O(1)$
Search for a value	$O(n)$ ; $O(\lg n)$ if sorted	$O(n)$ even if sorted	$O(n)$	$O(n)$

Binary search is not efficient on a linked list: finding the middle element is itself $O(n)$ .

Standard algorithms

Reversal

Iterative reversal visits every node: $\Theta(n)$ time in best, average and worst cases, and $O(1)$ extra space; three pointers:

struct node *reverse(struct node *h) {
    struct node *prev = NULL;
    while (h) {
        struct node *nx = h->next;   /* save the rest */
        h->next = prev;              /* turn this link around */
        prev = h; h = nx;            /* advance */
    }
    return prev;                     /* new head */
}

Recursive reversal also visits every node: $\Theta(n)$ time in best, average and worst cases, and $\Theta(n)$ call-stack space (constant for an empty list):

struct node *rrev(struct node *h) {
    if (!h || !h->next) return h;
    struct node *r = rrev(h->next);  /* reverse the rest; r is its head */
    h->next->next = h;               /* old successor now points back to h */
    h->next = NULL;
    return r;
}

Middle node and cycle detection (two pointers)

Move slow one step and fast two steps per iteration:

Middle: the full traversal takes $\Theta(n)$ time in every case and $O(1)$ auxiliary space. When fast reaches the end, slow is at the middle. For an even length $n$ this loop stops at the second of the two middle nodes, position $n/2 + 1$ .
Cycle detection (Floyd): if the list has a cycle, fast eventually meets slow inside it; if fast reaches NULL, there is no cycle. For $n$ distinct nodes reachable from the head, time is $\Theta(n+1)$ in best, average and worst cases: an acyclic traversal or a Floyd meeting takes linearly many steps for a fixed nonempty $n$ . Auxiliary space is $O(1)$ .

int has_cycle(struct node *h) {
    struct node *s = h, *f = h;
    while (f && f->next) { s = s->next; f = f->next->next; if (s == f) return 1; }
    return 0;
}

Merging two sorted lists

Repeatedly detach the smaller head and append it to the result, then link the unexhausted remainder in one step. In the constant-time pointer/key model, for nonempty inputs worst time is $\Theta(m+n)$ , best time is $\Theta(1+\min(m,n))$ (constant if either list is empty), and auxiliary space is $O(1)$ with a local dummy node. For equal nonempty lengths $m=n$ , best, average under any key-order distribution, and worst time are all $\Theta(n)$ ; for unequal lengths an average requires a specified interleaving distribution. This is the merge step of merge sort, which sorts a linked list in $O(n \lg n)$ without random access.

Circular lists

With only a tail pointer, the head is tail->next, so both insert at the front and insert at the end are $O(1)$ : link the new node after tail, and (for insert at end) move tail to it. Traversal must stop on returning to the start, typically with a do ... while (p != start) loop; a while (p != NULL) loop never ends.

Worked examples

All outputs below are for C11 with gcc on x86-64 Linux (LP64).

Example 1. Starting empty: push_front 20, push_front 10, push_back 40, insert_after(second node, 30) gives 10 20 30 40. delete_val 10 succeeds, delete_val 99 fails, and the length is then 3: 20 30 40.

Example 2. Append 50 and reverse: 50 40 30 20. Reverse again recursively: 20 30 40 50.

Example 3. The middle of 20 30 40 50 (even length 4) is 40, position 3; after appending 60, the middle of the five nodes is still 40.

Example 4. Pointing the last node's next at the second node creates a cycle: has_cycle returns 1; restoring NULL gives 0.

Example 5. Merging 1 4 7 with 2 3 8 9 gives 1 2 3 4 7 8 9.

Example 6. Building a circular list through the tail pointer by inserting 2, 3, 4 at the end after 1 and printing one loop from tail->next gives 1 2 3 4.

Example 7 (an evaluation-order trap). printf("%d %d %d\n", delete_val(&h, 10), delete_val(&h, 99), length(h)); prints a length of 4 with gcc on x86-64, where the arguments are evaluated right to left, so length runs before the deletions. The order is unspecified; perform the calls in separate statements (Operators and Expressions).

Important properties and observations

Each node costs extra space for one (singly) or two (doubly) pointers.
Insertion and deletion at a known position are $O(1)$ ; finding the position is $O(n)$ .
Singly linked deletion needs the predecessor; doubly linked deletion does not.
When updating links, first save or set every pointer you still need, then overwrite. Free a node only after unlinking it and reading its fields.
Lists are traversed sequentially, so they suit stacks, queues, adjacency lists (Graph Representations) and chained hash tables, and not binary search.

GATE examination perspective

What does this function do to the list? Trace on a 3- to 5-node example and draw the boxes after each assignment.
Missing statement in an insertion, deletion or reversal routine: check the order of pointer updates.
Complexity of insert or delete at the end, or of deleting a given node, for singly versus doubly lists, with or without a tail pointer.
Recursive list functions: output order when printing before or after the recursive call (Recursion).
Two-pointer techniques: middle element and cycle detection.

Summary

Sources

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009: Section 10.2 (linked lists, sentinels), Exercise 10.2-7 (reversal in Θ(n) time with constant extra space).
B. W. Kernighan and D. M. Ritchie, The C Programming Language, 2nd ed., Prentice Hall, 1988: Section 6.5 (self-referential structures).