Data Structures

List Insert

Changing a few next pointers inserts a node at the front or in the middle.

relink Insertion saves the old link before pointing a node at the new neighbor.
head update Inserting at the front changes which node the head pointer references.

List Insert

insertFront
list_insert.c
Replay: real traced execution (multi-file project)
#include <stdio.h>

struct Node {
    int value;
    struct Node *next;
};

int main(void) {
    int insertFront = 1;
    struct Node second = {20, 0};
    struct Node first = {10, &second};
    struct Node added = {15, 0};
    struct Node *head = &first;

    if (insertFront) {
        added.next = head;
        head = &added;
    } else {
        added.next = first.next;
        first.next = &added;
    }

    printf("head=%d next=%d\n", head->value, head->next->value);
    return 0;
}

#include <stdio.h>

struct Node {
    int value;
    struct Node *next;
};

int main(void) {
    int insertFront = 0;
    struct Node second = {20, 0};
    struct Node first = {10, &second};
    struct Node added = {15, 0};
    struct Node *head = &first;

    if (insertFront) {
        added.next = head;
        head = &added;
    } else {
        added.next = first.next;
        first.next = &added;
    }

    printf("head=%d next=%d\n", head->value, head->next->value);
    return 0;
}

  1. insertFront ← 1, second ← (empty), first ← (empty), added ← (empty)

    8int main(void) {9    int insertFront→ 1 = 1; //@insertFront=0, 110    struct Node second→ (empty) = {20, 0};11    struct Node first→ (empty) = {10, &second(empty)};12    struct Node added→ (empty) = {15, 0};13    struct Node *head→ ⟨addr A⟩ = &first(empty);

  2. added.next ← ⟨addr A⟩, head ← ⟨addr B⟩

    15if (insertFront1) {16    added.next→ ⟨addr A⟩ = head⟨addr A⟩;17    head→ ⟨addr B⟩ = &added(empty);18} else {

  3. printf("head=%d next=%d ", head->value, head->next->value);

    23    printf("head=%d next=%d\n", head⟨addr B⟩->value, head->next⟨addr A⟩->value);24    return 0;25}
    outputhead=15 next=10

  1. insertFront ← 0, second ← (empty), first ← (empty), added ← (empty)

    8int main(void) {9    int insertFront→ 0 = 0;10    struct Node second→ (empty) = {20, 0};11    struct Node first→ (empty) = {10, &second(empty)};12    struct Node added→ (empty) = {15, 0};13    struct Node *head→ ⟨addr A⟩ = &first(empty);

  2. added.next ← ⟨addr B⟩, first.next ← ⟨addr C⟩

    17    head = &added;18} else {19    added.next→ ⟨addr B⟩ = first.next⟨addr B⟩;20    first.next→ ⟨addr C⟩ = &added(empty);21}

  3. printf("head=%d next=%d ", head->value, head->next->value);

    23    printf("head=%d next=%d\n", head⟨addr A⟩->value, head->next⟨addr C⟩->value);24    return 0;25}
    outputhead=10 next=15