Lists

These notes cover lists.

Singly-Linked Lists
Problems

Singly-Linked Lists

Here is a basic linked list, storing integers:

Each box is a node with a pointer to the next node (called the node's pointee), and the last node (above, the box containing 1) has a null pointee. We call the first node the head and the last node the tail. Linked lists have some notion of "ordering" in the sense that each node points to the next. They do not, however, have any inherent indices, as arrays do. Accordingly (and this is true for other connected data structures), the data stored within a linked list are spread across memory. As such, they do not perform nearly as well as arrays when it comes to both caching and read time. In particular, lists do not have constant time access — we must traverse the list to read.

With lists, however, we can insert in ${\bigO{1}}$ (assuming a correct implementation). We set create a new node ${p}$ containing the data 6, then traverse the list until we reach the node just before the point of insertion:

Then we have ${p}$ point to node-5's pointee ( ${\set{5}\to p}$ ), followed by node-5 changing its pointee to ${p}$ ( ${p \to \set{7}}$ ).

For the puzzles that follow, solutions use the following structure for a node:

node definition. Where ${\df{comparable}}$ is a data type such that ${=},$ ${\lt,}$ and ${\gt}$ return either true or false, and ${\df{node}^*}$ is a node pointer type, a ${\df{node}}$ is a product type ${\df{comparable} \times \df{node}^*,}$ where ${\df{comparable} \bij \tx{value}}$ and ${\df{node}^* \bij \tx{next}.}$

${{\textbf{structure}}\df{ node } \textbf{contains}}$

${\df{comparable}~~\tx{value}}$

${\df{node}^*~~\tx{next}}$

${\textbf{end}}$

Problems

List to Array

Given the head of a linked list ${L,}$ write an algorithm that returns the values stored in ${L}$ as an array.

This problem asks for a simple traversal. As we're asked to traverse the entire list, the approach below has a time complexity of ${\bigTheta{n},}$ and a space complexity of ${\bigTheta{n}.}$

list-to-array

Input: the head ${h}$ of a linked list ${L.}$
Output: an array ${A,}$ containing the values stored in ${L.}$

init
1. ${\let{p}{h}}$
2. ${\let{A}{\df{new empty array}}}$
while ${p \neq \nil}$ start loop body
1. ${A \push p \ix{\tx{value}}}$
2. ${\let{p}{p \ix{\tx{next}}}}$
3. ${\goto{3}}$ end loop body
return ${A}$

We can also implement this recursively:

recursive-list-to-array

Input: the head of a linked list ${L,}$ ${h.}$
Output: an array ${A,}$ containing the values stored in ${L.}$

init
1. ${\let{p}{h}}$
2. ${\let{A}{\df{new empty array}}}$
function ${\df{traverse}(p): \df{node}^* \mapsto \nil}$
1. if ${p = \nil}$ then return ${\nil}$
2. else
  1. ${A \push p \ix{\tx{value}}}$
  2. ${\df{traverse}(p\ix{\tx{next}})}$
${\df{traverse}(p)}$
return ${A}$

With the recursive approach, it's important to avoid situations of pass-by-value. For some languages (e.g., JavaScript), passing the entire array ${A}$ (rather than a reference or pointer to ${A}$ ) in a recursive call requires copying each value in ${A}$ to a new array ${A'.}$ This results in a time complexity of ${\bigO{n^2}.}$

Sum List

Given the head ${h}$ of a linked list containing integers, write an algorithm that returns the total sum of all values in the linked list.

Like list to array, computing the sum can be done iteratively:

listsum

Input: ${h,}$ the head of a linked list ${L}$ containing integers.
Output: ${S,}$ the sum total of each integer in ${L.}$

init
1. ${\let{p}{h}}$
2. ${\let{S}{0}}$
while ${p \neq \nil}$ begin loop body
1. ${\let{sum}{p \ix{\tx{value}}}}$
2. ${\let{p}{p \ix{\tx{next}}}}$
3. ${\goto{3}}$ end loop body
return ${S}$

