Practical 2: Building a Singly Linked List

Chapter Twenty-Three

Syllabus topic Module 2, practical 2, "Linked List Manipulation: Write a program to: Create a singly linked list. Insert a node at the beginning, end, and at a given position in a linked list."

Pages 144 to 151 of 297

Aim

To create a singly linked list, and to insert a node at the beginning, at the end and at a given position.

The picture, which is the whole idea

head -> [ 10 | * ] -> [ 20 | * ] -> [ 30 | None ]
                                        ^
                                        tail

A node holds one value and a reference to the next node. The last node's reference is None, which is how the end is recognised. The list itself is nothing but a reference to the first node, called the head.

Nothing in that picture is contiguous. The three nodes may be anywhere in memory and the arrows are all that hold them together. Every difference from an array follows from that one fact:

	Array	Singly linked list
The items are	side by side in one block	anywhere, joined by references
Item n is found by	arithmetic, one step	walking n references, O(n)
Inserting at the front	every item shifts, O(n)	one new node, O(1)
Inserting at the back	O(1) if there is room	O(1) with a tail, O(n) without
Growing	a new block and a copy	nothing to do
Memory for n items	n slots, plus spare	n values plus n references
Going backwards	yes, subtract 1	no

The last row is the defect that a doubly linked list exists to cure, and it is why delete in the next chapter needs a trailing reference.

The three things the class keeps

head, the first node, or None when the list is empty.
tail, the last node. Optional, and worth having: without it, appending has to walk the whole

list.

count, how many nodes there are. Optional, and worth having, or len() has to walk.

Keeping a tail and a count means every operation must maintain them, and forgetting one is the commonest bug in this exercise. Inserting into an empty list must set the tail as well as the head.

The class

"""A singly linked list, built by hand for Major Practical 3, Module 2."""


class Node:
    """One item, and the reference to the next one."""

    def __init__(self, data, nxt=None):
        self.data = data
        self.nxt = nxt

    def __repr__(self):
        return f"Node({self.data!r})"


class SinglyLinkedList:
    """The container. It owns the head, the tail and the count."""

    def __init__(self, items=()):
        self.head = None
        self.tail = None
        self.count = 0
        self.steps = 0
        for item in items:
            self.insert_at_end(item)

    # ---- asking about it -------------------------------------------------
    def is_empty(self):
        return self.head is None

    def __len__(self):
        return self.count

    def __iter__(self):
        here = self.head
        while here is not None:
            yield here.data
            here = here.nxt

    def __repr__(self):
        if self.is_empty():
            return "head -> None   (empty, 0 nodes)"
        chain = " -> ".join(f"[ {item} | * ]" for item in self)
        return f"head -> {chain[:-9]}[ {list(self)[-1]} | None ]   ({self.count} nodes)"

    def as_chain(self):
        """A plain readable form for the journal."""
        if self.is_empty():
            return "None   (empty)"
        return " -> ".join(str(item) for item in self) + " -> None"

    # ---- inserting -------------------------------------------------------
    def insert_at_beginning(self, data):
        """MU's first case. One step, whatever the length."""
        node = Node(data, self.head)
        self.head = node
        if self.tail is None:
            self.tail = node
        self.count += 1
        return 0

    def insert_at_end(self, data):
        """MU's second case. One step, BECAUSE a tail is kept."""
        node = Node(data)
        if self.is_empty():
            self.head = node
        else:
            self.tail.nxt = node
        self.tail = node
        self.count += 1
        return 0

    def insert_at_position(self, position, data):
        """MU's third case. Walks to the node before the position.

        position 0 is the beginning and position len(self) is the end.
        Returns how many nodes had to be walked past.
        """
        if not 0 <= position <= self.count:
            raise IndexError(
                f"cannot insert at {position}; 0 to {self.count} allowed")
        if position == 0:
            return self.insert_at_beginning(data)
        if position == self.count:
            return self.insert_at_end(data)
        before = self.head
        walked = 0
        for _ in range(position - 1):
            before = before.nxt
            walked += 1
        before.nxt = Node(data, before.nxt)
        self.count += 1
        self.steps += walked
        return walked

    # ---- looking ---------------------------------------------------------
    def traverse(self):
        """Every value, front to back, with the nodes visited counted."""
        values = []
        here = self.head
        visited = 0
        while here is not None:
            values.append(here.data)
            visited += 1
            here = here.nxt
        return values, visited

    def search(self, value):
        """The position of the first match and the nodes visited, or (-1, n)."""
        here = self.head
        position = 0
        while here is not None:
            if here.data == value:
                return position, position + 1
            here = here.nxt
            position += 1
        return -1, position

    def get(self, position):
        """The value at a position. O(n), which is the whole point."""
        if not 0 <= position < self.count:
            raise IndexError(f"no position {position} in a list of {self.count}")
        here = self.head
        for _ in range(position):
            here = here.nxt
        return here.data

