Data Structures and Algorithms with C · Lecture Notes

Chapter 4: Linked Lists

An array keeps its elements side by side in memory. That layout makes indexing very fast, but inserting an element in the middle or deleting one from the middle forces every element behind it to shift. A linked list solves the problem with a different layout. Each element lives in its own node, and each node carries the address of the next one. The order now comes from these addresses rather than from position in memory. The chapter starts with the pointer and dynamic memory machinery that C needs to build such a structure. It then covers traversal, insertion, deletion, search and releasing a singly linked list, each with code traces. The classic routines follow: reversal, concatenation, finding the middle node and Floyd's cycle detection. The last sections treat the circular list, the header node, the doubly linked list and the available-node list that reuses deleted nodes.

Learning outcomes

Build a node
Define a self-referential struct, allocate a node with malloc and check the result, and return a finished node with free.
Link discipline
Insert at the front, at the end, in the middle and in sorted position without losing a single link, in the right order; pass the list by address to routines that change the head pointer.
Safe deletion
Delete a node, and release a whole list, without creating a memory leak or a dangling pointer.
Classic routines
Write reversal, concatenation, middle-node search and Floyd's cycle detection using O(1) extra memory, and justify their costs.
List variants and memory management
Choose among circular, header-node and doubly linked lists according to the purpose; reuse nodes with an available-node list.

4.1When arrays are not enough

Choosing a data structure starts with the question of which operations will be frequent. An array is excellent at some operations and rather poor at others. A linked list is strong exactly where the array is weak, and weak where the array is strong. This section compares the two structures on the same insertion task and introduces the basic idea of the linked list: the concepts of node and link.

4.1.1The cost of insertion and deletion in an array

In C, an array is a single block in which elements of the same type are laid out one after another in memory. The declaration int a[5] reserves a block of twenty bytes; a[0] occupies the first four bytes of the block, a[1] the next four. This layout has a great advantage. The address of a[i] is found with a single computation: i · sizeof(int) is added to the starting address. Reaching any element of an array therefore takes constant time, however long the array is, that is, O(1). This is called random access.

The same layout becomes a burden for insertion and deletion. No gaps can be left between elements; order is determined by position. To insert a new value into the middle of a sorted array, room must first be made for it. The only way to make room is to shift every element after the insertion point one cell to the right. Deletion works the other way around: the gap left by the deleted element is closed by shifting the elements behind it one cell to the left.

Figure 4.1 shows the difference with a concrete example. The value 10 is to be inserted into the sorted sequence 3, 8, 12, 20, right after 8. In the array, 20 moves one cell to the right first, then 12 does. Only then can 10 be written into the vacated cell, number 2. In total there are two moves and one write. In the list, no element moves at all. The new node is placed in any free spot in memory and two links are changed: the new node points to 12, and 8 points to the new node.

Array:03182123204shifts/writes: 0List:381220link updates: 0 Array:0318210312420shifts/writes: 3List:38122010link updates: 2
Figure 4.1: Inserting 10 after 8 in the sequence 3, 8, 12, 20, stored as an array and as a list. The upper drawing is the initial state. In the lower drawing the array has shifted 20 and 12 one cell to the right and written 10 into the vacated cell (three shifts/writes). In the list the new node points to 12 and 8 points to the new node; only two links have been updated.

This example has four elements, and the difference looks small. But the number of elements an array must shift equals the number of elements after the insertion point. If an element is inserted at the front of an array of n elements, all n elements are shifted. So insertion and deletion in an array cost O(n) in the worst case. In a list, if the node at which the insertion is to be made is known, only two links are written. This work does not change however long the list is; the cost is O(1).

The second weakness of the array is its size. The size of a static array is fixed at compile time. A dynamic array can be grown with realloc, but growing may require copying all elements into a new block. A linked list, on the other hand, asks for a separate small block for each element. The list grows by one node and shrinks by one node; no capacity has to be guessed in advance.

The linked list has its price as well. Because nodes are scattered in memory, the address of the i-th node cannot be computed. The only way to reach it is to start at the first node and follow the links one by one. Access to the i-th element of a list therefore takes O(i). In addition, each node carries an address next to its data, which means extra memory. In short, the two structures are opposites. If access is frequent and changes are rare, the array is the better fit; if insertions and deletions are frequent, the linked list is.

4.1.2Nodes and links

Definition 4.1

A linked list is a linear data structure that keeps its elements in separate blocks of memory called nodes. Each node consists of two fields: a data field that holds the value of the element and a link field that holds the address of the next node. The link field of the last node contains NULL. The pointer that holds the address of the first node is called the head of the list. The empty list, which has no nodes at all, is the list whose head is NULL.

In this definition each node knows only its successor. Such a list is called a singly linked list. The fact that a node does not know the node before it shapes the form of many operations. For example, to delete a node one must change the link of the node before it, but in a singly linked list there is no way to go back to the predecessor.

A linked list can be compared to a treasure hunt. Each clue slip carries a value and says where the next slip is hidden. It does not matter where in the house the slips lie; the order is established by the directions written on them. Someone who knows where the first slip is can find all the slips in order. Someone who forgets where the first slip is cannot reach any of them, even though they are all still in the house. Losing the head pointer of a linked list is exactly this: the nodes are in memory, but no variable points to them any more.

4.1.3The view in memory

The most important property of a linked list is that its nodes do not have to sit next to each other in memory. Figure 4.2 gives both the actual layout in memory and the logical view of a list of three nodes. On the left, memory is drawn as a strip together with its addresses. The node with value 12 is at address 0x1A40, the node with value 7 at 0x2C10, and the node with value 25 at 0x0F88. Other data lie in between.

Memory (physical)0x0F8825NULL0x1A40120x2C100x2330other data0x2C1070x0F88head = 0x1A40Logical view12725headThe order comes from links, not from addresses.
Figure 4.2: Nodes are scattered in memory. The variable head holds the address of the first node (0x1A40). The link field of 12 holds the address of 7 (0x2C10), the link field of 7 holds the address of 25 (0x0F88), and the link field of 25 holds NULL. The logical view on the right draws the same list with boxes and arrows.

Looking at the addresses, the order appears as 0x0F88, 0x1A40, 0x2C10. If the list were read in that order it would be 25, 12, 7. Yet the order of the list is 12, 7, 25. The source of the order is not the magnitude of the addresses but the links: head points to 12, 12 points to 7, and 7 points to 25. The logical view on the right side of the figure draws this information with boxes and arrows. All drawings used throughout these notes follow this box-and-arrow notation. The left half of a box shows the data field and the right half shows the link field. The arrow leaving a link field goes to the node whose address is in that field. A slash in a link field means NULL.

The arrows in the drawings are a convenience. There are no arrows in memory; there are only numbers. A link field stores the starting address of the other node as an integer. Going to the node an arrow “points to” means using that number as an address and reading the memory there. This distinction matters for understanding pointer errors. For example, when a node is returned with free, the number in any other link that points to it is not erased automatically. In the drawing the arrow is still there, but it now points to an invalid place.

The notion of an address has also changed over time. In old x86 processors an address consisted of two parts: a segment and a position within that segment. This arrangement is called segmented memory, and in the C compilers of that era it gave rise to distinctions such as “near” and “far” pointers. In today's operating systems every program has a single, flat address space. A pointer in this space is nothing but a number. On a 64-bit system a pointer takes 8 bytes.

4.2Pointers and dynamic memory in C

The linked list is built on two tools of C: the pointer, which holds the address of another object, and malloc and free, which let a program request memory at run time and give it back. Unless these two tools are well understood, linked list code never goes beyond rote memorization. If this topic is not mastered in the second year, it tends to stay incomplete in the years that follow; this is why the course returns to C and pointers before moving on to linked lists. It is quite normal for a student who believes they know pointers to get stuck on list code anyway. The section below therefore rebuilds the basic concepts briefly but completely.

4.2.1Addresses and pointers

Definition 4.2

A pointer is a variable that holds the memory address of an object. The declaration T *p defines a pointer p that can hold the address of an object of type T. The expression &x gives the address of x. The expression *p is the object that p points to; it can be read and overwritten. The value of a pointer that points to no object is NULL.

The short code fragment from the slides brings together these operators and the allocation and release of a node:

int x = 5;
int *p = &x;       /* p holds the address of x */
*p = 7;            /* write through p: x == 7 */

node_ptr q = NULL; /* no node yet */
q = malloc(sizeof *q);
if (q != NULL) {
    q->data = 3;   /* (*q).data = 3 */
    q->link = NULL;
}
free(q);           /* returned; q now dangles */
q = NULL;

The first three lines involve only an integer and a pointer. int x = 5; reserves four bytes of memory and writes 5 there. The line int *p = &x; defines a pointer named p and puts the address of x into it. Now p and x are two separate variables: x holds a number, p holds an address. The line *p = 7; writes 7 to the place p points to, that is, to x. The value of x has changed although x was never mentioned by name. This is also how a function can modify its caller's variable: the function is given the address of the variable, not the variable itself.

The * sign does two different jobs in two different places, and this is a common source of confusion for beginners. In a declaration (int *p) it means “p is a pointer”. Inside an expression (*p = 7) it means “the object p points to” and is called the dereference operator. The & operator is the address-of operator. The two are inverses of each other: *&x is x itself.

Table 4.1: Trace of the pointer fragment. The addresses are sample values; real addresses change with every run.
LinexpqExplanation
int x = 5;5——4 bytes were reserved for x.
int *p = &x;5&x—p holds the address of x.
*p = 7;7&x—x was written through p.
node_ptr q = NULL;7&xNULLNo node yet.
q = malloc(sizeof *q);7&x0x2C10A 16-byte block was allocated on the heap; its fields hold garbage values.
q->data = 3; q->link = NULL;7&x0x2C10The node: data = 3, link = NULL.
free(q);7&x0x2C10The block was returned; q still holds the old address (dangling).
q = NULL;7&xNULLThe dangling value was erased.

4.2.2Pointers to structures and the -> operator

The second half of the fragment works on a node. node_ptr is the “pointer to node” type, which will be defined in the next section. Since q holds the address of a node, reaching the data field of the node means going first to the node itself with *q and then to the field with the dot operator: (*q).data. The parentheses here are mandatory. In C the dot operator has higher precedence than *. Without parentheses, the expression *q.data is read as *(q.data); since q is a pointer and not a structure, this expression does not compile.

Because this notation is both long and error-prone, C offers a shorthand: q->data. The arrow operator -> goes to the field on its right in the structure that the pointer on its left points to. q->data and (*q).data are exactly the same. In linked list code the arrow operator is chained constantly. p->link->data is the value of the node after the one p points to; p->link->link is the address of the node two steps ahead. When reading such a chain, one must be sure that the pointer in front of each arrow is not NULL. Accessing a field through a NULL pointer is undefined behavior and on most systems ends in a program crash.

4.2.3Allocating a node with malloc

Local variables defined inside a function disappear when the function returns. The nodes of a linked list, however, must outlive the function that creates them. This is why nodes are allocated from heap memory. A block in heap memory is requested with malloc and lives until the program gives it back with free. malloc allocates a block of the requested number of bytes and returns the starting address of the block as type void *. In C, void * converts to any pointer type automatically, so it is enough to assign the return value without a cast. If no memory is left, malloc returns NULL.

The slides gather node allocation into a single helper function:

node_ptr new_node(int x) {
    node_ptr p = malloc(sizeof *p);
    if (p == NULL) {
        fprintf(stderr, "Out of memory...\n");
        exit(1);
    }
    p->data = x;
    p->link = NULL;
    return p;
}
  • malloc(sizeof *p) asks for as much space as the type p points to, that is, struct node. sizeof *p is computed at compile time; the current value of p is not looked at. It is therefore safe even when p has not yet been given a value. Not repeating the type name prevents the size from going wrong if the type of p changes later.
  • The return value is checked against NULL immediately. Without the check, when memory runs out the next line would try to write to a NULL address. The reaction chosen here is to write a message to the standard error stream and end the program with exit(1). The message in the slides announces the situation in a humorous tone.
  • The fields of the new node come from malloc with garbage values. The assignments p->data = x and p->link = NULL bring the node to a consistent state: the data is written and the node is not yet linked anywhere.
  • The function returns the address of the node. Because the node lives in heap memory, it does not disappear when the function returns; only the local variable p does.