This algorithm has a time complexity of ${\bigO{n},}$ and a space complexity of ${\bigO{1}.}$ A recursive implementation would also run on ${\bigO{n}}$ time, but with the added cost of ${\bigO{n}}$ space complexity, due to the call stack.

listsum

Input: ${h,}$ the head of a linked list ${L}$ containing integers.
Output: ${S,}$ the sum total of each integer in ${L.}$

if ${h = \nil}$ then return ${0}$
else ${\rw{h}{\tx{value}} + \df{listsum}(\rw{h}{\tx{next}})}$

Sequential Search

Given the head of a linked list and a target ${t,}$ write an algorithm that returns true (or 1) if ${t}$ is in the linked list, and false (or 0) otherwise. The target ${t}$ is of a type where ${=}$ is meaningful.

This is another problem handled easily by traversal. The algorithm below has a time complexity of order ${\bigO{n}}$ — since we must traverse the list — and the space complexity of order ${\bigO{1}.}$

seqfind

Input: ${h,}$ the head of a linked list ${L,}$ and ${t,}$ a target.
Output: true if ${t \in L,}$ false otherwise.

init ${\let{p}{h}}$
while ${p \neq \nil}$ begin loop body
1. if ${\rw{p}{\tx{value}}=t}$ then return ${\df{true}}$
2. ${\let{p}{p \ix{\tx{next}}}}$
3. ${\goto{1}}$ end loop body
return ${\df{false}}$

As usual, we can also implement this recursively:

seqfind

Input: ${h,}$ the head of a linked list ${L,}$ and ${t,}$ a target.
Output: true if ${t \in L,}$ false otherwise.

if ${h = \nil}$ return ${\df{false}}$
else if ${\rw{h}{\tx{value}} = t}$ then return ${\df{true}}$
else ${\df{seqfind}(\rw{h}{\tx{next}})}$

ith Element

Given the head of a linked list ${h}$ and index ${I \in \nat,}$ write an algorithm that returns the list element at the specified index. If there is no such element, return null.

There are many ways to go about this problem, some of which are tempting but wrong. A common mistake is an algorithm like the following:

getith

Input: the head of a linked list ${h}$ and an index ${I}$
Output: the element at index ${I}$

init
1. ${\let{p}{h}}$
2. ${\let{i}{0}}$
while ${i \lt I}$ begin loop body
1. ${\let{p}{p\ix{\tx{value}}}}$
2. ${+(i,1)}$
3. ${\goto{3}}$ end loop body
return ${p\ix{\tx{value}}}$

The problem with this approach is that there's no guard against ${p = \nil.}$ In the event that occurs — which is well within reason to expect — the very last line will return an error (hopefully; not all compilers or transpilers are so forgiving about dereferencing ${\nil}$ ). A correct approach would look like the following:

getith

Input: the head of a linked list ${h}$ and an index ${I}$
Output: the element at index ${I}$

init
1. ${\let{p}{h}}$
2. ${\let{i}{0}}$
while ${p \neq \nil}$ begin loop body
1. if ${i = I}$ return ${p\ix{\tx{value}}}$
2. ${\let{p}{\rw{p}{\tx{next}}}}$
3. ${+(i,1)}$
4. ${\goto{3}}$ end loop body
return ${\nil}$

This algorithm has a space complexity of order ${\bigO{1}}$ and a time complexity of order ${\bigO{n}.}$

getith

Input: the head of a linked list ${h}$ and an index ${I}$
Output: the element at index ${I}$

if ${h = \nil}$ return ${\nil}$
else if ${I = 0}$ return ${h\ix{\tx{value}}}$
else return ${\df{getith}(h\ix{\tx{next}},-(I,1))}$

The recursive solution has a time complexity of ${\bigO{n},}$ but unlike the iterative solution, has a space complexity of ${\bigO{n}.}$

