Ivan's wiki

Site Tools

wiki:forward-list

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
wiki:forward-list [August 14, 2026 at 14:55] – Ivan Janevskiwiki:forward-list [August 14, 2026 at 15:10] (current) – external edit 127.0.0.1
Line 17: Line 17:
 | Insert/delete at head | O(1) | | Insert/delete at head | O(1) |
 | Insert after a given node | O(1) | | Insert after a given node | O(1) |
 +| Remove after a given node | O(1) |
 | Access by index | O(n) | | Access by index | O(n) |
 | Append to tail | O(n) | | Append to tail | O(n) |
 | Search | O(n) | | Search | O(n) |
 +| Reverse | O(n) |
  
 ## Structure ## Structure
-(TODO) write prose +A generic forward list separates the node type from the payload type by storing an opaque `void*` in each node, rather than embedding a fixed value type directly. The list itself is just a pointer to the head node; a `list_t` wrapper adds a tail pointer purely as an O(1) append optimization for this implementation, even though a minimal forward list does not strictly need one. Traversal still only moves forward through `ln_next`, and there is still no `ln_prev`. 
-(TODO) draw standalone latex figure here of 1 -> 2 -> 3 -> 4+ 
 +\documentclass[border=5pt]{standalone} 
 +\usepackage{tikz} 
 +\usetikzlibrary{arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}] 
 +  \foreach \i/\x in {1/0,2/1.6,3/3.2,4/4.8} { 
 +    \node[node] (n\i) at (\x,0) {\i}; 
 +  } 
 +  \foreach \i/\j in {1/2,2/3,3/4} { 
 +    \draw[thick,->] (n\i.east) -- (n\j.west); 
 +  } 
 +  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL}; 
 +\end{tikzpicture} 
 +\end{document}
  
 ```c ```c
Line 39: Line 55:
  
 ## Operations ## Operations
-(TODO): Write prose for each operation 
-Write standalone latex figure for each illustration 
-Write code for each opreation 
  
 ### Create ### Create