How much space does a single node take? On a 64-bit Windows or Linux system an int is 4 bytes and a pointer is 8 bytes. Because a pointer must sit at an address that is a multiple of 8, the compiler inserts 4 bytes of padding after the data field. As a result sizeof(struct node) is 16 bytes (this value was measured in the verification program of these notes). Sixteen bytes are spent to store four bytes of data. On top of that, malloc keeps a few more bytes of its own bookkeeping beside each block. This is why the memory cost of a linked list is noticeable for small elements.

At this point a very common misunderstanding must be corrected. It is not necessary to call malloc for every pointer variable. malloc is called only when a new node is needed. Pointers such as p that are used to walk over the list point to nodes that already exist; allocating space for them is both unnecessary and a cause of memory leaks.

Common mistake

Allocating space for a traversal pointer: node_ptr p = malloc(sizeof *p); p = list;. The first line allocates a node, and the second line overwrites p with the head of the list. The address of the allocated block is now in no variable; the block occupies space for nothing until the program ends. The correct code is simply node_ptr p = list;.

4.2.4free and memory errors

free(p) returns the block that p points to back to memory. The rule is simple: for every address returned by malloc, free is called exactly once. Breaking this rule in the two possible directions gives two different kinds of error.

Definition 4.3

A memory leak is memory that no pointer can reach any more but that has not been returned with free. A dangling pointer is a pointer that keeps holding the address of an object that has been freed or whose lifetime has ended.

A leak comes from never calling free. In a short-running program it may go unnoticed, because the operating system takes all memory back when the program ends. But in a server that runs continuously, or in a program that builds and abandons lists inside a loop, the leaked memory accumulates and eventually memory runs out. A dangling pointer comes from the opposite cause, from returning memory too early. The call free(q) does not change the value of q; q keeps holding the old address. Reading from or writing to this address is undefined behavior. malloc may have handed the returned block out again for another purpose; in that case the value written corrupts completely unrelated data of the program. Freeing the same address a second time is also undefined behavior and can corrupt the internal bookkeeping of malloc.

This is why the last two lines of the fragment from the slides are written together: first free(q), immediately followed by q = NULL. The second line is not mandatory, but it is a good habit. Using a NULL pointer by mistake crashes the program at once on most systems, and the bug shows immediately. Using a dangling pointer, on the other hand, often “works” silently, and the bug appears much later in an unrelated place. In addition, according to the C standard free(NULL) does nothing, so releasing a pointer that has been set to NULL a second time by mistake is harmless.

Common mistake

Reading a field of a node after freeing it: free(p); p = p->link;. The second line reads from a block that has been returned. The program often gives the expected result, because the block has not yet been given to another use; but this is luck, not correctness. The right order is to save the address that is needed first and free afterwards: q = p->link; free(p); p = q;. This rule shows up in all of the deletion and release code of this chapter.

4.3Singly linked list: nodes and traversal

This section builds the definition of a linked list in C and describes the traversal pattern that visits every node of the list in order. Traversal is the skeleton of almost all list operations, including insertion and deletion.

4.3.1The self-referential structure

A node carries two fields: an integer and the address of the next node. The type of the second field is “pointer to node”. In other words, the node structure contains a field that points to an object of its own type. Such a structure is called a self-referential structure. The slides define this structure in the form used in Horowitz's book, first giving a name to the pointer type:

typedef struct node *node_ptr;  /* the pointer type first */

struct node {
    int data;         /* data field */
    node_ptr link;   /* address of the next node */
};

node_ptr list = NULL;  /* the empty list */
datanextstruct node: data field + link field
Figure 4.3: A node: the data field and the link field. The arrow leaving link points to the next node (the dashed box).

The first line gives the pointer type the name node_ptr (node pointer) before struct node has been defined. This line compiles, because C allows a pointer to a structure whose size is not yet known to be defined. Such a structure is called an incomplete type. A variable of an incomplete type cannot be defined, because the compiler does not know how much space to give it. But a pointer to an incomplete type can be defined, because the size of every pointer is known regardless of the type it points to. The struct node definition that follows completes the structure. Its link field is of the node_ptr type just defined.

The same structure can also be written without typedef: struct node { int data; struct node *link; };. In this form the structure can already refer to its own name inside its definition. The choice of name is a matter of habit. In books and old exam questions one sees names such as list_pointer, list_ptr or node_ptr for the same type. These notes use node_ptr, consistent with the slides; list_ptr appearing in an exam question is the same type.

The last line, node_ptr list = NULL;, creates an empty list. There is no separate type for the linked list itself. A list is represented by a single pointer that holds the address of the first node. If this pointer is NULL the list is empty. Every operation must therefore consider the empty list separately.

Common mistake

Writing typedef struct list { … }; and not putting a type name at the end. typedef gives a new name to a type; if no name is written the declaration is wasted, and most compilers warn “typedef requires a name”. Either the word typedef must be dropped or the type name must be written after the closing brace: typedef struct list { … } list_t;.

4.3.2Traversal

Visiting all nodes of a list in order from beginning to end is called traversal. The only tool of traversal is a pointer. The pointer starts at the first node, at each step reads the link field of the node it is on to move to the next one, and stops when it reaches NULL. The function that prints all values of the list is the simplest example of this pattern:

void print_list(node_ptr p) {
    for (; p != NULL; p = p->link)
        printf("%d ", p->data);
    printf("\n");
}

The first part of the for loop is empty, because p already arrives as a parameter holding the address of the first node. The condition p != NULL keeps the loop going as long as p points to a valid node. The body prints the value of that node. The increment part p = p->link moves p to the next node. In a linked list this assignment is the counterpart of i++ in an array. Because the link of the last node is NULL, after the last node has been printed p becomes NULL and the loop ends.

There is an important detail in the call print_list(list). In C all arguments are passed by value. The function receives not the variable list itself but a copy of the address inside it. The function advances this copy (p) in the loop and finally makes it NULL. The list in main never changes and still points to the first node. Doing the traversal directly on the parameter is therefore safe. If the same loop were written inside main on the variable list, the head of the list would be lost.

729listp 729listp 729listp = NULL
Figure 4.4: Traversing the list 7 → 2 → 9 with print_list. At the top, p is on the first node and 7 is printed. In the middle, after p = p->link, it is on the second node and 2 is printed. At the bottom the link of the third node has been followed and p has become NULL; the loop ends.

Figure 4.4 shows three moments of the traversal of the list 7 → 2 → 9. The loop runs three times and the output is 7 2 9. Each iteration does a constant amount of work: one comparison, one print and one assignment. On a list of n nodes the loop runs exactly n times, and the condition is tested n + 1 times. The running time of traversal is therefore Θ(n). The only extra memory is the pointer p, that is, O(1).

Finding the length of a list uses the same pattern; instead of printing, a counter is incremented: for (; p != NULL; p = p->link) n++;. In an array the length is either stored in a variable or known at compile time. In a linked list, unless the length is kept separately, the whole list must be traversed every time it is asked for, which takes Θ(n). In applications where the length is needed often, keeping a counter alongside the list is therefore a common solution.

Common mistake

Writing the loop condition as p->link != NULL. This condition ends the loop on arriving at the last node, so the value of the last node is never printed. Worse, if the list is empty, p is NULL and the expression p->link crashes the program. The condition p->link != NULL is correct only when the goal is to find the last node; even then the empty list must be checked separately.

4.4Insertion

There are four ways to insert a node into a linked list: at the front, at the end, after a known node, and at the right place in a sorted list. In all four the job amounts to allocating a new node and writing two links in the right order. The difference lies in how the place of insertion is found and in whether the head of the list changes.

A single rule holds for every insertion: save first, then link. Before a link field is overwritten, the address it holds must have been kept somewhere else. Otherwise all the nodes behind that address are lost. This rule is the reason why, in every piece of code below, the link of the new node is written before the link in the list.

4.4.1Inserting at the front and passing by address

Insertion at the front is the simplest insertion: the new node points to the old first node, and the new node becomes the head of the list. Simple as it is, it raises an important question specific to C. The head of the list is a variable in main, and the function must modify that variable. The code in the slides therefore takes the list by address:

bool push_front(node_ptr *head, int x) {
    node_ptr fresh = malloc(sizeof *fresh);
    if (fresh == NULL) return false;
    fresh->data = x;
    fresh->link = *head;
    *head = fresh;
    return true;
}

node_ptr list = NULL;
push_front(&list, 2);   /* 2 */
push_front(&list, 7);   /* 7 -> 2 */

The first parameter of the function is node_ptr *head, that is, a “pointer to pointer to node”. The call writes &list, handing the function the address of the variable list. Inside the function, *head is the variable list of main itself. Reading *head reads list, and writing to *head writes to list. This technique is called passing by address, and head, which holds the address of a pointer, is called a pointer to pointer.

What would happen if the parameter were taken by value, as node_ptr head? The function would receive a copy of list. The assignment head = fresh would change only this local copy. When the function returned, the copy would vanish, while list in main would keep pointing to the old first node. The new node would have been allocated and correctly linked, but no variable could reach it: a node that is neither inserted nor freed, a leak. The compiler does not catch this error, because the code is entirely valid syntactically.

A good rule helps here. A variable that appears as *head in a routine's parameter list is also used as *head inside the routine. If head shows up bare, without the star, either something deliberate is going on or there is a bug. This simple check catches most pass-by-address errors while reading.

The body of the function consists of five steps. A new node is requested with malloc. If memory could not be allocated, the function returns false; the list has not changed and is not damaged. Then the value is written. The line fresh->link = *head saves the old head: the new node points to the node that has been first until now. Finally *head = fresh changes the head. The bool return type and the values true/false come from the <stdbool.h> header.

The order of the last two lines is vital. If *head = fresh were written first, the head of the list would be the new node. The following fresh->link = *head would then write the address of the new node into its own link. The new node would point to itself and the whole old list would be lost. The only variable that pointed to it was *head, and it has been overwritten.

The cost of insertion at the front does not depend on the length of the list. One malloc, one comparison and three assignments are performed. The time is O(1), and the extra memory is the new node itself. The example in the slides starts from the empty list: push_front(&list, 2) makes the list 2, and push_front(&list, 7) makes it 7 → 2. Insertion at the front reverses the order; the most recently inserted element stands first. In the empty list *head is NULL and fresh->link becomes NULL, so no separate branch is needed for the empty list.

4.4.2Code trace: push_front(&list, 5)

The slides run the same function step by step, with the comments spelled out:

bool push_front(node_ptr *head, int x) {
    node_ptr fresh = malloc(sizeof *fresh);
    if (fresh == NULL) return false;  /* out of memory */
    fresh->data = x;
    fresh->link = *head;   /* save the old head first */
    *head = fresh;         /* then change the head */
    return true;
}

Initially the list is 7 → 2. Table 4.2 gives the state of memory after each line; Figure 4.5 draws the three most important moments.

Table 4.2: Trace of push_front(&list, 5); initially the list is 7 → 2.
Linefreshfresh->datafresh->link*head (= list)List
Call?——&node(7)7 → 2
fresh = malloc(…)&new node? (garbage)? (garbage)&node(7)7 → 2
if (fresh == NULL)False: memory was allocated, continue.
fresh->data = x&new node5? (garbage)&node(7)7 → 2
fresh->link = *head&new node5&node(7)&node(7)7 → 2 (the new node points to 7)
*head = fresh&new node5&node(7)&node(5)5 → 7 → 2
return trueThe function returns; list in main now points to 5.
72??listfresh*head 725listfresh*head 725listfresh*head
Figure 4.5: Three moments of insertion at the front. At the top, malloc has allocated the new node; its fields hold garbage values (?). In the middle, the value has been written and fresh->link = *head makes the new node point to 7; list is still at 7. At the bottom, *head = fresh moves list in main to 5: 5 → 7 → 2.

The fifth row of the table contains an interesting intermediate state. The new node points to 7, but the list still starts at 7. At this moment the contents of the list have not changed; the new node has merely been prepared. The structure of the list changes with a single assignment, in the line *head = fresh. Such an arrangement is also safe in the failure case. Had malloc failed, the function would have returned at the first check and the list would have been left untouched.