Reverse List

Given the head ${h}$ of a linked list ${L,}$ write an algorithm that returns ${L}$ with its nodes reversed.

Before we reverse ${L,}$ we return ${\nil}$ immediately if ${h = \nil.}$ Otherwise, we continue. Suppose the list were:

We begin with three pointers, ${p}$ (for previous), ${c}$ (for current), and ${n}$ (for next). Initially, ${p}$ points to nothing, ${c}$ points to ${h,}$ and ${n}$ points to ${h\ix{\tx{next}}.}$ Then, so long as ${n \neq \nil:}$ (1) Assign ${p}$ to ${c}$ 's next (make current point to previous). (2) Assign ${c}$ to ${p}$ (move previous to current). (3) Assign ${c}$ to ${n}$ (move current to next). And (4) Assign ${n}$ 's next to ${n}$ (move ${n}$ forward).

\begin{array}{:c:c:} {\let{\rw{c}{\tx{next}}}{p}}& {\begin{matrix} &{c}&~&{n}&~&{~}&~&{~}&~&{~}&~&{~}& \\ p\gets&\boxed{1}&~&\boxed{2}&\to&\boxed{3}&\to&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{p}{c}}& {\begin{matrix} &{pc}&~&{n}&~&{~}&~&{~}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&~&\boxed{2}&\to&\boxed{3}&\to&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{c}{n}}& {\begin{matrix} &{p}&~&{cn}&~&{~}&~&{~}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&~&\boxed{2}&\to&\boxed{3}&\to&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{n}{\rw{n}{\tx{next}}}}& {\begin{matrix} &{p}&~&{c}&~&{n}&~&{~}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&~&\boxed{2}&\to&\boxed{3}&\to&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{\rw{c}{\tx{next}}}{p}}& {\begin{matrix} &{p}&~&{c}&~&{n}&~&{~}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&~&\boxed{3}&\to&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{p}{c}}& {\begin{matrix} &{~}&~&{pc}&~&{n}&~&{~}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&~&\boxed{3}&\to&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{c}{n}}& {\begin{matrix} &{~}&~&{p}&~&{cn}&~&{~}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&~&\boxed{3}&\to&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{n}{\rw{n}{\tx{next}}}}& {\begin{matrix} &{~}&~&{p}&~&{c}&~&{n}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&~&\boxed{3}&\to&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{\rw{c}{\tx{next}}}{p}}& {\begin{matrix} &{~}&~&{p}&~&{c}&~&{n}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&~&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{p}{c}}& {\begin{matrix} &{~}&~&{~}&~&{pc}&~&{n}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&~&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{c}{n}}& {\begin{matrix} &{~}&~&{~}&~&{p}&~&{cn}&~&{~}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&~&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{n}{\rw{n}{\tx{next}}}}& {\begin{matrix} &{~}&~&{~}&~&{p}&~&{c}&~&{n}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&~&\boxed{4}&\to&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{\rw{c}{\tx{next}}}{p}}& {\begin{matrix} &{~}&~&{~}&~&{p}&~&{c}&~&{n}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&\gets&\boxed{4}&~&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{p}{c}}& {\begin{matrix} &{~}&~&{~}&~&{~}&~&{pc}&~&{n}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&\gets&\boxed{4}&~&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{c}{n}}& {\begin{matrix} &{~}&~&{~}&~&{~}&~&{p}&~&{cn}&~&{~}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&\gets&\boxed{4}&~&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{n}{\rw{n}{\tx{next}}}}& {\begin{matrix} &{~}&~&{~}&~&{~}&~&{p}&~&{c}&~&{n}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&\gets&\boxed{4}&~&\boxed{5}&\to&\boxed{6}& \\ \end{matrix}} \\ {\let{\rw{c}{\tx{next}}}{p}}& {\begin{matrix} &{~}&~&{~}&~&{~}&~&{p}&~&{c}&~&{n}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&\gets&\boxed{4}&\gets&\boxed{5}&~&\boxed{6}& \\ \end{matrix}} \\ {\let{p}{c}}& {\begin{matrix} &{~}&~&{~}&~&{~}&~&{~}&~&{pc}&~&{n}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&\gets&\boxed{4}&\gets&\boxed{5}&~&\boxed{6}& \\ \end{matrix}} \\ {\let{c}{n}}& {\begin{matrix} &{~}&~&{~}&~&{~}&~&{~}&~&{p}&~&{cn}& \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&\gets&\boxed{4}&\gets&\boxed{5}&~&\boxed{6}& \\ \end{matrix}} \\ {\let{n}{\rw{n}{\tx{next}}}}& {\begin{matrix} &{~}&~&{~}&~&{~}&~&{~}&~&{p}&~&{c}&n \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&\gets&\boxed{4}&\gets&\boxed{5}&~&\boxed{6}& \\ \end{matrix}} \\ \end{array}