Practical 2: Building a Singly Linked List

Five things in that file are the marks.

insert_at_beginning builds the node first and only then moves the head. Two assignments, in that order. Reverse them and the rest of the list is lost, which the section below shows.

insert_at_end uses the tail, so it is two assignments rather than a walk. Without a tail it would be O(n), and building n items by appending would be O(n squared).

Both of them check for an empty list, because inserting the first node has to set the head and the tail.

insert_at_position walks to the node BEFORE the position, because a new node is linked in by changing the nxt of the node in front of it. position - 1 steps, not position.

Practical 2: Building a Singly Linked List

position 0 and position == count are handed to the other two methods, which removes the special cases from the middle of the walk.

Creating the list and inserting all three ways

from linked import SinglyLinkedList

items = SinglyLinkedList()
print("empty                    ", items.as_chain(), f"  len {len(items)}")

items.insert_at_end(10)
print("insert_at_end(10)        ", items.as_chain(), f"  len {len(items)}")

items.insert_at_end(20)
items.insert_at_end(30)
print("two more at the end      ", items.as_chain(), f"  len {len(items)}")

items.insert_at_beginning(5)
print("insert_at_beginning(5)   ", items.as_chain(), f"  len {len(items)}")

walked = items.insert_at_position(2, 15)
print("insert_at_position(2, 15)", items.as_chain(),
      f"  len {len(items)}  walked {walked}")

walked = items.insert_at_position(0, 1)
print("insert_at_position(0, 1) ", items.as_chain(),
      f"  len {len(items)}  walked {walked}")

walked = items.insert_at_position(len(items), 99)
print("insert at the very end   ", items.as_chain(),
      f"  len {len(items)}  walked {walked}")

print()
print("head is", items.head, "and tail is", items.tail)
print("the tail's nxt is", items.tail.nxt, "which is how the end is known")

empty                     None   (empty)   len 0
insert_at_end(10)         10 -> None   len 1
two more at the end       10 -> 20 -> 30 -> None   len 3
insert_at_beginning(5)    5 -> 10 -> 20 -> 30 -> None   len 4
insert_at_position(2, 15) 5 -> 10 -> 15 -> 20 -> 30 -> None   len 5  walked 1
insert_at_position(0, 1)  1 -> 5 -> 10 -> 15 -> 20 -> 30 -> None   len 6  walked 0
insert at the very end    1 -> 5 -> 10 -> 15 -> 20 -> 30 -> 99 -> None   len 7  walked 0

head is Node(1) and tail is Node(99)
the tail's nxt is None which is how the end is known

Read the walk counts. Inserting at the beginning or at the end walked past nothing at all, because the head and the tail are held. Inserting at position 2 walked past one node, to reach the node before it. That is the linked list's bargain: cheap at the ends, and a walk in the middle.

The two cases that break a wrong answer

from linked import SinglyLinkedList

print("an EMPTY list:")
empty = SinglyLinkedList()
print("  is_empty      ", empty.is_empty())
print("  len           ", len(empty))
print("  chain         ", empty.as_chain())
print("  traverse      ", empty.traverse())
print("  search for 10 ", empty.search(10))
empty.insert_at_beginning(10)
print("  after inserting one at the beginning:")
print("    head", empty.head, " tail", empty.tail, " same node?", empty.head is empty.tail)

print()
print("a ONE NODE list:")
one = SinglyLinkedList([42])
print("  chain         ", one.as_chain())
print("  head is tail? ", one.head is one.tail)
one.insert_at_end(43)
print("  after an append:", one.as_chain(), " tail now", one.tail)
one.insert_at_beginning(41)
print("  after a prepend:", one.as_chain(), " head now", one.head,
      " tail still", one.tail)

an EMPTY list:
  is_empty       True
  len            0
  chain          None   (empty)
  traverse       ([], 0)
  search for 10  (-1, 0)
  after inserting one at the beginning:
    head Node(10)  tail Node(10)  same node? True

a ONE NODE list:
  chain          42 -> None
  head is tail?  True
  after an append: 42 -> 43 -> None  tail now Node(43)
  after a prepend: 41 -> 42 -> 43 -> None  head now Node(41)  tail still Node(43)

Practical 2: Building a Singly Linked List

In an empty list the head and the tail are the same node after the first insertion, and in a one node list they already are. An answer that sets only the head when inserting into an empty list leaves the tail as None, and then the next insert_at_end raises AttributeError on self.tail.nxt. That is the bug this section exists to prevent.

The order of the two assignments

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


def chain(head):
    parts = []
    here = head
    while here is not None:
        parts.append(str(here.data))
        here = here.nxt
    return " -> ".join(parts) + " -> None"