4.4.3Inserting at the end

When inserting at the end, the new node will be the last node, so its link is NULL. The real work is to find the current last node and turn its link toward the new node. Since the list is held only by its head, the last node can be found only by walking from the beginning:

bool push_back(node_ptr *head, int x) {
    node_ptr p, fresh = malloc(sizeof *fresh);
    if (fresh == NULL) return false;
    fresh->data = x;
    fresh->link = NULL;             /* the new last node */
    if (*head == NULL) { *head = fresh; return true; }
    for (p = *head; p->link != NULL; p = p->link)
        ;                          /* find the last node */
    p->link = fresh;
    return true;
}
  • The first two lines prepare the new node: allocate it, check it, write its value and set its link to NULL.
  • If the list is empty (*head == NULL) there is no last node. The new node becomes both the first and the last node, and the head changes. Because of this case, this function too takes the list by address.
  • If the list is not empty, the for loop starts p at the head and advances it as long as p->link != NULL. The body of the loop is empty; the lone semicolon makes this explicit. When the loop ends, p points to the node whose link is NULL, that is, the last node.
  • p->link = fresh attaches the new node to the end of the chain.

The loop condition here differs from the one in traversal: it is p->link != NULL, not p != NULL. The aim is not to step off the list but to stop at the last node. This condition assumes that p is not NULL; that is why the check for the empty list is done before the loop.

4165list 4165listp
Figure 4.6: Inserting 5 at the end of the list 4 → 1 → 6. At the top, the new node is ready and its link is NULL. At the bottom, p has found the last node (6) and p->link = fresh has been written: 4 → 1 → 6 → 5.

The cost of insertion at the end comes from the walk that finds the last node. On a list of n nodes the loop takes n − 1 steps; the time is Θ(n). Insertion into the empty list is O(1). Building a list of n nodes from empty by inserting at the end therefore takes 0 + 1 + 2 + … + (n − 1) = n(n − 1)/2 steps, that is, Θ(n2). This cost is unacceptable in applications where insertion at the end is frequent.

The solution is simple: keep a second pointer (tail) beside the head that holds the address of the last node. Since the last node is known at every moment, insertion at the end becomes O(1): tail->link = fresh; tail = fresh;. The price is keeping this pointer up to date in every operation. For example, if the last node is deleted, tail must be updated as well. The linked queue is implemented in exactly this way: elements are added at the end and removed from the front, and both operations take O(1). A circular list obtains the same gain with a single pointer.

4.4.4Inserting in the middle

If the node immediately before the place of insertion is known, insertion needs no walk. The function in the slides inserts a new node with value x after the node prev:

/* inserts a new node with value x after prev */
node_ptr insert_after(node_ptr prev, int x) {
    node_ptr p = new_node(x);  /* malloc + check */
    if (prev != NULL) {      /* middle or end */
        p->link = prev->link;
        prev->link = p;
    }                          /* else stand-alone */
    return p;
}

The new node is allocated with new_node; the memory check lives inside that function. If prev is not NULL, two links are written. The line p->link = prev->link copies into the new node the address of the node that prev has been pointing to. This is the “save first” step. prev->link = p then hooks the new node into the chain. If prev is the last node, prev->link is NULL and the new node is added at the end; the same code covers both cases. If prev is NULL, the new node is not attached to any list and is returned on its own. In that case the caller is expected to use the returned node as the head of a new list.

127259listprevp 127259listprevp
Figure 4.7: Inserting 9 after 7 in the list 12 → 7 → 25. At the top, p->link = prev->link has copied the address of 25 into the new node; two links now point to 25 at once. At the bottom, prev->link = p makes 7 point to the new node: 12 → 7 → 9 → 25.

The upper drawing of Figure 4.7 shows an important intermediate moment: 7 and 9 point to 25 at the same time. This is not a mistake; it is perfectly allowed for several links to point to one node. At this moment the list is still 12 → 7 → 25, because someone traversing from the head never visits 9. After the second assignment, 9 enters the chain. If the order of the assignments were reversed, that is, if prev->link = p were written first, the address of 25 would be lost. The following p->link = prev->link would then write the node's own address into its link, and 9 would turn into a node pointing at itself.

The function writes only two links and contains no loop; its time is O(1). How prev is found is a separate question. If it has to be found by value, a search is needed and the total cost becomes the O(n) of the search. This function is a generalization of the routine used in polynomial multiplication, which appends a new term after the previous term: there too the new term is added after the previous one, and since the previous term is known at every step, the insertion takes constant time.

4.4.5Sorted insertion

When a new value is inserted into a list whose values are kept in ascending order, the new node must be put in the right place so that the order is not broken. The right place is immediately after the last node that is smaller than the new value. In a singly linked list, inserting after a node requires that node itself. For this reason two pointers walk together during the search: p points to the node being examined and prev to the node one behind p.

void sorted_insert(node_ptr *head, node_ptr fresh) {
    node_ptr prev = NULL, p = *head;
    while (p != NULL && p->data < fresh->data) {
        prev = p;
        p = p->link;
    }
    fresh->link = p;
    if (prev == NULL) *head = fresh;  /* at the front */
    else prev->link = fresh;          /* middle or end */
}

The function receives the new node ready-made; allocating the node and writing its value is the caller's job. prev starts at NULL and p at the first node. The while loop advances the two pointers together one step as long as p has not left the list and the value of p is smaller than the new value. First prev = p, then p = p->link is written; this order guarantees that prev always stays exactly one step behind p. When the loop ends, the place of the new node is between prev and p.

After the loop, fresh->link = p is written first. This preserves the address of p, whether it is a real node or NULL. Then prev is examined. If prev is still NULL, the loop never ran. That means either the list is empty or the new value is smaller than or equal to the first node; in both cases the new node goes to the front and *head changes. If prev is not NULL, the new node is inserted in the middle or at the end: prev->link = fresh.

Example 4.1

The value 7 is to be inserted into the sorted list 2 → 5 → 9. The new node has been allocated with malloc and its value 7 written. Table 4.3 gives each test of the loop on a separate row.

Table 4.3: Trace of inserting 7 into the list 2 → 5 → 9 with sorted_insert.
StepprevpConditionAction
StartNULL&node(2)——
1st testNULL&node(2)2 < 7: trueprev = p, p = p->link
2nd test&node(2)&node(5)5 < 7: trueprev = p, p = p->link
3rd test&node(5)&node(9)9 < 7: falseThe loop ends; the place is between 5 and 9.
fresh->link = p&node(5)&node(9)—7 points to 9.
prev == NULL?&node(5)&node(9)falseThe head does not change.
prev->link = fresh&node(5)&node(9)—List: 2 → 5 → 7 → 9.
2597listprevp9 < 7 → falsefresh 2597listprevpfresh
Figure 4.8: Two moments of sorted insertion. At the top the loop has stopped because 9 < 7 is false; prev is at 5, p is at 9 and the new node is not yet linked. At the bottom fresh->link = p and prev->link = fresh have been written: 2 → 5 → 7 → 9.

The same code handles the other cases correctly too (they were tried in the verification program). If 1 is inserted, the first test 2 < 1 is false, so the loop never runs; prev stays NULL and the new node goes to the front. If 10 is inserted, the loop passes all the nodes and stops when p becomes NULL; fresh->link becomes NULL and the new node is attached after the last node. If a value equal to an existing one is inserted, for example 5, the condition 5 < 5 is false, so the loop stops in front of the old 5 and the new 5 goes in before the old one. Had the condition been written <=, the new 5 would go in after the old one. When the relative order of equal values matters, this detail is decisive.

The time of sorted insertion is determined by the number of iterations of the loop. In the best case the new value is the smallest, the loop does not run and the time is O(1). In the worst case the new value is the largest and the whole list is traversed: Θ(n). In a sorted array the right place can be found by binary search in O(log n), but the shifting that follows is again O(n). In a list, finding the place is O(n) and linking is O(1). The total cost is linear in both structures, but its source is different.

Common mistake

Writing the loop condition in the order p->data < fresh->data && p != NULL. The && operator is evaluated from left to right. When the end of the list is reached, p is NULL and the first condition tries to look inside NULL; the program crashes. In the right order (p != NULL && …), when the first condition is false the second is never evaluated. This behavior is called short-circuit evaluation, and every linked list loop relies on it.

4.5Deletion, search and releasing the list

Deletion is the reverse of insertion, but with one extra step: after the node has been taken out of the chain, its memory must also be returned with free. This section first describes deleting the next node, then deleting by value. Search and positional access follow, and last come the recursive and iterative routines that release a whole list.

4.5.1Deleting the next node

Deleting a node from a singly linked list means changing the link that points to it. That link is not in the node to be deleted but in the node before it. Deletion therefore needs the predecessor of the node to be deleted. The first deletion function in the slides carries this requirement directly into its interface: it takes not the node to be deleted but its predecessor.

/* deletes the node after prev from the list
   and from memory */
void delete_after(node_ptr prev) {
    node_ptr victim = prev->link; /* keep the address */
    if (victim == NULL) return; /* nothing to delete */
    prev->link = victim->link;   /* repair the link */
    free(victim);                /* release the node */
}

The first line takes the address of the node to be deleted into the variable victim. If this address were not saved, after the link was changed there would be no way to reach the node and free could not be called. If prev is the last node there is no node after it, and the function returns without doing anything. Otherwise the line prev->link = victim->link jumps over the node to be deleted: prev now points to the successor of that node. After this line the node is out of the list but still sits in memory. The last line returns it to memory.

5382listprevvictim 5382listprevvictim 5382listprevvictimfree
Figure 4.9: Deleting the node after 3 (the node 8) in the list 5 → 3 → 8 → 2. At the top, victim = prev->link has saved the address of 8. In the middle, prev->link = victim->link makes 3 point to 2; 8 is out of the chain. At the bottom, free(victim) has returned the memory of 8: 5 → 3 → 2.

The function performs two assignments and one free; its time is O(1). But it has a limit: the head node cannot be deleted, because the head node has no predecessor. To delete the head node, the variable that holds the head of the list must be changed. There are two ways around this limit. The first is for the function to take the list by address and contain a separate branch for the head; the delete-by-value function is like this. The second is to put a header node, which is never deleted, at the front of the list. Then every real node has a predecessor and the special case disappears.

4.5.2Deleting by value

In most applications the node to be deleted is known not by its address but by its value: “delete 1 from the list”. In this case the node is first found and then deleted. During the search, as in sorted insertion, a trailing prev pointer is kept.

bool delete_value(node_ptr *head, int x) {
    node_ptr prev = NULL, p = *head;
    while (p != NULL && p->data != x) {
        prev = p;
        p = p->link;
    }
    if (p == NULL) return false;         /* x absent */
    if (prev == NULL) *head = p->link;  /* the head */
    else prev->link = p->link;          /* skip it */
    free(p);
    return true;
}
  • The loop advances the two pointers together as long as p has not reached the end of the list and the value of p differs from x.
  • If the loop ended with p == NULL, x is not in the list; the function returns false and the list does not change.
  • If prev == NULL, the loop never ran, that is, x is in the first node. The head changes: *head = p->link. If the list has a single node, p->link is NULL and the list becomes empty.
  • Otherwise prev->link = p->link jumps over p.
  • In both branches p is no longer in the list and is released with free(p). The link change is made before free, because p->link has to be read.
Example 4.2

The list is 3 → 8 → 1 → 6 and delete_value(&list, 1) is called. Table 4.4 gives every step. The loop runs twice and stops at the third test because 1 != 1 is false. At this moment p points to 1 and prev to 8. Since prev is not NULL, the head does not change; the link of 8 is turned to 6 and the node of 1 is released. The result is 3 → 8 → 6.

