{"id":70,"date":"2026-02-09T17:33:29","date_gmt":"2026-02-09T17:33:29","guid":{"rendered":"https:\/\/mattbick.dev\/?p=70"},"modified":"2026-02-09T17:38:14","modified_gmt":"2026-02-09T17:38:14","slug":"data-structure-every-day-2-linked-list-with-tail","status":"publish","type":"post","link":"https:\/\/mattbick.dev\/?p=70","title":{"rendered":"Data Structure Every Day, Day 2: Linked List with Tail!"},"content":{"rendered":"\n
Yesterday we went over a basic implementation of a Linked List that lacked a tail. In other words, the entire list was implicitly stored through the use of a single head node and all subsequent list operations used this head pointer. From this, we derived a complexity table: <\/p>\n\n\n\n
Also in that last post, I hinted at the idea of removing some of the O(n) complexity entries in this table by implementing a linked list that stores the tail node of the list. If we store a tail of the list, we no longer have to walk the entire list to perform push_back and back functionality. <\/p>\n\n\n\n
We do this by removing the implicit linked list by head paradigm and instead store the linked list as a struct that contains a head node (just like before), but also a tail node! We end up getting code that looks like this: <\/p>\n\n\n\n
Of note is that in this declaration file, we have the EXACT same node structure as before, but the overall LinkedList datatype represents not only a head node but also a tail node. Because of this, the shape of our functions change a fair bit. We no longer pass a head pointer around to refer to the entire list. Instead, we pass the pointer pointing to the LinkedList struct and perform operations on this structure instead. The resulting implementation code looks like this: <\/p>\n\n\n\n
#include "linked_list.h"\n#include <stdlib.h>\n#include <string.h>\n\nstruct Node* alloc_node(size_t data_size) {\n struct Node* node = malloc(sizeof *node);\n if (!node) return NULL;\n\n node->data = malloc(data_size);\n if (!node->data) {\n free(node);\n return NULL;\n }\n\n node->data_size = data_size;\n node->next = NULL;\n return node;\n}\n\nstruct Node* create_node_from_data(void* data, size_t data_size) {\n struct Node* node = alloc_node(data_size);\n if (!node) return NULL;\n memcpy(node->data, data, data_size);\n return node;\n}\n\nvoid free_node(struct Node* node) {\n if (!node) return;\n\n if (node->data) {\n free(node->data);\n node->data = NULL;\n }\n\n free(node);\n}\n\nvoid list_init(struct LinkedList* list) {\n if (!list) return;\n list->head = NULL;\n list->tail = NULL;\n}\n\nvoid free_list(struct LinkedList* list) {\n if (!list) return;\n\n struct Node* cur = list->head;\n while (cur) {\n struct Node* next = cur->next;\n free_node(cur);\n cur = next;\n }\n\n list->head = NULL;\n list->tail = NULL;\n}\n\nvoid push_front(struct LinkedList* list, struct Node* new_head) {\n if (!list || !new_head) return;\n\n new_head->next = list->head;\n list->head = new_head;\n\n \/\/ if list was empty, tail must also point to the new node\n if (list->tail == NULL) {\n list->tail = new_head;\n }\n}\n\nvoid pop_front(struct LinkedList* list) {\n if (!list || !list->head) return;\n\n struct Node* old = list->head;\n list->head = old->next;\n\n \/\/ if we removed the last node, tail must become NULL too\n if (list->head == NULL) {\n list->tail = NULL;\n }\n\n free_node(old);\n}\n\nvoid push_back(struct LinkedList* list, struct Node* new_tail) {\n if (!list || !new_tail) return;\n\n new_tail->next = NULL;\n\n \/\/ empty list\n if (list->head == NULL) {\n list->head = new_tail;\n list->tail = new_tail;\n return;\n }\n\n \/\/ non-empty list: O(1) append\n list->tail->next = new_tail;\n list->tail = new_tail;\n}\n\nvoid 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 - this is where we cannot reduce down to O(1) unfortunately unless we implemeneted a doubly linked list (next thing to do)\n struct Node* prev = list->head;\n while (prev->next != list->tail) {\n prev = prev->next;\n }\n\n free_node(list->tail);\n prev->next = NULL;\n list->tail = prev;\n}\n\nstruct Node* front(struct LinkedList* list) {\n if (!list) return NULL;\n return list->head;\n}\n\nstruct Node* back(struct LinkedList* list) {\n if (!list) return NULL;\n return list->tail;\n}<\/code><\/pre>\n\n\n\n\n\n\n\n
The changes to pay attention to: <\/h2>\n\n\n\n
Of note are the “back” and “push_back” function. Now, instead of having to traverse the entire list which results in O(n) complexity, we simply use our tail pointer to implement the same functionality. The result is that we end up with a complexity chart that looks like this: <\/p>\n\n\n\n
I have highlighted the differences, and below we have a simple profiling test bed that I ran to compare the real world speed differences of the implementations: <\/p>\n\n\n\n
Tailless Linked List Implementation Benchmark:<\/h2>\n\n\n\n
=== Tailless Linked List Benchmark ===\nReal implementation timing (includes malloc\/free)\n\n=============================\nBENCH N=1000\n=============================\npush_front O(1)\/op total O(N) | 0.060 ms | 60.3 ns\/op\nfront O(1)\/op | 3.136 ms | 1.6 ns\/op (REPS=2000000)\nback O(N)\/op | 7.174 ms | 3587.1 ns\/op (REPS=2000)\npop_front O(1)\/op (+free) | 0.008 ms | 8.5 ns\/op\npush_back O(N)\/op total O(N^2) | 0.904 ms | 903.8 ns\/op\npop_back O(N)\/op total O(N^2) | 0.930 ms | 930.4 ns\/op\n\n=============================\nBENCH N=3000\n=============================\npush_front O(1)\/op total O(N) | 0.090 ms | 29.9 ns\/op\nfront O(1)\/op | 1.770 ms | 0.9 ns\/op (REPS=2000000)\nback O(N)\/op | 14.655 ms | 7327.6 ns\/op (REPS=2000)\npop_front O(1)\/op (+free) | 0.025 ms | 8.2 ns\/op\npush_back O(N)\/op total O(N^2) | 12.537 ms | 4178.9 ns\/op\npop_back O(N)\/op total O(N^2) | 9.181 ms | 3060.4 ns\/op\n\n=============================\nBENCH N=10000\n=============================\npush_front O(1)\/op total O(N) | 0.300 ms | 30.0 ns\/op\nfront O(1)\/op | 1.756 ms | 0.9 ns\/op (REPS=2000000)\nback O(N)\/op | 23.471 ms | 11735.7 ns\/op (REPS=2000)\npop_front O(1)\/op (+free) | 0.117 ms | 11.7 ns\/op\npush_back O(N)\/op total O(N^2) | 124.918 ms | 12491.8 ns\/op\npop_back O(N)\/op total O(N^2) | 111.918 ms | 11191.8 ns\/op\n\n=============================\nBENCH N=30000\n=============================\npush_front O(1)\/op total O(N) | 0.772 ms | 25.7 ns\/op\nfront O(1)\/op | 1.740 ms | 0.9 ns\/op (REPS=2000000)\nback O(N)\/op | 95.027 ms | 47513.3 ns\/op (REPS=2000)\npop_front O(1)\/op (+free) | 0.441 ms | 14.7 ns\/op\npush_back O(N)\/op total O(N^2) | 1301.376 ms | 43379.2 ns\/op\npop_back O(N)\/op total O(N^2) | 1083.715 ms | 36123.8 ns\/op\n\n=============================\nBENCH N=100000\n=============================\npush_front O(1)\/op total O(N) | 2.597 ms | 26.0 ns\/op\nfront O(1)\/op | 1.755 ms | 0.9 ns\/op (REPS=2000000)\nback O(N)\/op | 291.028 ms | 145514.2 ns\/op (REPS=2000)\npop_front O(1)\/op (+free) | 1.592 ms | 15.9 ns\/op\npush_back O(N)\/op total O(N^2) | 14328.900 ms | 143289.0 ns\/op\npop_back O(N)\/op total O(N^2) | 12886.971 ms | 128869.7 ns\/op<\/code><\/pre>\n\n\n\n
Tailed Linked List Implementation Benchmark:<\/h2>\n\n\n\n
=== Tailed 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.033 ms | 33.3 ns\/op\nfront O(1)\/op | 1.594 ms | 0.8 ns\/op (REPS=2000000)\nback O(1)\/op | 1.551 ms | 0.8 ns\/op (REPS=2000000)\npop_front O(1)\/op (+free) | 0.009 ms | 9.4 ns\/op\npush_back O(1)\/op total O(N) | 0.011 ms | 10.7 ns\/op\npop_back O(N)\/op total O(N^2) | 0.834 ms | 833.9 ns\/op\n\n=============================\nBENCH N=3000\n=============================\npush_front O(1)\/op total O(N) | 0.075 ms | 24.9 ns\/op\nfront O(1)\/op | 1.626 ms | 0.8 ns\/op (REPS=2000000)\nback O(1)\/op | 1.564 ms | 0.8 ns\/op (REPS=2000000)\npop_front O(1)\/op (+free) | 0.026 ms | 8.5 ns\/op\npush_back O(1)\/op total O(N) | 0.032 ms | 10.7 ns\/op\npop_back O(N)\/op total O(N^2) | 11.561 ms | 3853.5 ns\/op\n\n=============================\nBENCH N=10000\n=============================\npush_front O(1)\/op total O(N) | 0.257 ms | 25.7 ns\/op\nfront O(1)\/op | 1.625 ms | 0.8 ns\/op (REPS=2000000)\nback O(1)\/op | 1.612 ms | 0.8 ns\/op (REPS=2000000)\npop_front O(1)\/op (+free) | 0.089 ms | 8.9 ns\/op\npush_back O(1)\/op total O(N) | 0.110 ms | 11.0 ns\/op\npop_back O(N)\/op total O(N^2) | 127.046 ms | 12704.6 ns\/op\n\n=============================\nBENCH N=30000\n=============================\npush_front O(1)\/op total O(N) | 0.775 ms | 25.8 ns\/op\nfront O(1)\/op | 1.611 ms | 0.8 ns\/op (REPS=2000000)\nback O(1)\/op | 1.623 ms | 0.8 ns\/op (REPS=2000000)\npop_front O(1)\/op (+free) | 0.281 ms | 9.4 ns\/op\npush_back O(1)\/op total O(N) | 0.313 ms | 10.4 ns\/op\npop_back O(N)\/op total O(N^2) | 1197.998 ms | 39933.3 ns\/op\n\n=============================\nBENCH N=100000\n=============================\npush_front O(1)\/op total O(N) | 2.449 ms | 24.5 ns\/op\nfront O(1)\/op | 1.588 ms | 0.8 ns\/op (REPS=2000000)\nback O(1)\/op | 1.570 ms | 0.8 ns\/op (REPS=2000000)\npop_front O(1)\/op (+free) | 1.006 ms | 10.1 ns\/op\npush_back O(1)\/op total O(N) | 1.133 ms | 11.3 ns\/op\npop_back O(N)\/op total O(N^2) | 15171.713 ms | 151717.1 ns\/op<\/code><\/pre>\n\n\n\n
We get HUGE speedups here in the back and push_back functionality, but what about that darned pop_back function?!<\/p>\n\n\n\n
Well, this occurs because despite us storing the tail of the list, a pop_back operation still requires that we retrieve the node BEFORE the current tail so that we can set it as the new tail. There are a few ways to approach this, but the one that transitions the best into the next day of our challenge is implementing a DOUBLY Linked List. This will allow us to show a chart that is fully O(1), but with some trade-offs that we will discuss when the time comes.<\/p>\n\n\n\n
Yesterday we went over a basic implementation of a Linked List that lacked a tail. In other words, the entire list was implicitly stored through the use of a single head node and all subsequent list operations used this head pointer. From this, we derived a complexity table: Complexity Table (Tailless List) Operation Complexity push_front […]<\/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-70","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/70","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=70"}],"version-history":[{"count":4,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/70\/revisions"}],"predecessor-version":[{"id":74,"href":"https:\/\/mattbick.dev\/index.php?rest_route=\/wp\/v2\/posts\/70\/revisions\/74"}],"wp:attachment":[{"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=70"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=70"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mattbick.dev\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=70"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}