# build 20 -> 30
head = Node(20, Node(30))
print("before          ", chain(head))

# the RIGHT order: point the new node at the old head, then move the head
node = Node(10, head)
head = node
print("right order     ", chain(head))

# the WRONG order, on a fresh list
head2 = Node(20, Node(30))
wrong = Node(10)
head2 = wrong          # the head moves first
wrong.nxt = head2      # and now it points at ITSELF, not at the old list
print("wrong order     ", chain(head2) if head2.nxt is not head2 else
      "head points at itself, so the list is one node and the rest is lost")

before           20 -> 30 -> None
right order      10 -> 20 -> 30 -> None
wrong order      head points at itself, so the list is one node and the rest is lost

The wrong order loses everything after the new node, because by the time the link is set the old head has already been forgotten. Build the new node with its link, then move the head. In one line: self.head = Node(data, self.head).

What each operation costs, counted

from linked import SinglyLinkedList

sizes = [10, 100, 1000]
print(f"{'n':>6} {'get(0)':>8} {'get(n-1)':>10} {'search first':>14} {'search last':>13}"
      f" {'search absent':>15}")
for n in sizes:
    items = SinglyLinkedList(range(n))
    _, first_steps = items.search(0)
    _, last_steps = items.search(n - 1)
    _, absent_steps = items.search(-1)
    print(f"{n:>6} {1:>8} {n:>10} {first_steps:>14} {last_steps:>13} {absent_steps:>15}")

print()
items = SinglyLinkedList(range(10))
print("insert_at_position walk counts on a list of 10:")
for position in [0, 1, 5, 9, 10]:
    test = SinglyLinkedList(range(10))
    print(f"  position {position:>2} walked {test.insert_at_position(position, 99):>2} node(s)")

     n   get(0)   get(n-1)   search first   search last   search absent
    10        1         10              1            10              10
   100        1        100              1           100             100
  1000        1       1000              1          1000            1000

insert_at_position walk counts on a list of 10:
  position  0 walked  0 node(s)
  position  1 walked  0 node(s)
  position  5 walked  4 node(s)
  position  9 walked  8 node(s)
  position 10 walked  0 node(s)

Practical 2: Building a Singly Linked List

Operation	Cost	Why
`insert_at_beginning`	O(1)	two assignments, and the head is held
`insert_at_end`	O(1)	two assignments, because a tail is held
`insert_at_position(p)`	O(p)	walk to the node before p
`get(p)`	O(p), so O(n)	there is no arithmetic on an address
`search`	O(n)	up to every node is visited
`traverse`	O(n)	every node once
`len`	O(1)	because a count is kept

The array against the linked list, measured

from linked import SinglyLinkedList


class CountingArray:
    """A fixed array, counting the values it shifts."""

    def __init__(self, capacity):
        self.slots = [None] * capacity
        self.size = 0

    def insert(self, index, value):
        moved = 0
        for i in range(self.size, index, -1):
            self.slots[i] = self.slots[i - 1]
            moved += 1
        self.slots[index] = value
        self.size += 1
        return moved


n = 500

array = CountingArray(n + 1)
array_moves = 0
for value in range(n):
    array_moves += array.insert(0, value)

items = SinglyLinkedList()
list_moves = 0
for value in range(n):
    list_moves += items.insert_at_beginning(value)

print(f"building {n} items AT THE FRONT")
print(f"  array       : {array_moves} value(s) moved")
print(f"  linked list : {list_moves} value(s) moved")
print()

array2 = CountingArray(n)
for value in range(n):
    array2.insert(array2.size, value)
items2 = SinglyLinkedList(range(n))

middle = n // 2
print(f"reading the middle item of {n}")
print(f"  array       : 1 step, it is arithmetic")
_, steps = items2.search(middle)
print(f"  linked list : {steps} step(s), it has to walk")

building 500 items AT THE FRONT
  array       : 124750 value(s) moved
  linked list : 0 value(s) moved

reading the middle item of 500
  array       : 1 step, it is arithmetic
  linked list : 251 step(s), it has to walk

Read those two blocks against each other, because together they are the answer to "which is better", and the answer is neither.

Building at the front, the array moved a value for every item already there and the linked list moved nothing at all. Reading the middle item, the array did it in one step and the linked list walked halfway.

So the choice is decided by what the program does most, which is MU's Course Objective 8 exactly. A linked list trades position arithmetic for cheap insertion. Say that sentence at the table and the follow up question is answered before it is asked.

Procedure

Save linked.py with Node holding data and nxt, and SinglyLinkedList holding head,

tail and count, both with __repr__.

Write insert_at_beginning: build the node pointing at the old head, then move the head, and

set the tail too if the list was empty.