Table 4.4: Trace of delete_value(&list, 1); initially the list is 3 → 8 → 1 → 6.
StepprevpCondition / action
StartNULL&node(3)—
1st testNULL&node(3)3 != 1: true → prev = p, p = p->link
2nd test&node(3)&node(8)8 != 1: true → prev = p, p = p->link
3rd test&node(8)&node(1)1 != 1: false → the loop ends
p == NULL?&node(8)&node(1)false: x is in the list
prev == NULL?&node(8)&node(1)false: the head is not being deleted
prev->link = p->link&node(8)&node(1)8 now points to 6; 1 has been skipped
free(p)&node(8)(dangling)The node was returned; the list is 3 → 8 → 6, the result is true
3816listprevp1 != 1 → false 3816listprevp 3816listprevpfree
Figure 4.10: Three moments of the call delete_value(&list, 1). At the top the loop has stopped because 1 != 1 is false; prev is at 8 and p is at 1. In the middle, prev->link = p->link makes 8 point to 6. At the bottom, after free(p), the list is 3 → 8 → 6.

The cost of the function comes from the search. If x is in the k-th node (counting from 0), the loop runs k times; if x is not in the list, it runs n times. In the worst case the time is Θ(n). The link change and free after the search take constant time. In the verification program, from the same list first 1 was deleted, then 3 at the head, and finally 42, which is not in the list, was searched for. The three calls ran their loops 2, 0 and 2 times; the first two returned true and the last returned false. At the last call the list was 8 → 6, so searching for 42 took two iterations.

What happens if the call free(p) is forgotten? The node has left the list and the only variable that points to it is the local p. When the function returns, p disappears too. The node stays in memory but no pointer can reach it: this is the memory leak of the definition. Most leaks in list code come precisely from a forgotten free in a deletion function.

4.5.3Search and positional access

Search is a form of traversal that ends early. It stops the moment the value is found and returns the address of the node. Positional access takes a given number of steps. The two functions in the slides do these two jobs:

node_ptr find(node_ptr p, int x) {
    while (p != NULL && p->data != x)
        p = p->link;
    return p;               /* NULL if not found */
}

node_ptr nth(node_ptr p, int i) {  /* 0-based */
    while (p != NULL && i-- > 0)
        p = p->link;
    return p;               /* NULL if i >= length */
}

find advances as long as p has not reached the end of the list and does not hold the sought value. The loop ends for two reasons. If p has stopped on a node, that node holds the sought value and its address is returned. If p has reached NULL, the value is not in the list and NULL is returned. The caller must therefore check for NULL before using the return value.

The order in the condition is decisive here too: first p != NULL, then p->data != x. If the order were reversed, when the value is absent p would become NULL after the last node and an attempt would be made to read p->data. Thanks to short-circuit evaluation, in the right order the second condition is never evaluated when the first is false.

The function nth finds the 0-based i-th node. The expression i-- > 0 first compares i with 0 and then decrements i. If it is called with i = 2, the comparisons are 2 > 0, 1 > 0 and 0 > 0; since the first two are true, p advances two steps. If the list is shorter than i, p becomes NULL on the way and the function returns NULL. In the verification program, on the list 4 → 1 → 6 → 5, nth(list, 0) and nth(list, 3) returned 4 and 5 respectively, and nth(list, 4) returned NULL.

The costs of the two functions show plainly the weakest side of the linked list compared with the array. find takes Θ(n) in the worst case, and nth(p, i) takes Θ(i). In an array, a[i] is read in O(1) with a single address computation. A list is therefore a poor choice in a program that frequently asks to “fetch the i-th element”. For example, reading all elements with nth(list, i) for i = 0, 1, …, n − 1 in a loop takes 0 + 1 + … + (n − 1), that is, Θ(n2) steps. The same job can be done in Θ(n) with a single traversal.

If the list is sorted, search can be improved a little. One stops the moment p->data > x is seen, because all later values are larger than x as well. When the value is absent, this halves the search on average. But the worst case is still Θ(n). Binary search, which is used on sorted arrays, is useless on a linked list. Binary search looks at the middle element at every step. In a list, even reaching the middle element requires walking half the list. The total work is n/2 + n/4 + …, that is, again Θ(n), and the reduction in the number of comparisons gains nothing.

4.5.4Releasing the list: an exam question

When a list is no longer needed, all of its nodes must be returned to memory. To do this each node is freed one by one. The slides treat this job through an old exam question. The question gives two routines and asks which is correct and what the other routine does to the list in the calling function. The first version is the faulty form that students often write:

void free_list( list_ptr *list ){
    node_ptr p = *list;
    if( *list ){
        p = *list->link;
        free(*list);
        free_list(&p);
}}

The second version is the correct one:

void free_list( list_ptr *list ){
    node_ptr p = *list;
    if( p ){
        *list = p->link;
        free(p);
        free_list(list);
}}

The first version has two separate problems. The first is a syntax error: the expression *list->link does not compile. The -> operator has higher precedence than *, so the expression is read as *(list->link). list points to a pointer, not to a node; list->link is meaningless. The compiler reports “member reference base type is not a structure or union” (this error was obtained in the verification program). The intended expression is (*list)->link.

Even if the syntax error is fixed, a second, deeper problem remains. The first version makes the recursive call with &p, that is, with the address of the local variable p. The second call therefore sees not the list of main but the local p of the first call. All nodes are still released, but list in main never changes. When the calls return, list still holds the address of the old first node. That node has been returned by now: list has become a dangling pointer. In the verification program the corrected first version was called with the list 4 → 9; on return the test list == NULL came out false and list->data could be read. This read is undefined behavior; that it returned the old value 4 in that run does not show that the program is correct, only that the bug stayed hidden.

The second version uses the same address list in every call. The line *list = p->link advances list in main directly to the next node; then the old head is released. In the last call *list is NULL and the recursion stops. On return, list in main is NULL; no dangling pointer is left.

This question also shows how easy it is for the person who writes code to trust their own code too much. The first version looks reasonable at first sight, and once the syntax error is fixed it gives the impression of working without trouble. The way to see the bug is to follow, one by one, which variable's address each pointer holds. The trace in the next subsection does this for the correct version.

4.5.5Code trace: free_list(&list)

The slides trace the second version, tidied up and commented:

void free_list(node_ptr *list) {
    node_ptr p = *list;
    if (p) {
        *list = p->link;      /* advance the head first */
        free(p);              /* then free the old head */
        free_list(list);      /* continue, same address */
    }
}

The list is 4 → 9. Table 4.5 gives the state of the variables in each of the three calls. Every call has its own p, but the list parameter of all three calls holds the same address, the address of list in main.

Table 4.5: Trace of free_list(&list); initially the list is 4 → 9.
CallLinep*list (= list)Explanation
1p = *list&node(4)&node(4)There is a node to free.
1*list = p->link&node(4)&node(9)list in main advanced.
1free(p)(dangling)&node(9)Node(4) was returned; p is no longer used.
2p = *list&node(9)&node(9)The second call, with the same address.
2*list = p->link&node(9)NULLlist is now NULL.
2free(p)(dangling)NULLNode(9) was returned.
3p = *listNULLNULLif (p) is false: the base case, the call returns.
2, 1return—NULLNo work is left; the calls return in turn.
49listp*listfree 49list*list
Figure 4.11: Two moments of the release. At the top, in the first call, list has advanced to 9 and node(4) has been returned with free. At the bottom, all nodes have been released and list in main has become NULL.

The order inside the body of the function is the same rule as in the deletion functions. First the address of the next node is moved to a safe place with *list = p->link, and then the old head is released. If the order were reversed, that is, if free(p) were written first, the following read of p->link would come from freed memory. After free, p must no longer be used; that is why it is marked “dangling” in the trace table.

For a list of n nodes the function is called n + 1 times: one call for each node, and a last call that sees NULL. Each call does constant work; the time is Θ(n). But recursion is not free. Each call takes room on the call stack for a frame that holds the return address, the parameter and the local p. At the deepest moment n + 1 frames are on the stack at once, and the extra memory is Θ(n).

4.5.6Emptying with a loop

The call stack is a limited region of memory. Its size varies with the operating system and compiler settings, but it usually does not exceed a few megabytes. On a list of a million nodes the recursive version opens a million frames and may exceed the stack. This is called stack overflow. This case was tried in the verification program. When the code was compiled without optimization (-O0), a list of 100,000 nodes was released without trouble, while a list of 1,000,000 nodes crashed with a stack overflow error (STATUS_STACK_OVERFLOW). When the same code was compiled with -O2, a million nodes were released without trouble. The reason is that the recursive call is the last thing the function does. The compiler can turn such tail recursion into a loop. But the C standard does not guarantee this transformation; the safe way is to write the loop explicitly.

void clear_list(node_ptr *list) {
    while (*list != NULL) {
        node_ptr p = *list;
        *list = p->link;    /* advance first */
        free(p);            /* then free */
    }
}

The loop runs until the list is empty. In each iteration the address of the head node is taken into the local p. *list = p->link moves the list one node forward. Then p is freed. This is the body of the recursive version placed inside a loop. The time is again Θ(n), but the extra memory is only p: O(1). When the loop ends, *list is NULL, so the caller's variable has been cleared as well.

The common rule of the recursive and iterative versions is this: the next address is taken before free; the link field of a freed node is never read. This rule was applied to all deletion and release functions in the verification program of these notes, and at the end of the program the calls to malloc and free were counted. 84 calls to free matched 84 calls to malloc, so no node leaked.

Common mistake

Writing the emptying loop as while (*list != NULL) { free(*list); *list = (*list)->link; }. The second line reads the link field of the node that has just been freed. In most runs the program gives the expected result, because the returned block has not been handed to another use immediately. But if another thread or the internal bookkeeping of malloc has written into that block, the loop jumps to a random address. Errors of this kind are caught by tools such as AddressSanitizer; they are hard to notice by eye.

4.6Classic routines

Some problems about linked lists come up so often in exams, interviews and real code that their names have become classic. The four routines in this section share a common property: they traverse the list at most once, allocate no new nodes, and work with only a few pointers, that is, with O(1) extra memory. The essence of all of them is walking several pointers together in a particular pattern.

4.6.1Reversing a list

The slides introduce this routine with an old exam question: write a routine reverse that reverses the link fields of the list pointed to by the pointer list. The list 10 → 20 → 30 must become 30 → 20 → 10. The key phrase of the question is “link fields”. Copying the values into an array and writing them back in reverse order, or building a new list and moving the nodes by inserting them at the front, would also give a result. But that is not what is asked. What is asked is to turn only the direction of the links, without allocating any node and without moving any value. There are no new nodes, no copies, no malloc and no extra memory; the pointers do all the work.

The idea is this: the list is traversed once from beginning to end, and the link of each node is turned so that it points to the previous node. But the moment the link of a node is turned, the way to the node after it is lost. The address of the next node must therefore be saved before turning. Also the value to be written into the turned link, that is, the address of the previous node, must be kept at hand. Three pointers are needed in all.

102030listrqpprocessed | to process
Figure 4.12: An intermediate state of reversal. The link between r and q has been turned (the processed part); everything from p on is still in its old direction (the part yet to be processed).

Figure 4.12 shows the roles of the three pointers. r is the pointer furthest behind; it holds the head of the reversed part, that is, the node the turned link will point to. q is in the middle and points to the node whose link will be turned in this iteration. p is furthest ahead and holds the head of the list not yet processed. In each iteration one link is turned and the three pointers advance one step together.

void reverse(node_ptr *list) {
    node_ptr r, p = *list, q = NULL;
    while (p) {
        r = q;         /* r trails q */
        q = p;         /* q trails p */
        p = p->link;   /* advance p */
        q->link = r;   /* reverse the link */
    }
    *list = q;         /* last node is the head */
}

Initially p points to the head of the list and q to NULL; the value of r does not matter yet. That q is NULL is no accident: since the first node will be the last node of the reversed list, its link must be NULL, and this value is written into it through r in the first iteration. Each iteration of the loop makes four assignments:

  1. r = q: r moves to the node that was turned in the previous iteration. This node is the new target of the link to be turned in this iteration.
  2. q = p: q moves to the node whose link will be turned in this iteration.
  3. p = p->link: p advances one step. This assignment is made before the link is turned; otherwise the rest of the list would be lost.
  4. q->link = r: the link of q is turned backwards, to r.

The loop ends when p becomes NULL. At this moment q points to the last node of the old list. This node is the first node of the reversed list and is made the head with *list = q. Because the head of the list changes, the function takes the list by address, as node_ptr *list.

4.6.2Code trace: reverse(&list)

