{"id":75,"date":"2026-02-10T08:16:00","date_gmt":"2026-02-10T08:16:00","guid":{"rendered":"https:\/\/mattbick.dev\/?p=75"},"modified":"2026-02-09T20:18:26","modified_gmt":"2026-02-09T20:18:26","slug":"data-structure-every-day-day-3-doubly-linked-list","status":"publish","type":"post","link":"https:\/\/mattbick.dev\/?p=75","title":{"rendered":"Data Structure Every Day, Day 3: Doubly Linked List"},"content":{"rendered":"\n

From Tailed Lists to Doubly Linked Lists \u2014 Killing O(n) pop_back<\/h2>\n\n\n\n

In yesterday\u2019s post, we improved a basic singly linked list by adding a tail pointer:<\/p>\n\n\n\n

struct LinkedList {\n    struct Node* head;\n    struct Node* tail;\n};<\/code><\/pre>\n\n\n\n
That change alone gave us:<\/p>\n\n\n\n
Operation<\/th>Complexity<\/th><\/tr><\/thead>
push_front<\/td>O(1)<\/td><\/tr>
pop_front<\/td>O(1)<\/td><\/tr>
front<\/td>O(1)<\/td><\/tr>
push_back<\/td>O(1)<\/td><\/tr>
pop_back<\/td>O(n)<\/strong> <\/td><\/tr>
back<\/td>O(1)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
The big remaining problem was pop_back()<\/code>.<\/p>\n\n\n\n
Because singly linked lists only store next<\/code>, removing the tail requires walking the list to find the node before it:<\/p>\n\n\n\n
O(n) traversal \u2192 find prev \u2192 remove tail<\/code><\/pre>\n\n\n\n
Today we fix that permanently.<\/p>\n\n\n\n
\n\n\n\n
The Upgrade: Doubly Linked Nodes<\/h2>\n\n\n\n
We add a prev<\/code> pointer:<\/p>\n\n\n\n
struct Node {\n    void* data;\n    size_t data_size;\n    struct Node* next;\n    struct Node* prev;\n};\n<\/code><\/pre>\n\n\n\n
Now every node knows:<\/p>\n\n\n\n
    \n
  • Who comes after it<\/li>\n\n\n\n
  • Who comes before it<\/li>\n<\/ul>\n\n\n\n
    That single extra pointer changes everything.<\/p>\n\n\n\n
    \n\n\n\n
    New Complexity Table<\/h2>\n\n\n\n
    Operation<\/th>Complexity<\/th><\/tr><\/thead>
    push_front<\/td>O(1)<\/td><\/tr>
    pop_front<\/td>O(1)<\/td><\/tr>
    front<\/td>O(1)<\/td><\/tr>
    push_back<\/td>O(1)<\/td><\/tr>
    pop_back<\/td>O(1) <\/strong><\/td><\/tr>
    back<\/td>O(1)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
    No more traversal. Ever.<\/p>\n\n\n\n
    \n\n\n\n
    Why pop_back Becomes O(1)<\/h2>\n\n\n\n
    Old singly linked list:<\/p>\n\n\n\n
    HEAD \u2192 A \u2192 B \u2192 C \u2192 D \u2192 NULL\n                        \u2191 tail<\/code><\/pre>\n\n\n\n
    To remove D<\/code>, we had to find C<\/code> by scanning from HEAD.<\/p>\n\n\n\n
    \n\n\n\n
    New doubly linked list:<\/p>\n\n\n\n
    HEAD \u2192 A \u2194 B \u2194 C \u2194 D \u2190 tail<\/code><\/pre>\n\n\n\n
    Now:<\/p>\n\n\n\n
    tail->prev = C<\/code><\/pre>\n\n\n\n
    So removal becomes:<\/p>\n\n\n\n
    free(tail)\ntail = prev<\/code><\/pre>\n\n\n\n
    Constant time.<\/p>\n\n\n\n
    \n\n\n\n
    Key Implementation Details<\/h2>\n\n\n\n
    push_front (Must Update Old Head\u2019s prev)<\/h3>\n\n\n\n
    \/\/onyl diff is that we enforce the standard that the head node has a NULL previous pointer and account for empty lists in a diff way\nvoid push_front(struct LinkedList* list, struct Node* new_head) {\n        if (!list || !new_head) return;\n\n        new_head->next = list->head;\n        new_head->prev = NULL; \/\/as stated in our header, head previous pointer is NULL since its the head\n\n        if (list->head) {\n                list->head->prev = new_head;\n        } else {\n                list->tail = new_head;\n        }\n\n        list->head = new_head;\n}<\/code><\/pre>\n\n\n\n
    \n\n\n\n
    pop_front (Must Handle Single Node Case)<\/h3>\n\n\n\n
    void pop_front(struct LinkedList* list) {\n        if (!list || !list->head) return;\n\n        struct Node* old = list->head;\n\n        \/\/now we grab the new head so that we can set the previous pointer to NULL\n        struct Node* new_head = old->next;\n\n        \/\/this is how we handle the condition of one node\n        if (new_head) {\n                new_head->prev = NULL;\n                list->head = new_head;\n        } else {\n                \/\/we rmeoved the last node, empty list\n                list->head = NULL;\n                list->tail = NULL;\n        }\n\n        free_node(old);\n}<\/code><\/pre>\n\n\n\n
    \n\n\n\n
    pop_back (Now Trivial)<\/h3>\n\n\n\n
    void pop_back(struct LinkedList* list) {\n        if (!list || !list->head) return;\n\n        \/\/ single node\n        if (list->head == list->tail) {\n                free_node(list->head);\n                list->head = NULL;\n                list->tail = NULL;\n                return;\n        }\n\n        \/\/ find node right before tail - before, we had to iterate and thus it was O(n), now we can just use the previous pointer!\n        struct Node* prev = list->tail->prev;\n\n        free_node(list->tail);\n        prev->next = NULL;\n        list->tail = prev;\n}<\/code><\/pre>\n\n\n\n
    \n\n\n\n
    This now brings us to the new benchmark profile:<\/p>\n\n\n\n
    === Doubly Linked List Benchmark ===\nImplementation: struct LinkedList { head, tail }\nBenchmarks: push_front, push_back, pop_front, pop_back, front, back\nNote: pop_* includes free_node() time.\n\n=============================\nBENCH N=1000\n=============================\npush_front   O(1)\/op total O(N)   |      0.061 ms |       61.1 ns\/op\nfront        O(1)\/op              |      2.876 ms |        1.4 ns\/op (REPS=2000000)\nback         O(1)\/op              |      2.635 ms |        1.3 ns\/op (REPS=2000000)\npop_front    O(1)\/op (+free)      |      0.012 ms |       11.8 ns\/op\npush_back    O(1)\/op total O(N)   |      0.014 ms |       14.0 ns\/op\npop_back     O(1)\/op total O(N) |      0.011 ms |       11.0 ns\/op\n\n=============================\nBENCH N=3000\n=============================\npush_front   O(1)\/op total O(N)   |      0.113 ms |       37.6 ns\/op\nfront        O(1)\/op              |      1.779 ms |        0.9 ns\/op (REPS=2000000)\nback         O(1)\/op              |      1.611 ms |        0.8 ns\/op (REPS=2000000)\npop_front    O(1)\/op (+free)      |      0.026 ms |        8.8 ns\/op\npush_back    O(1)\/op total O(N)   |      0.031 ms |       10.3 ns\/op\npop_back     O(1)\/op total O(N) |      0.025 ms |        8.2 ns\/op\n\n=============================\nBENCH N=10000\n=============================\npush_front   O(1)\/op total O(N)   |      0.293 ms |       29.3 ns\/op\nfront        O(1)\/op              |      1.614 ms |        0.8 ns\/op (REPS=2000000)\nback         O(1)\/op              |      1.590 ms |        0.8 ns\/op (REPS=2000000)\npop_front    O(1)\/op (+free)      |      0.086 ms |        8.6 ns\/op\npush_back    O(1)\/op total O(N)   |      0.108 ms |       10.8 ns\/op\npop_back     O(1)\/op total O(N) |      0.089 ms |        8.9 ns\/op\n\n=============================\nBENCH N=30000\n=============================\npush_front   O(1)\/op total O(N)   |      0.826 ms |       27.5 ns\/op\nfront        O(1)\/op              |      1.525 ms |        0.8 ns\/op (REPS=2000000)\nback         O(1)\/op              |      1.613 ms |        0.8 ns\/op (REPS=2000000)\npop_front    O(1)\/op (+free)      |      0.251 ms |        8.4 ns\/op\npush_back    O(1)\/op total O(N)   |      0.300 ms |       10.0 ns\/op\npop_back     O(1)\/op total O(N) |      0.264 ms |        8.8 ns\/op\n\n=============================\nBENCH N=100000\n=============================\npush_front   O(1)\/op total O(N)   |      2.745 ms |       27.5 ns\/op\nfront        O(1)\/op              |      1.530 ms |        0.8 ns\/op (REPS=2000000)\nback         O(1)\/op              |      1.553 ms |        0.8 ns\/op (REPS=2000000)\npop_front    O(1)\/op (+free)      |      0.854 ms |        8.5 ns\/op\npush_back    O(1)\/op total O(N)   |      1.109 ms |       11.1 ns\/op\npop_back     O(1)\/op total O(N) |      0.863 ms |        8.6 ns\/op\n\nTOTAL TIME: 26.819 ms<\/code><\/pre>\n\n\n\n
    Which compared to yesterday’s post, is WAY faster, but this comes at a cost:<\/p>\n\n\n\n
      \n
    • We now store an extra pointer for every node <\/li>\n<\/ul>\n\n\n\n
      The classic trade-off of allocating more memory to save CPU time… this is a tradeoff that you will run into in just about every piece of code you write. In this instance, the speed is well worth it however. <\/p>\n","protected":false},"excerpt":{"rendered":"
      From Tailed Lists to Doubly Linked Lists \u2014 Killing O(n) pop_back In yesterday\u2019s post, we improved a basic singly linked list by adding a tail pointer: That change alone gave us: Operation Complexity push_front O(1) pop_front O(1) front O(1) push_back O(1) pop_back O(n) back O(1) The big remaining problem was pop_back(). Because singly linked lists […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-75","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/75","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=75"}],"version-history":[{"count":6,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/75\/revisions"}],"predecessor-version":[{"id":81,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/75\/revisions\/81"}],"wp:attachment":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=75"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=75"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=75"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}