Appending a Node, and Why It Costs More

Get access to whole semester resourcesSemester Pass

Chapter Eighteen

Syllabus topic Module 1, "Linked Structures: Prepending and Removing Nodes"

Pages 53 to 55 of 411

In one line

Appending means adding at the end, which costs a full walk to find the end, unless the list keeps a pointer to its last node, in which case it costs the same as prepending.

Why the end is far away

A singly linked list knows where it starts. Nothing in it knows where it ends: the only way to find the last node is to follow the chain until a node's next is null.

So the naive append is a traversal plus two assignments, and the traversal is the whole cost.

if head is null: head = new; stop

walk = head

while walk.next is not null: walk = walk.next

walk.next = new

Note while walk.next is not null and not while walk is not null. The loop must stop on the last node, not past it, because the last node is the one that has to be modified. Writing the traversal condition out of habit here is a standard mistake.

Measured

class Node:
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node


class SlowList:
    """Append by walking to the end every time."""

    def __init__(self):
        self.head = None
        self.steps = 0

    def append(self, value):
        new = Node(value)
        if self.head is None:
            self.head = new
            return
        walk = self.head
        while walk.next is not None:
            walk = walk.next
            self.steps += 1
        walk.next = new


for n in (100, 200, 400, 800):
    lst = SlowList()
    for i in range(n):
        lst.append(i)
    print("appended %4d nodes by walking: %7d pointer steps" % (n, lst.steps))

appended  100 nodes by walking:    4851 pointer steps
appended  200 nodes by walking:   19701 pointer steps
appended  400 nodes by walking:   79401 pointer steps
appended  800 nodes by walking:  318801 pointer steps

Double the nodes, quadruple the steps. Building a list by appending this way is O(n squared), which is exactly as bad as the array was at prepending. The structure that was supposed to make insertion cheap has become expensive, and only at one end.

The tail pointer

The fix is to remember the answer instead of recomputing it. Keep a second variable, tail, holding the address of the last node.

Append then becomes: point the old last node at the new one, and move the tail. Two assignments, O(1).

The price is that every operation that changes the end of the list must now maintain the tail, and forgetting is a real defect: the list keeps working for a while and then appends into a node that is no longer last.

class Node:
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node


class FastList:
    """Append in O(1) by keeping a pointer to the last node."""

    def __init__(self):
        self.head = None
        self.tail = None
        self.assignments = 0

    def append(self, value):
        new = Node(value)
        if self.head is None:
            self.head = self.tail = new        # both, on the first node
            self.assignments += 2
            return
        self.tail.next = new
        self.assignments += 1
        self.tail = new
        self.assignments += 1

    def to_list(self):
        out, walk = [], self.head
        while walk is not None:
            out.append(walk.data)
            walk = walk.next
        return out


lst = FastList()
for value in ("A", "B", "C"):
    lst.append(value)
    print("append %s ->" % value, lst.to_list(), "| tail holds", lst.tail.data)

print()
for n in (100, 200, 400, 800):
    big = FastList()
    for i in range(n):
        big.append(i)
    print("appended %4d nodes with a tail: %5d assignments, %d per node"
          % (n, big.assignments, big.assignments // n))

Appending a Node, and Why It Costs More

append A -> ['A'] | tail holds A
append B -> ['A', 'B'] | tail holds B
append C -> ['A', 'B', 'C'] | tail holds C

appended  100 nodes with a tail:   200 assignments, 2 per node
appended  200 nodes with a tail:   400 assignments, 2 per node
appended  400 nodes with a tail:   800 assignments, 2 per node
appended  800 nodes with a tail:  1600 assignments, 2 per node

Two per node at every size, the same as prepend. The 318,801 steps for 800 nodes became 1,600.

The general habit

This is worth naming, because the paper does it four more times.

When an operation recomputes something that could have been remembered, remember it. The cost is a little memory and the discipline of keeping the remembered thing correct.

Where	What is remembered	What it saves
this chapter	the last node	a full walk per append
chapter 14	the length	a full walk per length
chapter 82	a heap's shape, in an array	all the child pointers
chapter 107	the count of items in a hash table	recomputing the load factor

And the matching warning, which is the same every time: anything remembered must be updated by every operation that could invalidate it. A tail pointer that is not updated on deletion of the last node is worse than no tail pointer at all, because the list still looks correct.

What the tail cannot fix

A tail pointer makes appending cheap. It does not make deleting from the end cheap, and that catches people.

To delete the last node you must set the second to last node's next to null, and a singly linked list gives you no way to find the second to last node except by walking from the head. The tail pointer tells you where the end is, not what came before it.

Deleting from the end of a singly linked list is O(n) even with a tail pointer. Fixing that needs a backward link, which is the doubly linked list of chapter 26.

Appending a Node, and Why It Costs More

Quick revision

A singly linked list has no way to find its end except by walking; the naive append is O(n).
Building a list by naive appending is O(n squared): 800 nodes cost 318,801 pointer steps.
The append traversal stops on the last node, testing walk.next is not null, not walk is not null.
A tail pointer makes append O(1): measured at 2 assignments per node at every size.
On the first node, head and tail are both set to it.
Anything remembered must be maintained by every operation that could invalidate it.
A tail pointer does not make deletion from the end cheap: that needs the second to last node, which

only a backward link gives you.

Test yourself

1. Why is appending to a singly linked list O(n) without a tail pointer? Because nothing records where the list ends, so the last node must be found by following the chain from the head.

2. What is the cost of building an n node list by naive appending, and what did the run show? O(n squared). Doubling the nodes quadrupled the steps: 100 nodes cost 4,851 steps and 800 cost 318,801.

3. Why is the loop condition walk.next is not null rather than walk is not null? Because the operation must stop on the last node in order to modify it. The ordinary traversal condition would walk past the end.

4. What must be set when the first node is appended to an empty list? Both head and tail must be set to the new node.

5. State the general habit this chapter introduces, and its matching danger. Remember what would otherwise be recomputed. The danger is that anything remembered must be updated by every operation that could invalidate it, or the structure lies while still appearing to work.

6. Does a tail pointer make deleting the last node O(1)? Explain. No. Deleting the last node requires setting the second to last node's next to null, and a singly linked list can only find that node by walking from the head. It stays O(n) until a backward link exists.

The rest of this subject

These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.

Issue