The list is 10 → 20 → 30. Table 4.6 gives the state at the end of each iteration. The last column of the table shows the links turned up to that moment.

Table 4.6: Trace of reverse; initially the list is 10 → 20 → 30. The values are the state at the end of each iteration.
MomentrqpLink turned in this iterationState of the links
Start?NULL&node(10)—10 → 20 → 30
Iteration 1NULL&node(10)&node(20)10 → NULLNULL ← 10 · 20 → 30
Iteration 2&node(10)&node(20)&node(30)20 → 10NULL ← 10 ← 20 · 30
Iteration 3&node(20)&node(30)NULL30 → 20NULL ← 10 ← 20 ← 30
*list = q&node(20)&node(30)NULL—List: 30 → 20 → 10
102030listqpr = NULL 102030listrqp 102030listrqp = NULL
Figure 4.13: Three moments of reversal. At the top, at the end of the first iteration, node(10) points to NULL. In the middle, at the end of the second iteration, node(20) points to node(10); p is at 30. At the bottom, *list = q has made the old last node the new head: 30 → 20 → 10.

In the first iteration r takes the value NULL, which is written into the link of 10. So 10 becomes the last node of the reversed list. In the second iteration the link of 20 is turned to 10, and in the third the link of 30 to 20. In the middle of every iteration there is a moment when the list is split into two parts: the part turned backwards, reachable from q, and the part not yet turned, reachable from p. Since the head of each part is held in a pointer, no node is lost. In the verification program the function was applied twice to the same list and the list returned to its original state. On an empty list the loop never runs and the assignment *list = q writes NULL; the empty list stays empty.

On a list of n nodes the loop runs n times and each iteration makes four assignments. The time is Θ(n) and the extra memory is three pointers, that is, O(1). The routine works in place: it allocates no new nodes and creates no copies. It therefore cannot fail for lack of memory; reversal can be done even when memory is full.

Common mistake

Swapping the lines p = p->link and q->link = r in the loop. At this point q and p point to the same node. If q->link = r is written first, p->link changes as well; the following p = p->link takes p not forward but backward, to r. In the first iteration r is NULL, so the loop ends immediately and the list consists only of the first node. All the remaining nodes are lost.

4.6.3Concatenating two lists

Concatenating two lists consists of linking the last node of the first list to the first node of the second. No node is copied.

/* links L2 after the end of L1, returns the head */
node_ptr concat(node_ptr L1, node_ptr L2) {
    node_ptr p;
    if (L1 == NULL) return L2;
    if (L2 != NULL) {
        for (p = L1; p->link != NULL; p = p->link)
            ;                   /* last node of L1 */
        p->link = L2;
    }
    return L1;
}

If the first list is empty the result is the second list, and the function returns L2. If the second list is empty there is nothing to do. If neither is empty, the for loop takes p to the last node of L1 and p->link = L2 is written. The function returns the head of the result list. This design differs from the insert-at-end function in that it takes the list by value and delivers the new head through the return value. The caller assigns the new head to its own variable: list = concat(L1, L2);. Both designs are correct; passing by address needs less typing, while the return value gives a clearer interface.

1469L1L2 1469L1L2p
Figure 4.14: Concatenating the lists L1 = 1 → 4 and L2 = 6 → 9. At the top there are two separate lists. At the bottom p has found the last node of L1 (4) and p->link = L2 has been written: 1 → 4 → 6 → 9.

The cost comes from finding the last node of the first list: Θ(|L1|). The length of the second list does not matter. Concatenating two arrays, on the other hand, requires copying the elements into a new array and takes Θ(n + m). If the last node of the first list is kept in a tail pointer, concatenation drops to O(1). In a circular list the job is again O(1), because a circular list is held by its last node anyway.

Concatenation has a side effect: after the operation the nodes of L2 belong jointly to both lists. The variable L2 still points to 6, and a change made through L2 changes the combined list as well. Care is needed especially when releasing. If, after the combined list has been released, L2 is also released, the same nodes are freed a second time. Setting L2 to NULL after concatenation prevents this error.

4.6.4The middle node

The first way that comes to mind to find the middle node of a list takes two passes: first the length n is counted, then n/2 steps are walked from the head. This is correct and takes Θ(n). But the same job can be done in a single pass. For this, two pointers set out together from the head: the slow pointer takes one step per iteration and the fast pointer takes two. When the fast pointer reaches the end of the list, the slow pointer is exactly halfway.

node_ptr middle(node_ptr head) {
    node_ptr slow = head, fast = head;
    while (fast != NULL && fast->link != NULL) {
        slow = slow->link;         /* 1 step */
        fast = fast->link->link;   /* 2 steps */
    }
    return slow;
}

The loop condition guarantees that the fast pointer can take two steps. The test fast != NULL catches the case in which, in a list of even length, the fast pointer passes the last node and falls onto NULL. The test fast->link != NULL catches the case in which, in a list of odd length, the fast pointer stops on the last node. The second condition also prevents the read fast->link->link from going through a NULL pointer.

12345headslowfast 12345headslowfast
Figure 4.15: The middle node of the list 1 → 2 → 3 → 4 → 5. At the top both pointers are at the head. At the bottom fast has reached the last node (5); since fast->link == NULL the loop ends and slow points to the middle node (3).

In the five-node list 1 → 2 → 3 → 4 → 5 the loop runs twice. In the first iteration slow moves to 2 and fast to 3. In the second iteration slow moves to 3 and fast to 5. Since the link of 5 is NULL, the loop ends and the function returns 3. With even length there are two middles. On the list 1 → 2 → 3 → 4 the loop again runs twice: slow moves to 2 and 3, fast to 3 and NULL. The function returns the second middle, 3. If the first middle (2) is wanted, the condition fast->link->link != NULL is added; then the fast pointer stops one step earlier. All four of these values were obtained in the verification program.

On a list of n nodes the loop runs ⌊n/2⌋ times. The fast pointer takes about n steps in total and the slow pointer n/2; the total number of link reads is of the same order as in the two-pass solution. The gain is the single pass: the list is traversed once, and the length need not be known in advance. The time is Θ(n) and the extra memory is O(1). The same “slow and fast pointer” idea gives a much stronger result in the next problem.

4.6.5Floyd's cycle detection

In a correctly built linked list the link of the last node is NULL. A faulty link can break this arrangement. For example, if the link of the last node is mistakenly written to point to a node in the middle (last->link = middle_node), the list enters a cycle. In such a list the steps p = p->link never reach NULL. print_list prints forever, and a loop that counts the length never ends. Telling whether a list contains a cycle is called cycle detection.

The first solution that comes to mind is to keep the addresses of the visited nodes in a set. At each step one checks whether the new node is in the set; if it is, a cycle has been found. This solution works but needs O(n) extra memory. The method attributed to Robert W. Floyd does the same job with O(1) extra memory. The method is also known as “the tortoise and the hare”: the tortoise (slow) takes one step per iteration and the hare (fast) takes two.

bool has_cycle(node_ptr head) {
    node_ptr slow = head, fast = head;
    while (fast != NULL && fast->link != NULL) {
        slow = slow->link;         /* 1 step */
        fast = fast->link->link;   /* 2 steps */
        if (slow == fast) return true;
    }
    return false;
}

The skeleton of the code is the same as that of the middle-node function; the only difference is the test slow == fast at the end of each iteration. What is compared here is the addresses of the nodes, not their values. Two different nodes can hold the same value; but if two pointers hold the same address, they are on the same node. If the list has no cycle, the hare, being faster than the tortoise, reaches NULL before it, and the function returns false. If the list has a cycle, both pointers enter the cycle and go around it forever. Inside the cycle the hare gains one step on the tortoise in every iteration; so they must meet.

Theorem 4.1 (The tortoise and the hare meet)

Let there be μ steps from the head of the list to the first node of the cycle, and let the cycle consist of λ nodes. In has_cycle the two pointers meet at the same node within at most λ iterations after entering the cycle. The total number of iterations does not exceed μ + λ, which equals the number n of distinct nodes in the list.

Proof. After t iterations the tortoise is t steps from the head and the hare is 2t steps away. As soon as t ≥ μ, both are inside the cycle. Inside the cycle, positions are measured modulo λ. Let d be the distance by which the hare is ahead of the tortoise, counted forward around the cycle; 0 ≤ d < λ. In each iteration the hare takes two steps and the tortoise one, so this distance decreases by 1. After d iterations the distance is 0 and the two pointers are on the same node. Since d < λ, the meeting happens at most λ − 1 iterations after the tortoise enters the cycle. The tortoise enters the cycle in iteration μ; the total number of iterations is therefore less than μ + λ. If there is no cycle, the hare reaches NULL in at most n/2 iterations. In both cases the time is O(n). ∎

The important point in the proof is that the hare cannot “jump over” the tortoise. The hare takes two steps per iteration, but the distance between them decreases by exactly 1 per iteration. When the distance is 1 it becomes 0 one iteration later; when it is 2 it goes first to 1 and then to 0. The distance never becomes negative. If the hare took three steps, the distance would decrease by 2 at a time, and with an odd distance the meeting could be missed.

Example 4.3

The list is 1 → 2 → 3 → 4 → 5 and the link of 5 mistakenly points to 3. The cycle is 3 → 4 → 5 → 3; μ = 2, λ = 3. Both pointers start at 1. Table 4.7 gives the end of each iteration. In the third iteration both pointers are at 4 and the function returns true. The number of iterations is 3, below the bound μ + λ = 5 of the theorem.

Table 4.7: Trace of has_cycle on the list 1 → 2 → 3 → 4 → 5 → (3) with a cycle.
IterationslowfastLoop conditionslow == fast
Start11——
1231 and the successor of 1 are not NULLfalse
2353 and the successor of 3 are not NULLfalse
344 (5 → 3 → 4)5 and the successor of 5 are not NULLtrue: return true
12345headslowfast5 → 3: cycle 12345headslowfast5 → 3: cycle
Figure 4.16: The hare and the tortoise in a list with a cycle. At the top both are at the head; the link from 5 back to 3 forms the cycle. At the bottom, at the end of the third iteration, the hare has gone around the cycle and caught up with the tortoise; both are at 4.

Had the same list had no cycle, that is, had the link of 5 been NULL, the hare would have reached 3 in the first iteration and 5 in the second. At the third test fast->link == NULL would end the loop and the function would return false. The verification program ran both cases and produced exactly the positions in the table.

4.6.6The start of the cycle

Knowing that a cycle exists is often not enough; to repair the fault one also needs to know at which node the cycle begins. Floyd's method gives this too with O(1) extra memory. After the meeting, one of the pointers is moved back to the head of the list. Then both are advanced one step per iteration. The node where they meet again is the first node of the cycle. In the verification program the method was written as follows:

node_ptr cycle_start(node_ptr head) {
    node_ptr slow = head, fast = head;
    while (fast != NULL && fast->link != NULL) {
        slow = slow->link;
        fast = fast->link->link;
        if (slow == fast) {          /* a cycle exists */
            slow = head;               /* one goes back */
            while (slow != fast) {     /* one step each */
                slow = slow->link;
                fast = fast->link;
            }
            return slow;               /* first cycle node */
        }
    }
    return NULL;                       /* no cycle */
}
Theorem 4.2 (The start of the cycle)

If, after the meeting, one pointer is moved to the head and both pointers are advanced one step at a time, they meet exactly μ steps later at the first node of the cycle.

Proof. Let the meeting happen in iteration t. At that moment the tortoise is t steps from the head, the hare is 2t steps away, and both are on the same node. Since the two positions denote the same node, their difference t is a multiple of the cycle length λ: in the extra t steps it took, the hare has gone around the cycle a whole number of times. Now the pointer that starts at the head reaches the first node of the cycle after μ steps. The pointer that starts at the meeting point is, after μ steps, t + μ steps from the head. The first node of the cycle is μ steps from the head, and since t is a multiple of λ, t + μ steps also lands on the same node. So the two pointers meet at the start of the cycle at step μ. They cannot meet earlier, because before step μ the pointer coming from the head is outside the cycle, while the other pointer is always inside it. ∎