Once we've gone through the entire loop, all that's left is ${\let{c\ix{\tx{next}}}{p}:}$

{\begin{matrix} &{~}&~&{~}&~&{~}&~&{~}&~&{p}&~&{c}&n \\ \nil\gets&\boxed{1}&\gets&\boxed{2}&\gets&\boxed{3}&\gets&\boxed{4}&\gets&\boxed{5}&\gets&\boxed{6}& \\ \end{matrix}} \\

The iterative solution has a time complexity of order ${\bigO{n}}$ and a space complexity of ${\bigO{1}.}$

reverse

Input: ${h,}$ the head of a linked list ${L}$
Output ${h,}$ the head of a reversed ${L}$

if ${h = \nil}$ return ${h}$
else
1. ${\let{p}{\nil}}$
2. ${\let{c}{h}}$
3. ${\let{n}{\rw{n}{\tx{next}}}}$
4. while ${n \neq \nil}$
  1. ${\let{c\ix{\tx{next}}}{p}}$
  2. ${\let{p}{c}}$
  3. ${\let{c}{n}}$
  4. ${\let{n}{n\ix{\tx{next}}}}$
  5. ${\goto{5}}$
5. ${\let{c\ix{\tx{next}}}{p}}$
6. ${\let{h}{c}}$
7. return ${h}$

A recursive approach is much more concise:

reverse

Input: ${h,}$ the head of a linked list ${L}$
Output ${h,}$ the head of a reversed ${L}$

function ${f(h,\let{c}{\df{default}~\nil})}$
1. if ${h = \nil}$ return ${c}$
2. ${\let{n}{h\ix{\tx{next}}}}$
3. ${\let{h\ix{\tx{next}}}{c}}$
4. ${f(n,h)}$

The recursive approach has a time complexity of order ${\bigO{n},}$ but while it is noticeably simpler, it does have a space complexity of order ${\bigO{n}.}$

Zipper List

Given two list heads ${a}$ and ${b,}$ write an algorithm that zips their respective lists: The two lists merged into single linked list, where their nodes alternate. Should one be longer than the other, the final list must terminate with the longer's remaining nodes. Return the head of the zipped list.

ziplist

Input: two list heads ${H_1}$ and ${H_2.}$
Output: a zipped list ${h.}$

init
1. ${\let{head}{H_1}}$
2. ${\let{tail}{head}}$
3. ${\let{p_1}{\rw{H_1}{\tx{next}}}}$
4. ${\let{p_2}{H_2}}$
5. ${\let{step}{0}}$
while ${(p_1 \neq \nil \land p_2 \neq \nil)}$ begin loop body
1. if ${(step \rem 2) = 0}$
  1. ${\let{\rw{tail}{\tx{next}}}{p_2}}$
  2. ${\let{p_2}{\rw{p_2}{\tx{next}}}}$
2. else
  1. ${\let{\rw{t}{\tx{next}}}{p_1}}$
  2. ${\let{p_1}{\rw{p_1}{\tx{next}}}}$