Write insert_at_end using the tail, handling the empty list.
Write insert_at_position, checking the bounds, walking position - 1 nodes, and handing

position 0 and position count to the other two methods.

Practical 2: Building a Singly Linked List

Write traverse, search and get, each counting the nodes it visits.
In a second file, build a list, insert at the beginning, at the end and at a position, and print

the chain after every step with the walk count.

Test the empty list and the one node list explicitly, and print whether the head and the tail

are the same node.

Write the wrong order of the two assignments and record what it does.
Count the search steps for the first, the last and an absent value, for n of 10, 100 and 1000.
Compare with an array on building at the front and on reading the middle.

Result

The list was created empty and grown to seven nodes by all three insertions. Inserting at the beginning and at the end walked past no nodes; inserting at position 2 walked past one. On the empty list, the first insertion set the head and the tail to the same node. Reversing the two assignments in insert_at_beginning left the new node pointing at itself and lost the rest of the list. Search steps were 1 for the first value, n for the last and n for an absent value, at every size tried. Building 500 items at the front moved 124750 values in the array and none at all in the linked list; reading the middle item took 1 step in the array and 251 in the list.

Where marks are lost

Using a Python list and calling it a linked list. The exercise is the nodes.
No tail, and then claiming insert_at_end is O(1). Without a tail it is O(n).
Not setting the tail when inserting into an empty list, so the next append raises

AttributeError.

Moving the head before linking the new node, which loses the rest of the list.
Walking position nodes instead of position - 1, which inserts one place too far along.
No bounds check on the position.
No __repr__, so the output is a column of memory addresses.
Not testing the empty and one node cases. They are where a wrong answer fails.
Saying a linked list is faster than an array. It is faster at one thing and thousands of times

slower at another, and the marks are in saying which.

For the journal

The aim in MU's words, all three insertions. The picture first, three nodes with their references and the trailing None, because that diagram is worth a mark on its own. Then the seven row table of array against linked list. Then linked.py in full and the driver, with the chain printed after every insertion and the walk count beside it. Then the empty and one node tests with the head and tail lines. Then the wrong order of the two assignments and what it produced, with one sentence: build the node with its link, then move the head. Then the measured comparison, both figures. The conclusion: a linked list is a chain of nodes joined by references, so it inserts at either end in one step and has to walk to reach position n, which is the exact opposite of an array.

Practical 2: Building a Singly Linked List

Quick revision

A node holds a value and a reference to the next. The last reference is None.
The list is a reference to the first node, the head. Keep a tail and a count too.
Every operation must maintain all three. Inserting into an empty list sets the head and the

tail.

At the beginning: self.head = Node(data, self.head). Build first, then move the head.
At the end: self.tail.nxt = node then self.tail = node. O(1) only because of the tail.
At a position: walk position - 1 nodes to reach the one BEFORE it, then

before.nxt = Node(data, before.nxt).

Position 0 is the beginning and position count is the end; hand both to the other methods.
Costs: both ends O(1), at position p O(p), get and search O(n), len O(1) with a

count.

Measured: building 500 items at the front moved 124750 values in an array and 0 in a list;

reading the middle took 1 step in the array and 251 in the list.

A linked list has no way back from a node to the one before it. That is why the next chapter needs

a trailing reference.

Questions you should be able to answer

1. What does a node hold, and what marks the end of the list? A value and a reference to the next node. The last node's reference is None.

2. What is the head? The reference to the first node, which is the only thing the list itself holds. It is None when the list is empty.

3. Write insert_at_beginning in one line. self.head = Node(data, self.head), then update the tail if the list was empty and increase the count.

4. What goes wrong if you move the head before linking the new node? The old head has already been forgotten, so the new node ends up pointing at itself or at nothing and the rest of the list is lost.

5. Why does insert_at_end need a tail? Without one it has to walk from the head to the last node, which is O(n), so building n items by appending would cost n squared steps. With a tail it is two assignments.

Practical 2: Building a Singly Linked List

6. Inserting at position 5, how many nodes do you walk past, and to which one? Four, to reach position 4, the node before the insertion point, because linking a node in means changing the nxt of the node in front of it.

7. What must happen when you insert into an empty list? Both the head and the tail must be set to the new node. Setting only the head leaves the tail None and the next append fails.

8. What does get(n) cost, and why is it not O(1)? O(n). There is no address arithmetic, because the nodes are not side by side, so the only way to position n is to follow n references.

9. Which is better, an array or a linked list? Neither. Counted here: building 500 items at the front moved 124750 values in the array and none in the list, while reading the middle item took 1 step in the array and 251 in the list.

10. Why can a singly linked node not reach the node before it? Because it holds only a forward reference. That is the defect a doubly linked list cures, and it is why deletion needs a trailing reference.

The rest of this subject

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

Syllabus for Major Practical 3

Report or request