In the example the meeting happened in iteration 3, at 4. The pointer from the head follows the path 1 → 2 → 3, and the pointer from the meeting point follows 4 → 5 → 3. Both reach 3 in two steps (μ = 2), and 3 is found as the start of the cycle. Finding the length of the cycle is even easier: a pointer starting at the meeting node is walked, counting, until it returns to the same node. This is one of the exercises at the end of the chapter.

Floyd's method is used outside linked lists as well. Any sequence in which each value is computed from the previous one by the same rule, for example the output of a random number generator, eventually enters a cycle. The method finds the start and the length of this cycle without storing the elements of the sequence. Knuth attributes the method to Floyd in an exercise about random number generators (3.1-6) in the second volume of The Art of Computer Programming.

4.7The circular list and the header node

The singly linked list has two recurring annoyances. Insertion at the end and concatenation must search for the last node, and the insertion and deletion code contains a separate branch for the head node. Two small changes in this section remove these annoyances. In a circular list the last node points to the first node and the list is held by its last node. In a header node scheme, a node that carries no data and is never deleted is placed at the front of the list.

4.7.1The circular list

Definition 4.4

A circular linked list is a linked list in which the link field of the last node points to the first node instead of NULL. The list is usually held by a pointer last that points to the last node. In an empty circular list last is NULL; in a list with one node, the node points to itself.

358last
Figure 4.17: The circular list 3 → 5 → 8. The link of the last node (8) returns to the first node (3). The list is held by the pointer last; the first node is last->link.

Holding the end of the list instead of its head looks odd at first. But whoever knows the last node also knows the first: the first node is last->link and is found in one step. Whoever knows the head can find the end only by walking the whole list. The pointer last thus makes both ends accessible in O(1). That is why, in a circular list, insertion both at the front and at the end takes constant time.

In a circular list no link is NULL. This changes the stopping condition of traversal. A loop written with the condition p != NULL never ends on a circular list. Traversal stops when it returns to the starting node. Since the starting node would satisfy the condition already in the very first iteration, the condition is checked at the end of the loop; this is why do-while is used. The length function in the slides shows this pattern:

int c_length(node_ptr last) {
    int n = 0;
    node_ptr p = last;
    if (last == NULL) return 0;   /* empty list */
    do {
        n++;
        p = p->link;
    } while (p != last);          /* full circle */
    return n;
}

The empty list is checked separately, because the body of a do-while runs at least once and p->link cannot be read on an empty list. If the list is not empty, p starts at the last node. The body first increments the counter and then advances p. The condition keeps the loop going until p is back at the last node. On the list 3 → 5 → 8, p moves to 3, 5 and 8 in turn; after the third iteration p == last and the function returns 3. The time is Θ(n). Had the same loop been written as while (p != last), the body would never run, because p is initially already equal to last, and the result would be 0.

4.7.2Insertion into a circular list

In a circular list, insertion at the front means putting the new node between the last node and the first node:

void c_push_front(node_ptr *last, node_ptr fresh) {
    if (*last == NULL) {           /* empty list */
        *last = fresh;
        fresh->link = fresh;       /* points to itself */
    } else {
        fresh->link = (*last)->link;  /* old first node */
        (*last)->link = fresh;
    }
}

If the list is empty, the new node becomes the only node. last points to it and the link of the node returns to itself: a circular list with one node. If the list is not empty, two links are written. The line fresh->link = (*last)->link links the new node to the old first node. (*last)->link = fresh links the last node to the new node; the new node is now the first node. Here too the order obeys the “save first, then link” rule. The parentheses in (*last)->link are mandatory; *last->link is read as *(last->link) and does not compile.

3581?lastfresh 3581lastfresh 3581lastfresh
Figure 4.18: Inserting 1 into the circular list 3 → 5 → 8. At the top the new node is ready. In the middle, fresh->link = last->link and last->link = fresh have inserted 1 at the front: 1 → 3 → 5 → 8. At the bottom *last = fresh has also been written, so that 1 is inserted at the end: 3 → 5 → 8 → 1.

No separate function is needed for insertion at the end. In a circular list, “first” and “last” depend only on where the pointer last stands. If, after the new node has been inserted at the front, last is advanced by one node, that is, *last = fresh is written, the same node has been inserted at the end: c_push_front(last, fresh); *last = fresh;. Insertion at the front and at the end is the same link operation; the difference lies only in the pointer last. Both are O(1). In the verification program, insertion at the front into the list 3 → 5 → 8 gave 1 → 3 → 5 → 8 and insertion at the end gave 3 → 5 → 8 → 1.

The circular list is a natural structure for data that is traversed again and again in order. The round-robin job scheduler of an operating system keeps the ready processes in a circular list; in each time slice it moves on to the next process, and when it reaches the end of the list it wraps around to the beginning by itself. In a multiplayer game, whose turn it is can be kept in the same way.

4.7.3The header node

All the insertion and deletion code in the previous sections made the same distinction: if the change is at the head node, *head changes; otherwise the link of the previous node changes. This distinction needs an if (prev == NULL) branch in every function and passing by address in every call. Its origin is simple: the head node has no predecessor. The header node removes this deficiency.

Definition 4.5

A header node is a node that stands at the front of the list, carries no data and is never deleted. The list variable always points to the header node. The empty list consists of the header node alone. Because it makes boundary checks unnecessary, such a node is also called a sentinel node in some sources.

H38listHlistnon-empty list: H → 3 → 8empty list: H only
Figure 4.19: A list with a header node. On the left, a non-empty list: list points to the header (H) and the real nodes come after H (H → 3 → 8). On the right, the empty list: only H exists.

The gain of the header node is this: every real node has a predecessor. The predecessor of the first real node is the header. The list variable points to the header, and since the header is never deleted, this variable never changes. There is no need to give the functions the address of the list; the address of the header is enough. The sorted insertion function therefore becomes much shorter:

/* sorted insertion with a header: no special case */
void h_sorted_insert(node_ptr header, node_ptr fresh) {
    node_ptr prev = header;         /* never NULL */
    while (prev->link != NULL &&
           prev->link->data < fresh->data)
        prev = prev->link;
    fresh->link = prev->link;
    prev->link = fresh;
}

prev starts at the header and is never NULL. The loop advances as long as the successor of prev exists and is smaller than the new value. A single pointer is enough here, because the node being examined is always prev->link. When the loop ends, the new node is inserted after prev. Insertion at the front, in the middle, at the end and into the empty list: all four are done with the same two lines. The special case if (prev == NULL) has disappeared. In the verification program 8, 3, 5, 1 and 9 were inserted in this order into an empty list with a header, and the result was 1 → 3 → 5 → 8 → 9. In this sequence 3 and 1 went to the front and 9 to the end.

The price of the header node is the memory of a single node. In some applications the data field of the header does not go to waste; it is used to hold summary information such as the length of the list. In traversal and printing code, however, the header must be skipped: the real nodes start at list->link. The header node shows its greatest benefit when it is used together with doubly linked and circular lists.

4.8The doubly linked list

In a singly linked list it is not possible to go backwards from a node. To delete a node or to insert in front of it, its predecessor is needed, and the predecessor can only be found by searching from the head. If a second link that holds the address of the previous node is added to each node, this restriction disappears.

4.8.1Structure and invariant

Definition 4.6

A doubly linked list is a linked list in which each node holds the address of both the next and the previous node. In the implementation in the slides, the field that points to the previous node is called llink and the field that points to the next node is called rlink.

typedef struct dnode *dnode_ptr;
struct dnode {
    dnode_ptr llink;   /* previous */
    int data;
    dnode_ptr rlink;   /* next */
};
/* invariant: p == p->llink->rlink == p->rlink->llink */

The slides build the doubly linked list as circular and with a header node. The rlink of the header node points to the first real node and its llink to the last real node. The rlink of the last real node and the llink of the first real node return to the header. So the list has no NULL link at all. In the empty list both links of the header point to itself.

HH48empty: H points to itselfH ⇄ 4 ⇄ 8 ⇄ H
Figure 4.20: A circular doubly linked list with a header. On the left the empty list: both links of H point to itself. On the right H ⇄ 4 ⇄ 8 ⇄ H; the rlink of each node points to the next, the llink to the previous, and the two ends return to the header.

In this structure an equality holds for every node. The right neighbor of a node's left neighbor is the node itself; the left neighbor of its right neighbor is also itself. In short, p == p->llink->rlink == p->rlink->llink. This equality is called the invariant of the structure: it must hold for all nodes before and after every operation. In the circular structure with a header, the equality holds for the header and for the end nodes alike; no node is special. When writing insertion or deletion code, the question to ask is this: when the operation is over, is the invariant restored at all nodes? The verification program of these notes checked this equality for all nodes after every operation.

The doubly linked list has three important gains. The list can be traversed in both directions: p = p->rlink goes forward and p = p->llink goes backward. A node whose address is known is deleted in O(1) without searching for its predecessor. Insertion both before and after a node is done in O(1). There are also three costs. Each node carries two pointers; on a 64-bit system this is an extra 8 bytes per node. Each insertion and deletion updates four links. With more links, it also becomes easier to make a link error.

4.8.2Insertion

The insertion function in the slides inserts a new node to the right of the node p:

/* inserts the new node to the right of p */
void dinsert(dnode_ptr p, dnode_ptr fresh) {
    fresh->llink = p;
    fresh->rlink = p->rlink;
    p->rlink->llink = fresh;
    p->rlink = fresh;
}

Each of the four lines writes one link. The first two lines only prepare the new node: fresh->llink = p links the left of the new node to p, and fresh->rlink = p->rlink links the right of the new node to the current right neighbor of p. After these two lines the list itself has not changed at all; someone traversing from the front or from the back does not see the new node. The third line, p->rlink->llink = fresh, turns the llink of the node to the right of p toward the new node. The fourth line, p->rlink = fresh, turns the rlink of p toward the new node.

The order of the third and fourth lines cannot be changed. The third line reaches the node on the right of p through p->rlink. If the fourth line ran first, p->rlink would now be the new node, and p->rlink->llink = fresh would turn the left of the new node toward itself. The llink of the real right neighbor would still point to p; the invariant would be broken. The first two lines, on the other hand, can be written in either order, because they write only to the new node.

Example 4.4

The list is H ⇄ 4 ⇄ 8 ⇄ H. A new node with value 6 is to be inserted to the right of 4; p is node(4). Table 4.8 gives the link that changes after each line.

Table 4.8: Trace of dinsert(p, fresh); p = node(4), fresh = node(6), initially H ⇄ 4 ⇄ 8 ⇄ H.
LineLink that changesExplanation
fresh->llink = p6.llink → 4The left link of the new node points to 4.
fresh->rlink = p->rlink6.rlink → 8Its right link points to 8. The list has not changed yet.
p->rlink->llink = fresh8.llink → 6Since p->rlink is still 8, the left of 8 is written.
p->rlink = fresh4.rlink → 6The last link; the list is H ⇄ 4 ⇄ 6 ⇄ 8 ⇄ H.
H486pH: the header nodefresh H486pH: the header nodefresh H486pH: the header node
Figure 4.21: Three moments of doubly linked insertion. At the top the new node has been prepared: its left points to 4 and its right to 8. In the middle, p->rlink->llink = fresh has turned the left of 8 to 6. At the bottom, p->rlink = fresh has completed the insertion: H ⇄ 4 ⇄ 6 ⇄ 8 ⇄ H.

The function has no if at all. Whether p is the header (insertion at the front), the last node (insertion at the end) or the list is empty, the same four lines work correctly. In the empty list p is the header and p->rlink is the header too. Both links of the new node point to the header, and both links of the header point to the new node. This generality is the common gain of the header node and the circular structure. The time is four assignments, that is, O(1).

4.8.3Deletion

In a doubly linked list the predecessor of the node to be deleted is already at hand: p->llink. Deletion therefore consists of linking the node's two neighbors to each other and releasing the node:

void ddelete(dnode_ptr header, dnode_ptr p) {
    if (p == header) {       /* the header is never deleted */
        fprintf(stderr, "Cannot delete the header\n");
        return;
    }
    p->llink->rlink = p->rlink;
    p->rlink->llink = p->llink;
    free(p);
}

