A doubly linked list in C

Two pointers per node, so insertion and removal need no traversal.

#include <stdlib.h>

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

Node *push_front(Node *head, int value) {
    Node *node = malloc(sizeof *node);
    if (node == NULL) {
        return head;
    }
    node->value = value;
    node->prev = NULL;
    node->next = head;
    if (head != NULL) {
        head->prev = node;
    }
    return node;
}

Node *unlink_node(Node *head, Node *node) {
    if (node->prev != NULL) {
        node->prev->next = node->next;
    } else {
        head = node->next;
    }
    if (node->next != NULL) {
        node->next->prev = node->prev;
    }
    free(node);
    return head;
}

How it works

1. Each node knows its predecessor and its successor.
2. Removing a node patches its neighbours to each other.
3. The head and tail cases are the ones that break.

Keywords and builtins used here

• NULL
• Node
• else
• if
• int
• push_front
• return
• sizeof
• struct
• typedef
• unlink_node

The run, in numbers

Lines

34

Characters to type

545

Tokens

181

Three-star pace

100 tpm

At the three-star pace of 100 tokens a minute, this run takes about 109 seconds.

Type this snippet

Step 2 of 5 in Lists & stacks, step 7 of 20 in Data structures & algorithms.

← Previous Next →