3. ${\let{tail}{\rw{tail}{\tx{next}}}}$
4. ${+(step,1)}$
5. ${\goto{6}}$ end loop body
if ${p_1 \neq \nil}$ then ${\let{\rw{tail}{\tx{next}}}{p_1}}$
if ${p_2 \neq \nil}$ then ${\let{\rw{tail}{\tx{next}}}{p_2}}$
return ${head}$

Suppose ${a}$ and ${b}$ correspond to the following lists.

We're asked to construct the list:

It's easier to view this problem in terms of sets. We're given two posets:

a=\set{3,7,9,11,13} ~~~ b=\set{2,4,6}.

We then have two functions ${f}$ and ${g.}$ The former returns a current element in ${a,}$ the latter, ${b.}$ Because the final list is an alternates, we call ${f}$ and ${g}$ in alternum:

\ax{ 3 & 2 & 7 & 4 & 6 & 9 \\ f(a) & g(b) & f(a) & g(b) & f(a) & g(b) \\ }.

Once this is done, we append the elements of whatever remains, yielding the list:

This algorithm's time complexity is of order ${\bigO{\min\set{n,m}},}$ where ${n}$ and ${m}$ are the lengths of the two lists respectively. The use of ${\min}$ stems from iterating only in so far as the shortest list.

A recursive approach has a time complexity of order ${\bigO{n},}$ and a space complexity of order ${\bigO{n}.}$

ziplist

Input: two list heads ${H_1}$ and ${H_2.}$
Output: a zipped list ${h.}$

if ${(H_1 = \nil) \land (H_2 = \nil)}$ return ${\nil}$
if ${(H_1 = \nil)}$ return ${H_2}$
if ${(H_2 = \nil)}$ return ${H_1}$
${\let{next1}=\rw{H_1}{\tx{next}}}$
${\let{next2}=\rw{H_2}{\tx{next}}}$
${\let{\rw{H_1}{\tx{next}}}{H_2}}$
${\let{\rw{H_2}{\tx{next}}}{\df{ziplist}(next1,~next2)}}$
return ${H_1}$

List Merge

Let ${H_1}$ and ${H_2}$ be the heads of two nonempty lists ${L_1=(a_0,a_1,a_2,\ldots,a_{m-1})}$ and ${L_2=(b_0,b_1,b_2,\ldots,b_{m-1})}$ respectively, where ${L_1}$ has a length ${m}$ and ${L_2}$ has a length ${n,}$ not necessarily equal. The elements of ${L_1}$ and ${L_2}$ are integers, sorted in increasing order. Write an algorithm that merges ${L_1}$ and ${L_2,}$ the two lists together into single sorted linked list ${L_3,}$ whose elements are the elements of ${L_1}$ and ${L_2}$ sorted in increasing order. The algorithm must merge-in-place and the head of ${L_3.}$

This algorithm has a time complexity of order ${\bigO{\min\set{n,m}}}$ and a space complexity of order ${\bigO{1}.}$

sortedmerge

Input: a list head ${H_1}$ and a list head ${H_2,}$ wherein elements are sorted in increasing order.
Output: the head of a list comprising nodes of ${H_1}$ and ${H_2,}$ wherein elements are sorted in increasing order.

init
1. ${\let{D}{\df{new node}}}$
2. ${\let{t}{D}}$
3. if ${\rw{H_1}{\tx{next}} \gt \rw{H_2}{\tx{next}}}$
  1. then ${\let{\rw{t}{\tx{next}}}{\rw{H_1}{\tx{next}}}}$
4. else
  1. ${\let{\rw{t}{\tx{next}}}{\rw{H_2}{\tx{next}}}}$