The header node must never be deleted; if it were, the list variable would turn into a dangling pointer. The function checks for this case and returns with an error message. Then two links are written. The line p->llink->rlink = p->rlink turns the rlink of the left neighbor toward the right neighbor. The line p->rlink->llink = p->llink turns the llink of the right neighbor toward the left neighbor. The order of these two lines does not matter, because both read the links of p itself and the links of p do not change. Finally the node is released.

H468pH: the header node H468pH: the header node H468pH: the header nodefree
Figure 4.22: Deleting 6 from the list H ⇄ 4 ⇄ 6 ⇄ 8 ⇄ H. At the top p points to node(6); its predecessor is at hand through p->llink. In the middle the two neighbors have been linked to each other: the rlink of 4 is 8 and the llink of 8 is 4. At the bottom the node has been returned with free(p).

There is no search in deletion; the time is O(1). In a singly linked list the same operation would take O(n) to find the predecessor. Thanks to the header node, no separate code is needed for the first and last nodes either. When the first real node is deleted, p->llink is the header and the rlink of the header is updated. When the last real node is deleted, p->rlink is the header and the llink of the header is updated. In the verification program, from the list H ⇄ 4 ⇄ 6 ⇄ 8 ⇄ H first 6 was deleted, then 4 and 8; the invariant held at every step and in the end both links of the header pointed to itself. An attempt to delete the header was rejected with the message “Cannot delete the header”.

Common mistake

Updating the links in only one direction in a doubly linked list. For example, forgetting the line p->rlink->llink = fresh in insertion. Forward traversal works correctly and the bug goes unnoticed. But in backward traversal, going left from 8 skips 6 and arrives directly at 4. In a structure that shows different lists in the two directions, the next deletion scrambles the links completely. A small test function that checks the invariant (p == p->llink->rlink == p->rlink->llink) at all nodes after every operation catches this bug immediately.

4.9The available-node list

Some programs keep inserting and deleting nodes throughout their run. For example, a polynomial-processing program creates new term nodes in every addition and multiplication, and it also releases the nodes of intermediate results immediately. Calling malloc at every insertion and free at every deletion is correct but not cheap. These two functions have to look for a free block of suitable size in memory and update their own bookkeeping. The solution in the book by Horowitz, Sahni and Anderson-Freed is to collect deleted nodes on the side instead of releasing them, and to take from there first when a new node is needed.

4.9.1get_node and ret_node

Definition 4.7

An available-space list is a linked list to which deleted nodes are added instead of being freed, and which is consulted first when a new node is needed. The head of the list is traditionally kept in a global variable called avail.

node_ptr avail = NULL;        /* available nodes */

node_ptr get_node(void) {
    node_ptr p;
    if (avail != NULL) {         /* take from the list first */
        p = avail;
        avail = avail->link;
    } else {                     /* else ask the system */
        p = malloc(sizeof *p);
        if (p == NULL) exit(1);
    }
    return p;
}

void ret_node(node_ptr p) {      /* instead of free */
    p->link = avail;
    avail = p;
}

get_node takes the place of malloc. If avail is not empty, the first node of the list is taken and avail is advanced by one node. In this case malloc is not called at all. If avail is empty, a node is requested from the system; if there is no memory, the program ends. ret_node takes the place of free: the given node is added to the front of avail. Both functions perform a constant number of assignments and take O(1).

On careful inspection, avail turns out to be a stack. ret_node adds at the front of the list and get_node takes from the front of the list. The node returned last is reused first: last in, first out. That is, get_node is the same as the pop operation of a linked stack and ret_node the same as push. Since insertion at the front and deletion from the front are the two operations that take constant time in a linked list, this choice is no coincidence.

The method has a limitation: the nodes in avail do not return to heap memory until the program ends. If a program uses a large number of nodes at one moment and then deletes most of them, the deleted nodes wait in avail and no other data structure can use that memory. Also, avail is useful only for a single node type. A program that uses nodes of different sizes must keep a separate avail for each type. The method is therefore suitable for cases in which there is a single node type and insertions and deletions are very frequent.

4.9.2Step by step

Figure 4.23 starts from a state in which two free nodes are waiting in the avail chain. On the right there is a node in use (9).

  1. get_node() is called. Since avail is not empty, p = avail is executed; malloc is not called.
  2. With avail = avail->link the head of the chain advances. The node taken now belongs to the caller; one node is left in avail.
  3. Later the node of 9 will be deleted. Instead of free, ret_node(deleted) is called and deleted->link = avail is written first.
  4. With avail = deleted the node moves to the head of the chain and is ready for reuse.
··9?availnode in use ··9??availpnode in use ··9?availdeleted(in use)
Figure 4.23: Taking and returning nodes with the avail list. At the top there are two free nodes in the avail chain. In the middle get_node has handed the first node to p and avail has advanced. At the bottom the deleted node has been added to the head of the chain with ret_node.

In the verification program this behavior was observed with counters. get_node calls made while nodes were waiting in avail did not increase the malloc counter and returned the node that had been returned last. While waiting in the chain, nodes may carry their old values in their data fields. get_node, like malloc, does not initialize the fields; that is the caller's job.

Common mistake

Continuing to use a node after returning it with ret_node. Unlike free, this error is caught by no tool, because the memory of the node is actually valid. But the link field of the node is now part of the avail chain. Every value written to it corrupts avail, and the next get_node call may hand out a random address as a node.

4.9.3Returning a circular list in one move

Returning all the nodes of a list to avail requires, in a plain singly linked list, one ret_node per node, or at least a walk to find the last node, that is, Θ(n). In a circular list the same job is O(1) regardless of length. The routine called cerase in Horowitz's book opens the ring at a single point and puts the whole list in front of avail:

/* return a circular list to avail in O(1) */
void cerase(node_ptr *last) {
    node_ptr first;
    if (*last != NULL) {
        first = (*last)->link;   /* first node */
        (*last)->link = avail;   /* open the ring */
        avail = first;
        *last = NULL;
    }
}

If the list is not empty, the address of the first node is first taken into first ((*last)->link). Then the link of the last node is turned to avail. This assignment opens the ring: the last node now points not to the first node but to the head of the avail chain. At this moment someone starting at first and moving forward passes through all the nodes of the list and reaches the old nodes of avail. The assignment avail = first makes this whole chain the new avail. Finally the caller's variable last is set to NULL; the list is now empty and no dangling pointer is left.

358·lastavailfirst 358·lastavailfirst 358·lastavailfirst
Figure 4.24: Returning the circular list 3 → 5 → 8 to avail. At the top last = 8, first = 3 and there is one node in avail. In the middle last->link = avail has opened the ring; 8 now points to the old head of avail. At the bottom avail = first and *last = NULL have put the whole list in front of avail.

The routine makes only four assignments and contains no loop; the time is the same whether the list has three nodes or three million. What makes this possible is that a circular list gives both of its ends in O(1): last points to the last node and last->link to the first. In a plain singly linked list, finding the last node for the same job would take Θ(n). In the verification program three nodes were taken from an avail chain of eight nodes and the circular list 3 → 5 → 8 was built with them; five nodes remained in avail. After the cerase call, avail started with 3, 5, 8 and its length rose to eight again.

4.10Complexity summary and measurement

Table 4.9 gives the costs of the operations of this chapter for four structures side by side. Every value in the table has been justified in the relevant section. The singly linked list is held by its head pointer alone, the circular list by the pointer last, and the doubly linked list by its header node.

Table 4.9: Operation costs for arrays and the kinds of linked list (n and m are list lengths).
OperationArraySingly linked (head)Circular (last)Doubly linked (header)
Access the i-th elementO(1)O(i)O(i)O(i)
Insert at the frontO(n)O(1)O(1)O(1)
Insert at the endO(1)*O(n)O(1)O(1)
Insert after a known nodeO(n)O(1)O(1)O(1)
Delete a known nodeO(n)O(n)†O(n)†O(1)
Search for a valueO(n)O(n)O(n)O(n)
ConcatenationO(n + m)O(n)O(1)O(1)
Extra memory per node—1 pointer1 pointer2 pointers

* If the array's capacity is full, a resize is needed first; that step is O(n). † Finding the predecessor of the node to be deleted requires a traversal; if the predecessor is known, deletion is O(1). Reversal, the middle node and Floyd's cycle detection need O(n) time and O(1) extra memory in every kind of list.

To see what the table row “insertion at the end of a singly linked list is O(n)” means in practice, a small measurement was made. The measurement program inserted n elements in three ways: into an array, each time at the front (shifting the earlier ones with memmove), into a list with push_front, and into a list with push_back. The program was compiled with -O2 and run several times. Table 4.10 gives one of the runs. The times vary with the machine and the run; what matters is how the numbers grow.

Table 4.10: Time to insert n elements (milliseconds). The times vary with the machine.
nArray, at the front (shifting)List, push_frontList, push_back
10,0002.40.42232
20,00018.80.72768
40,00057.51.333,039

Insertion at the front of a list does constant work per element; the total time is Θ(n) and roughly doubles when n doubles. The other two columns grow quadratically: when n doubles, the time roughly quadruples. In the array every insertion shifts all the elements so far; in the list every push_back walks all the nodes so far. Both do n(n − 1)/2 units of work in total.

The surprising side of the measurement is the gap between the two quadratic operations. Although they take the same number of steps, insertion at the end of the list is about fifty times slower than insertion at the front of the array. The reason is the way memory is accessed. memmove moves consecutive bytes in large blocks and uses the processor's cache very efficiently. A list walk, on the other hand, jumps to another place in memory at every step; the address of the next node is known only after the current node has been read. This is why, even when the asymptotic cost is the same, array operations are often faster in practice. The linked list should be preferred where the asymptotic difference is truly large, for example for frequent insertion and deletion at a known position.

4.11Common mistakes

Most errors in linked list code reduce to a few patterns. The list below collects them in one place; the details of each are explained in the relevant section.

  1. Overwriting a link without saving it. In insertion in the middle, if prev->link = fresh is written first, the address of the old successor of prev is lost and the rest of the list is cut off. The rule: save first, then link.
  2. Passing the list by value to a routine that changes the head. With a definition like push_front(node_ptr head, …) only the local copy changes; list in main is not updated and the new node leaks. If the head is going to change, the list is passed by address: node_ptr *head and &list in the call.
  3. Not checking the result of malloc; forgetting free or calling it twice. An unchecked malloc writes to NULL when memory runs out. A forgotten free gives a leak, a second free gives undefined behavior.
  4. Reading the link field of a freed node. free(p); p = p->link; reads from returned memory. The successor is saved first, then the node is freed.
  5. Not testing the boundary cases. Operations on the empty list, a one-node list, the head node and the last node must be tried separately. Most bugs show up in one of these four cases.
  6. Traversing a circular list with p != NULL. In a circular list no link is NULL; the loop never ends. The stopping condition is returning to the starting node, written with do-while.
  7. Writing the condition in the wrong order. p->data != x && p != NULL looks inside NULL at the end of the list. To take advantage of short-circuit evaluation, the NULL check always comes first.

Most of these errors escape the compiler, and the program gives the right result on most inputs. List code should therefore be tested with small tests that cover the boundary cases and, where possible, with tools that catch memory errors. On Linux and macOS, the compiler option -fsanitize=address reports access after free and leaks at run time. What homework and exams ask for, beyond working code, is the ability to explain what every pointer points to at every moment.

4.12Exercises and solutions

The five exercises in the last section of the slides apply the patterns learned in the chapter to new problems. Below, the solution idea and the full C code of each exercise are given. All of the code was compiled and run on sample lists. The node type and the avail functions are the same as in the chapter.

4.12.1Merging two sorted lists without allocating nodes

Two sorted lists are to be merged into a single sorted list; no new node is to be allocated, only the links of the existing nodes rearranged. The idea is this: the nodes at the heads of the two lists are compared, the smaller one is linked to the end of the result list, and one step is taken in that list. When one of the lists runs out, the other is attached as it is; the remaining nodes are already sorted and all are greater than or equal to those in the result.

node_ptr sorted_merge(node_ptr a, node_ptr b) {
    struct node head;             /* temporary header node */
    node_ptr tail = &head;
    while (a != NULL && b != NULL) {
        if (a->data <= b->data) { tail->link = a; a = a->link; }
        else                     { tail->link = b; b = b->link; }
        tail = tail->link;
    }
    tail->link = (a != NULL) ? a : b;  /* attach the rest as is */
    return head.link;
}