-list_create with calloc()+The list starts as a zeroed `list_t`: `ln_head` and `ln_tail` both NULL. `calloc()` is a convenient way to get this for free when the list itself is heap-allocated. 
 + 
 +```c 
 +list_t *list_create(void) { 
 +    return calloc(1, sizeof(list_t)); 
 +} 
 +``` 
 + 
 +\documentclass[border=5pt]{standalone} 
 +\usepackage{tikz} 
 +\usetikzlibrary{arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[>={Stealth[round]}] 
 +  \node (head) at (0,0) {head}; 
 +  \node (tail) at (2.4,0) {tail}; 
 +  \node[draw,thick,rectangle,minimum width=1.1cm,minimum height=0.6cm] (null) at (1.2,-1.3) {NULL}; 
 +  \draw[thick,->] (head.south) -- (null.north west); 
 +  \draw[thick,->] (tail.south) -- (null.north east); 
 +\end{tikzpicture} 
 +\end{document} 
 ### Destroy ### Destroy
-Free memory with free+Freeing the list means walking from `ln_head` to NULL, freeing each node, then freeing the list struct itself. The payload pointed to by `ln_data` is the caller's responsibility unless the list owns it. 
 + 
 +```c 
 +void list_destroy(list_t *list) { 
 +    list_node_t *cur = list->ln_head; 
 +    while (cur != NULL) { 
 +        list_node_t *next = cur->ln_next; 
 +        free(cur); 
 +        cur = next; 
 +    } 
 +    free(list); 
 +} 
 +``` 
 + 
 +\documentclass[border=5pt]{standalone} 
 +\usepackage{tikz} 
 +\usetikzlibrary{arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}] 
 +  \node[node] (n1) at (0,0) {1}; 
 +  \node[node] (n2) at (1.6,0) {2}; 
 +  \node[node] (n3) at (3.2,0) {3}; 
 +  \draw[thick,->] (n1.east) -- (n2.west); 
 +  \draw[thick,->] (n2.east) -- (n3.west); 
 +  \draw[thick,->] (n3.east) -- ++(1.2,0) node[right] {NULL}; 
 + 
 +  \node[node,draw=gray,dashed,text=gray] (m1) at (0,-2) {1}; 
 +  \node[node,draw=gray,dashed,text=gray] (m2) at (1.6,-2) {2}; 
 +  \node[node,draw=gray,dashed,text=gray] (m3) at (3.2,-2) {3}; 
 +  \foreach \n in {m1,m2,m3} { 
 +    \draw[gray,thick] (\n.south west) -- (\n.north east); 
 +    \draw[gray,thick] (\n.north west) -- (\n.south east); 
 +  } 
 +  \node[gray] at (1.6,-2.9) {free()'d, list = NULL}; 
 +\end{tikzpicture} 
 +\end{document} 
 ### Append ### Append
 +Because `ln_tail` is tracked, appending is O(1): the new node is linked after the current tail, and `ln_tail` is advanced. Without a tail pointer this would require an O(n) traversal, as noted above.
 +
 +```c
 +void list_append(list_t *list, void *data) {
 +    list_node_t *node = malloc(sizeof(list_node_t));
 +    node->ln_data = data;
 +    node->ln_next = NULL;
 +    if (list->ln_tail == NULL) {
 +        list->ln_head = list->ln_tail = node;
 +    } else {
 +        list->ln_tail->ln_next = node;
 +        list->ln_tail = node;
 +    }
 +}
 +```
 +
 +\documentclass[border=5pt]{standalone}
 +\usepackage{tikz}
 +\usetikzlibrary{arrows.meta}
 +\begin{document}
 +\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
 +  \node[node] (n1) at (0,0) {1};
 +  \node[node] (n2) at (1.6,0) {2};
 +  \node[node] (n3) at (3.2,0) {3};
 +  \node[node,draw=teal,thick,fill=teal!15] (n4) at (4.8,0) {4};
 +  \draw[thick,->] (n1.east) -- (n2.west);
 +  \draw[thick,->] (n2.east) -- (n3.west);
 +  \draw[teal,thick,->] (n3.east) -- (n4.west);
 +  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL};
 +  \node at (3.2,0.9) {tail (before)};
 +  \draw[thick,->,dashed] (3.2,0.65) -- (3.2,0.45);
 +  \node[teal] at (4.8,0.9) {tail (after)};
 +  \draw[teal,thick,->,dashed] (4.8,0.65) -- (4.8,0.45);
 +\end{tikzpicture}
 +\end{document}
 +
 ### Prepend ### Prepend