5. ${\let{a}{H_1}}$
6. ${\let{b}{H_2}}$
while ${(t\ix{\tx{next}}\neq\nil)}$
1. if ${(a\ix{\tx{value}} \lt b\ix{\tx{value}})}$ then
  1. ${\let{t\ix{\tx{next}}}{a}}$
  2. ${\let{a}{a\ix{\tx{next}}}}$
2. else
  1. ${\let{t\ix{\tx{next}}}{b}}$
  2. ${\let{b}{b\ix{\tx{next}}}}$
3. ${\goto{9}}$
if ${a \neq \nil}$ then ${\let{\rw{t}{\tx{next}}}{a}}$
if ${b \neq \nil}$ then ${\let{\rw{t}{\tx{next}}}{b}}$
return ${\rw{D}{\tx{next}}}$

Univalue List

Given an integer list head ${h,}$ write an algorithm that returns true if the list contains exactly one unique value (i.e., all the list's nodes store the same integer), and false otherwise. The list is guaranteed to be non-empty.

The approach here is fairly straightforward. We set initialize a pointer ${p}$ with the head ${h,}$ then iterate through the list. If the data stored in ${p}$ 's pointee is not equal to the data stored in ${h}$ 's pointee (the first integer in the list), then we immediately return false, as there are multiple unique values. This algorithm has a time complexity of order ${\bigO{n},}$ and space complexity of order ${\bigO{1}.}$

univalue

Input: the head of a list ${h.}$
Output: a Boolean ${result.}$

init
1. ${\let{p}{h}}$
while ${p \neq \nil}$ begin loop body
1. if ${\rw{p}{\tx{value}}\neq\rw{h}{\tx{value}}}$ then
  1. return ${\df{false}}$
2. ${\let{p}{\rw{p}{\tx{next}}}}$
3. ${\goto{2}}$ end loop body
return ${\df{true}}$

Remove Node

Let ${h}$ be a head of a linked list ${L,}$ and ${t}$ an integer. Write an algorithm that deletes the ${L}$ node containing ${t}$ in place, and returns ${h.}$ If there are multiple instances of ${t,}$ remove only the first instance.

This problem is conducive to a three-pointer approach. We use three pointers, ${t}$ (a tailer), ${p}$ (a passenger), and ${d}$ (a driver), where ${d}$ is always ahead of ${p,}$ and ${p}$ is always ahead of ${t.}$ Initially, ${t}$ points to ${\nil,}$ ${p}$ points to the head ${h,}$ and ${d}$ points to ${h\ix{\tx{next}}}$ (the head's next pointer). Once established, we traverse, so long as ${p\ix{\tx{value}}}$ isn't equal to the target value ${t.}$ There are two possible cases with this approach. First, the target value could be stored in ${h,}$ in which case we never transition from our initial state:

${t}$	${p}$	${d}$
	${1 \mapsto}$	${2 \mapsto}$	${3 \mapsto}$	${4 \mapsto\nil}$

The second case is everything else — where we do transition states:

		${t}$	${p}$	${d}$
	${1 \mapsto}$	${2 \mapsto}$	${3 \mapsto}$	${4 \mapsto\nil}$

In the first case, ${t}$ is nothing more than a null pointer, so it isn't of any use. This causes us to branch at the end of the loop. The algorithm below has a time complexity of order ${\bigO{n},}$ and a space complexity of ${\bigO{1}.}$

remove-node

Input: a list head ${\h.}$
Output: the list head ${\h.}$

init
1. ${\let{t}{\nil}}$
2. ${\let{p}{\h}}$
3. ${\let{d}{\h{\ix{\tx{next}}}}}$
while ${\rw{p}{\tx{value}}\neq \nil}$
1. ${\let{t}{p}}$
2. ${\let{p}{d}}$
3. ${\let{d}{d\ix{\tx{next}}}}$
4. ${\goto{4}}$
if ${t = \nil}$ then
1. ${\let{\h}{d}}$
else
1. ${\let{\rw{t}{\tx{next}}}{d}}$
2. ${\let{p}{\nil}}$
return ${\h}$