The subtle part of the code is the local struct node variable head. It acts as a temporary header node. The first node of the result list is written into its link; the special case “is the result list still empty?” therefore disappears. The pointer tail holds the last node of the result list and advances by one after each linking. At the end the function returns the link of the temporary header, that is, the head of the real result list. Since the temporary header lives on the stack, it needs neither malloc nor free. Because <= is used in the comparison, for equal values the node of the first list comes first. The lists 1 → 4 → 7 and 2 → 3 → 8 → 9 become 1 → 2 → 3 → 4 → 7 → 8 → 9. Since one node is added to the result in each iteration, the time is O(n + m) and the extra memory is O(1).

4.12.2The k-th node from the end

The k-th node from the end of a list is to be found in a single pass (k = 1 is the last node). Two pointers are used. The fast pointer is first moved k steps ahead. Then the two pointers are walked together, one step at a time. When the fast pointer reaches NULL, the slow pointer is exactly k nodes behind it, that is, on the k-th node from the end.

node_ptr kth_from_end(node_ptr head, int k) {
    node_ptr fast = head, slow = head;
    for (int i = 0; i < k; i++) {
        if (fast == NULL) return NULL;   /* list shorter than k */
        fast = fast->link;
    }
    while (fast != NULL) {
        fast = fast->link;
        slow = slow->link;
    }
    return slow;
}

If the list is shorter than k, the fast pointer falls onto NULL while being moved ahead and the function returns NULL. On the list 1 → 2 → 3 → 4 → 7 → 8 → 9, 9 was found for k = 1, 7 for k = 3 and 1 for k = 7; for k = 8, NULL was returned. The fast pointer takes n steps in total and the slow pointer n − k; the time is Θ(n) and the extra memory is O(1).

4.12.3Removing duplicates from a sorted list

In a sorted list, equal values stand next to each other. Each node is therefore compared only with its successor. If they are equal, the successor is deleted and p stays where it is, because the new successor may carry the same value too. If they are not equal, p advances. The deleted nodes are returned to avail with ret_node instead of free.

void return_next(node_ptr prev) {
    node_ptr victim = prev->link;
    if (victim == NULL) return;
    prev->link = victim->link;
    ret_node(victim);
}
void remove_duplicates(node_ptr head) {
    node_ptr p = head;
    while (p != NULL && p->link != NULL) {
        if (p->data == p->link->data) return_next(p);  /* p stays put */
        else p = p->link;
    }
}

return_next is the form of the chapter's delete_after function that calls ret_node instead of free. The list 1 → 1 → 2 → 3 → 3 → 3 → 5 becomes 1 → 2 → 3 → 5, and the three deleted nodes go to avail. Each test either deletes a node or advances p; the total number of tests is n − 1 and the time is O(n).

4.12.4Recursive reversal

A recursive version of reverse rests on this thought: the list after the first node is reversed recursively, and then the first node is attached to the end of this reversed list. The end of the reversed list is the old second node, and the link of the first node still points to it.

node_ptr reverse_rec(node_ptr p) {
    node_ptr new_head;
    if (p == NULL || p->link == NULL) return p;  /* 0 or 1 node */
    new_head = reverse_rec(p->link);             /* reverse the rest */
    p->link->link = p;                           /* old next points back to me */
    p->link = NULL;
    return new_head;
}

The base case is the empty or one-node list; such a list equals its own reversal. Otherwise the rest of the list is reversed and the new head is kept in new_head. The line p->link->link = p turns the link of the old second node to p; p->link = NULL makes p the new last node. The list 10 → 20 → 30 → 40 becomes 40 → 30 → 20 → 10. The time is again Θ(n), but since a call frame is opened for each node, the extra memory is Θ(n). The O(1) extra memory of the iterative version is therefore better. Because the recursive call is not the last thing the function does, the compiler cannot turn it into a loop either.

4.12.5The length of the cycle

After a cycle has been found with Floyd's method, its length is to be computed. The meeting node is inside the cycle. A pointer starting there is walked, counting, until it returns to the same node.

int cycle_length(node_ptr head) {
    node_ptr slow = head, fast = head;
    while (fast != NULL && fast->link != NULL) {
        slow = slow->link;
        fast = fast->link->link;
        if (slow == fast) {               /* meeting inside the cycle */
            int n = 1;
            for (node_ptr p = slow->link; p != slow; p = p->link) n++;
            return n;
        }
    }
    return 0;                               /* no cycle */
}

On the list 1 → 2 → 3 → 4 → 5, the function returned 3 when the link of 5 was redirected to 3, 5 when it was redirected to 1, and 1 when it was redirected to 5 itself; on a list without a cycle it returns 0. At most n iterations are taken up to the meeting, plus λ steps for counting; the time is O(n) and the extra memory is O(1).

4.13Summary

  • A linked list keeps its elements in nodes scattered in memory; the order is established by the link field of each node. The list is represented by a pointer to the first node; the empty list is NULL.
  • A node is a self-referential structure: with typedef struct node *node_ptr; the pointer type is named first, and the structure carries a link field of its own type.
  • Nodes are allocated from heap memory with malloc(sizeof *p); the result is checked against NULL. For every malloc, exactly one free is called. A forgotten free gives a memory leak; an early or double free gives a dangling pointer and undefined behavior.
  • Link discipline: save first, then link, free last. If the head of the list is going to change, the list is passed by address (node_ptr *head, &list in the call).
  • In a singly linked list, insertion at the front is O(1) and at the end O(n); insertion after a known node and deleting the next node are O(1), deletion by value and search are O(n), and access to the i-th element is O(i). Binary search is useless on a linked list.
  • A list can be released recursively or with a loop; the recursive version uses Θ(n) stack and can cause stack overflow on a very long list.
  • Reversal (three pointers), concatenation, the middle node (slow and fast pointers) and Floyd's cycle detection work in a single pass with O(1) extra memory. In Floyd's method, if after the meeting one pointer is moved to the head and both are walked one step at a time, the start of the cycle is found.
  • A circular list is held by its last node; insertion at the front and at the end is O(1), and traversal is done with do-while. A header node removes the special case of the head node. A doubly linked list allows traversal in both directions and deletion of a known node in O(1); its invariant is p == p->llink->rlink == p->rlink->llink.
  • The available-node list (avail) reuses deleted nodes; get_node and ret_node are the pop and push operations of a stack. A circular list is returned to avail in O(1).

4.14Key concepts

The key terms of this chapter:

  • linked list
  • singly linked list
  • node
  • link
  • head
  • pointer
  • pointer to pointer
  • null pointer (NULL)
  • self-referential struct
  • incomplete type
  • typedef
  • dynamic memory allocation
  • heap memory
  • malloc
  • free
  • memory leak
  • dangling pointer
  • short-circuit evaluation
  • stack overflow
  • tail recursion
  • reversing a list
  • cycle
  • cycle detection
  • circular linked list
  • header node
  • sentinel
  • doubly linked list
  • available space list
  • push

4.15Try It Yourself

  1. The calls push_back(&list, 3), push_back(&list, 6), push_back(&list, 9), push_front(&list, 1), push_back(&list, 12) and delete_value(&list, 6) are applied in order to an empty list. What does print_list(list) print?

    Answer

    After the three insertions at the end the list is 3 → 6 → 9. Insertion at the front gives 1 → 3 → 6 → 9, and insertion at the end gives 1 → 3 → 6 → 9 → 12. delete_value finds 6 (its predecessor is 3) and turns the link of 3 to 9. The output is 1 3 9 12.

  2. Although print_list(node_ptr p) advances p until NULL, why does list in main not change? Why is push_front called with &list?

    Answer

    C passes arguments by value. print_list receives a copy of the address in list, and the function advances only this copy. push_front, on the other hand, must change the head of the list. Called by value, only the local copy would point to the new node, list in main would stay as it was and the new node would leak. With &list the function is given the address of the variable, and *head = fresh changes list directly.

  3. A second 5 is inserted into the sorted list 2 → 5 → 9 with sorted_insert. When the loop ends, what is prev, and does the new 5 go in front of or behind the old one?

    Answer

    The first test 2 < 5 is true; prev moves to 2 and p to the old 5. The second test 5 < 5 is false and the loop ends. prev is node(2). The new 5 goes in front of the old 5: 2 → 5 (new) → 5 (old) → 9. Had the condition been <=, it would have gone behind.

  4. Which node does the function middle return on the list 1 → 2 → 3 → 4 → 5 → 6? How many iterations does the loop run?

    Answer

    It runs three iterations. In them slow moves to 2, 3, 4; fast moves to 3, 5 and NULL. When fast == NULL the loop ends and the function returns 4, the second middle.

  5. In the list 1 → 2 → 3 → 4 → 5 → 6, the link of 6 points to 4. In which iteration, and at which node, does has_cycle find the meeting? How many steps does the step that finds the start of the cycle take?

    Answer

    At the end of the iterations (slow, fast) are (2, 3), (3, 5), (4, 4) in turn; the meeting is in iteration 3, at 4. Here μ = 3 and λ = 3. If one pointer is moved to the head and both are walked one step at a time, after 3 steps (1 → 2 → 3 → 4 and 4 → 5 → 6 → 4) both meet at 4. The start of the cycle is 4.

  6. If, in the body of the loop in reverse, the lines p = p->link and q->link = r are swapped, what happens to the list 10 → 20 → 30?

    Answer

    In the first iteration r = NULL and q = p = node(10). q->link = r makes the link of 10 NULL. Since q and p point to the same node, the following p = p->link makes p NULL. The loop ends and *list = q leaves the list consisting of 10 alone. 20 and 30 are pointed to by no pointer; they have leaked.

  7. If the last two lines of dinsert are swapped, that is, p->rlink = fresh is written first and then p->rlink->llink = fresh, what is the result of inserting 6 to the right of 4 in the list H ⇄ 4 ⇄ 8 ⇄ H?

    Answer

    p->rlink = fresh makes the right of 4 equal to 6. Then, since p->rlink is now 6, p->rlink->llink = fresh turns the left of 6 toward 6 itself. The left of 8 is still 4. Forward traversal gives the order H, 4, 6, 8 correctly; backward traversal jumps from 8 to 4 and does not see 6. For 6 the equality p->llink->rlink == p is broken (the left of 6 is itself and its right is 8).

  8. A program calls get_node three times with avail empty, then ret_node twice, then get_node three times again. How many times is malloc called in total?

    Answer

    In the first three calls avail is empty; three malloc calls are made. The two ret_node calls put two nodes into avail. Of the next three get_node calls, the first two take these nodes; at the third, avail is empty again and one more malloc is made. Four malloc calls in total.

  9. In a singly linked list only the head pointer is kept. What is the cost of deleting the last node? Would keeping a tail pointer as well reduce this cost? What is the situation in a doubly linked list with a header?

    Answer

    Deleting the last node requires its predecessor, the second-to-last node, which can be found only by walking from the head: Θ(n). A tail pointer makes insertion at the end O(1) but does not speed up deletion from the end; updating tail after the deletion also needs the second-to-last node. In a doubly linked list with a header, the last node is header->llink and its predecessor is p->llink; deletion is O(1).

4.16Further reading

  • E. Horowitz, S. Sahni and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd edition), Chapter 4: the source of the C implementations that these notes follow, of the avail list, of circular and doubly linked lists, and of polynomial operations with linked lists.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Section 10.2: presents the doubly linked list and the sentinel node in pseudocode, concisely and precisely.
  • D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Sections 2.2.3–2.2.5: examines linked allocation, circular lists and doubly linked lists, together with the available-space list and their historical origins.
  • D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Section 3.1, Exercise 6: gives Floyd's cycle-finding method in the context of the period of random number generators.

4.17References

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, Section 10.2 (lists with sentinels).
  2. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd edition, Chapter 4 (lists, avail, circular and doubly linked lists).
  3. D. E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd edition, Addison-Wesley, 1997, Sections 2.2.3–2.2.5.
  4. D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Section 3.1, Exercise 6 (Floyd's cycle detection).

Related pages: Chapter 4 slides · © Sercan Külcü. All rights reserved.