-### Sort+Prepending is O(1) regardless of whether a tail pointer exists, since it only ever touches the head. 
 + 
 +```c 
 +void list_prepend(list_t *list, void *data) { 
 +    list_node_t *node = malloc(sizeof(list_node_t)); 
 +    node->ln_data = data; 
 +    node->ln_next = list->ln_head; 
 +    list->ln_head = node; 
 +    if (list->ln_tail == NULL) { 
 +        list->ln_tail = node; 
 +    } 
 +} 
 +``` 
 + 
 +\documentclass[border=5pt]{standalone} 
 +\usepackage{tikz} 
 +\usetikzlibrary{arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}] 
 +  \node[node,draw=teal,thick,fill=teal!15] (n1) at (0,0) {1}; 
 +  \node[node] (n2) at (1.6,0) {2}; 
 +  \node[node] (n3) at (3.2,0) {3}; 
 +  \draw[teal,thick,->] (n1.east) -- (n2.west); 
 +  \draw[thick,->] (n2.east) -- (n3.west); 
 +  \draw[thick,->] (n3.east) -- ++(1.2,0) node[right] {NULL}; 
 +  \node[teal] at (0,0.9) {head (after)}; 
 +  \draw[teal,thick,->,dashed] (0,0.65) -- (0,0.45); 
 +  \node at (1.6,0.9) {head (before)}; 
 +  \draw[thick,->,dashed] (1.6,0.65) -- (1.6,0.45); 
 +\end{tikzpicture} 
 +\end{document} 
 + 
 +### Insert after 
 +Inserting after a given node is O(1) because it only touches two links: the new node's `ln_next` and the given node's `ln_next`. This is the operation a forward list is actually good at, and the reason algorithms hold onto a node pointer rather than an index when they can. If the given node happens to be the tail, `ln_tail` must be advanced too. 
 + 
 +```c 
 +void list_insert_after(list_t *list, list_node_t *node, void *data) { 
 +    list_node_t *n = malloc(sizeof(list_node_t)); 
 +    n->ln_data = data; 
 +    n->ln_next = node->ln_next; 
 +    node->ln_next = n; 
 +    if (list->ln_tail == node) { 
 +        list->ln_tail = n; 
 +    } 
 +} 
 +``` 
 + 
 +\documentclass[border=5pt]{standalone} 
 +\usepackage{tikz} 
 +\usetikzlibrary{arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}] 
 +  \node[node] (n1) at (0,0) {1}; 
 +  \node[node] (n2) at (1.6,0) {2}; 
 +  \node[node] (n3) at (3.2,0) {3}; 
 +  \node[node,draw=teal,thick,fill=teal!15] (nx) at (1.6,-1.6) {X}; 
 +  \draw[thick,->] (n1.east) -- (n2.west); 
 +  \draw[gray,thick,dashed] (n2.east) to[bend left=15] (n3.west); 
 +  \draw[teal,thick,->] (n2.south) -- (nx.north west); 
 +  \draw[teal,thick,->] (nx.north east) -- (n3.south); 
 +  \draw[thick,->] (n3.east) -- ++(1.2,0) node[right] {NULL}; 
 +\end{tikzpicture} 
 +\end{document} 
 + 
 +### Remove after 
 +The mirror of insert-after: freeing the node that follows a given one only touches links on either side of the doomed node, so it is O(1). This is why deleting a known node in a forward list needs a pointer to its *predecessor* rather than to the node itself, as noted above; remove-after is the operation that predecessor pointer is for. 
 + 
 +```c 
 +void list_remove_after(list_t *list, list_node_t *node) { 
 +    list_node_t *doomed = node->ln_next; 
 +    if (doomed == NULL) return; 
 +    node->ln_next = doomed->ln_next; 
 +    if (list->ln_tail == doomed) { 
 +        list->ln_tail = node; 
 +    } 
 +    free(doomed); 
 +} 
 +``` 
 + 
 +\documentclass[border=5pt]{standalone} 
 +\usepackage{tikz} 
 +\usetikzlibrary{arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}] 
 +  \node[node] (n1) at (0,0) {1}; 
 +  \node[node] (n2) at (1.6,0) {2}; 
 +  \node[node,draw=gray,dashed,text=gray] (n3) at (3.2,0) {3}; 
 +  \node[node] (n4) at (4.8,0) {4}; 
 +  \draw[thick,->] (n1.east) -- (n2.west); 
 +  \draw[gray,thick] (n3.south west) -- (n3.north east); 
 +  \draw[gray,thick] (n3.north west) -- (n3.south east); 
 +  \draw[thick,->] (n2.east) to[bend left=25] (n4.west); 
 +  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL}; 
 +  \node[gray] at (3.2,-0.9) {free()'d}; 
 +\end{tikzpicture} 
 +\end{document} 
 ### Search ### Search
-### ... most common oprations...+A linear scan comparing `ln_data` against a target using a caller-supplied comparator, since the list is generic over the payload type. 
 + 
 +```c 
 +list_node_t *list_search(list_t *list, void *key, int (*cmp)(void *, void *)) { 
 +    list_node_t *cur = list->ln_head; 
 +    while (cur != NULL) { 
 +        if (cmp(cur->ln_data, key) == 0) return cur; 
 +        cur = cur->ln_next; 
 +    } 
 +    return NULL; 
 +} 
 +``` 
 + 
 +\documentclass[border=5pt]{standalone} 
 +\usepackage{tikz} 
 +\usetikzlibrary{arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}] 
 +  \node[node] (n1) at (0,0) {7}; 
 +  \node[node] (n2) at (1.6,0) {3}; 
 +  \node[node,draw=orange,thick,fill=orange!15] (n3) at (3.2,0) {9}; 
 +  \node[node] (n4) at (4.8,0) {2}; 
 +  \draw[thick,->] (n1.east) -- (n2.west); 
 +  \draw[thick,->] (n2.east) -- (n3.west); 
 +  \draw[thick,->] (n3.east) -- (n4.west); 
 +  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL}; 
 +  \node[orange] at (3.2,-0.9) {key = 9, found}; 
 +\end{tikzpicture} 
 +\end{document} 
 + 
 +### Length 
 +Since there is no size field, computing the length costs an O(n) traversal. A forward list that needs frequent length queries should cache a count in `list_t` and maintain it in every insert/remove, trading a little bookkeeping for O(1) lookups. 
 + 
 +```c 
 +size_t list_length(list_t *list) { 
 +    size_t n = 0; 
 +    for (list_node_t *cur = list->ln_head; cur != NULL; cur = cur->ln_next) { 
 +        n++; 
 +    } 
 +    return n; 
 +} 
 +``` 
 + 
 +### Reverse 
 +Reversal is done in place with the classic three-pointer walk: `prev`, `cur`, and a saved `next` so the forward link isn't lost the moment it's overwritten. Each node's `ln_next` is flipped to point backward, and `prev` and `cur` both advance one step. The old head ends up as the new tail and vice versa, so both `ln_head` and `ln_tail` need updating. 
 + 
 +```c 
 +void list_reverse(list_t *list) { 
 +    list_node_t *prev = NULL; 
 +    list_node_t *cur = list->ln_head; 
 +    list->ln_tail = cur; 
 +    while (cur != NULL) { 
 +        list_node_t *next = cur->ln_next; 
 +        cur->ln_next = prev; 
 +        prev = cur; 
 +        cur = next; 
 +    } 
 +    list->ln_head = prev; 
 +} 
 +``` 
 + 
 +\documentclass[border=5pt]{standalone} 
 +\usepackage{tikz} 
 +\usetikzlibrary{arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}] 
 +  \node[node] (n1) at (0,0) {1}; 
 +  \node[node] (n2) at (1.6,0) {2}; 
 +  \node[node] (n3) at (3.2,0) {3}; 
 +  \node[node] (n4) at (4.8,0) {4}; 
 +  \draw[thick,->] (n1.east) -- (n2.west); 
 +  \draw[thick,->] (n2.east) -- (n3.west); 
 +  \draw[thick,->] (n3.east) -- (n4.west); 
 +  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL}; 
 + 
 +  \node[node,draw=teal,fill=teal!10] (m1) at (0,-2) {1}; 
 +  \node[node,draw=teal,fill=teal!10] (m2) at (1.6,-2) {2}; 
 +  \node[node,draw=teal,fill=teal!10] (m3) at (3.2,-2) {3}; 
 +  \node[node,draw=teal,fill=teal!10] (m4) at (4.8,-2) {4}; 
 +  \draw[teal,thick,<-] (m1.east) -- (m2.west); 
 +  \draw[teal,thick,<-] (m2.east) -- (m3.west); 
 +  \draw[teal,thick,<-] (m3.east) -- (m4.west); 
 +  \draw[teal,thick,->] (m1.west) -- ++(-1.2,0) node[left] {NULL}; 
 +\end{tikzpicture} 
 +\end{document} 
 + 
 +### Sort 
 +In-place sorting a singly linked list is naturally suited to merge sort: splitting the list in half only requires forward pointers (advance a slow and a fast pointer to find the midpoint), and merging two sorted forward lists only requires relinking `ln_next` pointers, no random access. Quicksort's partitioning step, by contrast, wants two-directional swaps, which the forward list cannot do efficiently. 
 + 
 +```c 
 +static list_node_t *split(list_node_t *head) { 
 +    list_node_t *slow = head, *fast = head->ln_next; 
 +    while (fast != NULL && fast->ln_next != NULL) { 
 +        slow = slow->ln_next; 
 +        fast = fast->ln_next->ln_next; 
 +    } 
 +    list_node_t *mid = slow->ln_next; 
 +    slow->ln_next = NULL; 
 +    return mid; 
 +} 
 + 
 +static list_node_t *merge(list_node_t *a, list_node_t *b, int (*cmp)(void *, void *)) { 
 +    list_node_t head = {0}; 
 +    list_node_t *tail = &head; 
 +    while (a != NULL && b != NULL) { 
 +        if (cmp(a->ln_data, b->ln_data) <= 0) { 
 +            tail->ln_next = a; 
 +            a = a->ln_next; 
 +        } else { 
 +            tail->ln_next = b; 
 +            b = b->ln_next; 
 +        } 
 +        tail = tail->ln_next; 
 +    } 
 +    tail->ln_next = (a != NULL) ? a : b; 
 +    return head.ln_next; 
 +} 
 + 
 +static list_node_t *merge_sort(list_node_t *head, int (*cmp)(void *, void *)) { 
 +    if (head == NULL || head->ln_next == NULL) return head; 
 +    list_node_t *mid = split(head); 
 +    return merge(merge_sort(head, cmp), merge_sort(mid, cmp), cmp); 
 +} 
 + 
 +void list_sort(list_t *list, int (*cmp)(void *, void *)) { 
 +    list->ln_head = merge_sort(list->ln_head, cmp); 
 +    list_node_t *cur = list->ln_head; 
 +    while (cur != NULL && cur->ln_next != NULL) { 
 +        cur = cur->ln_next; 
 +    } 
 +    list->ln_tail = cur; 
 +} 
 +``` 
 + 
 +\documentclass[border=5pt]{standalone} 
 +\usepackage{tikz} 
 +\usetikzlibrary{arrows.meta} 
 +\begin{document} 
 +\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}] 
 +  \node[node] (b1) at (0,0) {3}; 
 +  \node[node] (b2) at (1.6,0) {1}; 
 +  \node[node] (b3) at (3.2,0) {4}; 
 +  \node[node] (b4) at (4.8,0) {2}; 
 +  \draw[thick,->] (b1.east) -- (b2.west); 
 +  \draw[thick,->] (b2.east) -- (b3.west); 
 +  \draw[thick,->] (b3.east) -- (b4.west); 
 +  \draw[thick,->] (b4.east) -- ++(1.2,0) node[right] {NULL}; 
 +  \node at (-1.1,0) {before}; 
 + 
 +  \node[node,draw=teal,fill=teal!10] (a1) at (0,-2) {1}; 
 +  \node[node,draw=teal,fill=teal!10] (a2) at (1.6,-2) {2}; 
 +  \node[node,draw=teal,fill=teal!10] (a3) at (3.2,-2) {3}; 
 +  \node[node,draw=teal,fill=teal!10] (a4) at (4.8,-2) {4}; 
 +  \draw[teal,thick,->] (a1.east) -- (a2.west); 
 +  \draw[teal,thick,->] (a2.east) -- (a3.west); 
 +  \draw[teal,thick,->] (a3.east) -- (a4.west); 
 +  \draw[teal,thick,->] (a4.east) -- ++(1.2,0) node[right] {NULL}; 
 +  \node at (-1.1,-2) {after}; 
 +\end{tikzpicture} 
 +\end{document}
wiki/forward-list.md · Last modified: (external edit)