Practical 12: Singly Linked Lists

The four operations worth reading twice

prepend is the cheap one. A new node whose nxt is the old head, and then the head is the new node. Two assignments, whatever the length of the list. The order matters: build the node pointing at the old head first, then move the head. Reversing those two lines loses the whole list.

append is cheap only because of the tail. Without self.tail it would have to walk to the end, and appending n items would cost n squared steps in total. The two cases are the empty list, where head and tail both become the new node, and everything else, where the old tail's nxt is set and then the tail moves.

remove needs a trailing pointer, and this is the idea to take away from the chapter:

before = None
here = self.head
while here is not None and here.data != target:
    before = here
    here = here.nxt

A singly linked node cannot reach its predecessor, so to unlink a node you must already be holding the one in front of it. before walks one step behind here for exactly that reason. Then three cases:

Note that the first and third can both be true, when the list had one node: then head becomes None and tail becomes before, which is None. The code handles it without a special case, which is worth checking on paper.

reverse turns every link round in one pass, and it is a favourite examination question:

before = None
here = self.head
while here is not None:
    after = here.nxt        # remember where we were going
    here.nxt = before       # turn this link round
    before = here           # step both pointers on
    here = after
self.head = before

Three pointers and no new nodes. after has to be saved before here.nxt is overwritten, or the rest of the list is lost; that single line is what the question is testing. The run above shows the head and the tail swapping over, which is the other half of getting it right.

Making the list behave like a Python container

Three special methods, and each buys something:

__iter__ is written with yield, which makes it a generator: it produces one item at a time without building a list of them. That is why __repr__ can be written as one line over self, and why for name in lst: costs no extra memory however long the list is.

__contains__ is defined here in terms of search, so in and search can never disagree. Writing the traversal twice is how two methods come to answer differently.

MU's application: a playlist

MU names a playlist or a to-do list. A playlist is the better example, because it needs one thing an array makes awkward: a pointer to the item currently playing, which must survive songs being added and removed around it.

class Song:
    def __init__(self, title, minutes):
        self.title = title
        self.minutes = minutes

    def __repr__(self):
        return f"{self.title} ({self.minutes} min)"


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


class Playlist:
    """A singly linked list with a pointer to what is playing."""

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

    def add(self, song):
        node = Node(song)
        if self.tail is None:
            self.head = self.tail = node
            self.playing = node
        else:
            self.tail.nxt = node
            self.tail = node
        self.count += 1

    def play_next(self):
        """Move on. At the end, wrap round to the beginning."""
        if self.playing is None:
            raise IndexError("the playlist is empty")
        self.playing = self.playing.nxt if self.playing.nxt else self.head
        return self.playing.data

    def now_playing(self):
        if self.playing is None:
            raise IndexError("the playlist is empty")
        return self.playing.data

    def remove(self, title):
        before, here = None, self.head
        while here is not None and here.data.title != title:
            before, here = here, here.nxt
        if here is None:
            raise ValueError(f"{title!r} is not in the playlist")
        if before is None:
            self.head = here.nxt
        else:
            before.nxt = here.nxt
        if here is self.tail:
            self.tail = before
        if here is self.playing:               # what was playing has gone
            self.playing = here.nxt or self.head
        self.count -= 1

    def total_minutes(self):
        total, here = 0, self.head
        while here is not None:
            total += here.data.minutes
            here = here.nxt
        return total

    def show(self):
        here = self.head
        while here is not None:
            mark = " <- playing" if here is self.playing else ""
            print(f"    {here.data}{mark}")
            here = here.nxt
        print(f"    {self.count} song(s), {self.total_minutes()} minutes")


p = Playlist()
for title, mins in (("Ae Dil Hai Mushkil", 4),
                    ("Kun Faya Kun", 8),
                    ("Tum Hi Ho", 5),
                    ("Channa Mereya", 5)):
    p.add(Song(title, mins))

print("the playlist")
p.show()

print()
print("now playing :", p.now_playing())
print("next        :", p.play_next())
print("next        :", p.play_next())
print("next        :", p.play_next())
print("next wraps  :", p.play_next())

print()
p.remove("Kun Faya Kun")
print("after removing Kun Faya Kun")
p.show()

print()
p.play_next()
print("now playing :", p.now_playing())
p.remove("Tum Hi Ho")
print("that was what was playing; it moves on to:", p.now_playing())
p.show()

the playlist
    Ae Dil Hai Mushkil (4 min) <- playing
    Kun Faya Kun (8 min)
    Tum Hi Ho (5 min)
    Channa Mereya (5 min)
    4 song(s), 22 minutes

now playing : Ae Dil Hai Mushkil (4 min)
next        : Kun Faya Kun (8 min)
next        : Tum Hi Ho (5 min)
next        : Channa Mereya (5 min)
next wraps  : Ae Dil Hai Mushkil (4 min)

after removing Kun Faya Kun
    Ae Dil Hai Mushkil (4 min) <- playing
    Tum Hi Ho (5 min)
    Channa Mereya (5 min)
    3 song(s), 14 minutes

now playing : Tum Hi Ho (5 min)
that was what was playing; it moves on to: Channa Mereya (5 min)
    Ae Dil Hai Mushkil (4 min)
    Channa Mereya (5 min) <- playing
    2 song(s), 9 minutes

Three things that program does which are the reason a linked list suits the job.

The playing pointer is a node, not an index. With a Python list and an index of 2, removing the song at index 0 makes the index wrong: it now points at the song after the one that was playing. With a reference to a node, removing something else does not disturb it at all.

Wrapping round is one line. self.playing.nxt if self.playing.nxt else self.head, or equivalently self.playing.nxt or self.head, gives repeat-all for nothing. A circular linked list, where the last node's nxt is the head rather than None, makes even that unnecessary, and the ready queue of [Practical 8: CPU Scheduling, Round Robin] is exactly that structure.

Removing what is playing has to be handled. The last part of the run shows it: Tum Hi Ho was playing, it was removed, and the pointer moved on to the next song rather than being left pointing at a node that is no longer in the list. A program that forgets this case keeps playing a song that the user has deleted, which is a bug a user notices immediately.

The to-do list, which is the same structure

MU offers a to-do list as the alternative, and it needs nothing new: a Task with a description and a done flag instead of a Song, add at the tail so that tasks stay in the order they were written, remove by description, and a traversal that prints [x] or [ ]. Everything else is the program above. If your college sets the to-do list, that is the change.

MU's third bullet: the array against the linked list, measured

The two structures are good at opposite things, so one measurement flatters whichever was chosen. This program measures both.

from time import perf_counter


class Node:
    __slots__ = ("data", "nxt")           # a little less memory per node

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


def build_linked_at_front(n):
    head = None
    for i in range(n):
        head = Node(i, head)              # one new node, no shifting
    return head


def build_array_at_front(n):
    items = []
    for i in range(n):
        items.insert(0, i)                # everything moves up one
    return items


def walk(head, want):
    at, here = 0, head
    while here is not None:
        if here.data == want:
            return at
        here, at = here.nxt, at + 1
    return -1


N = 20000

start = perf_counter()
head = build_linked_at_front(N)
linked_build = perf_counter() - start

start = perf_counter()
items = build_array_at_front(N)
array_build = perf_counter() - start

print(f"building {N} items, adding each at the FRONT")
print(f"  linked list : {linked_build:.4f} seconds")
print(f"  python list : {array_build:.4f} seconds")
print(f"  the list was {array_build / linked_build:.0f} times slower")

middle = N // 2

start = perf_counter()
for _ in range(200):
    got = items[middle]
array_read = perf_counter() - start

start = perf_counter()
for _ in range(200):
    pos = walk(head, items[middle])
linked_read = perf_counter() - start

print()
print(f"reading item {middle}, 200 times over")
print(f"  python list : {array_read:.6f} seconds, by arithmetic")
print(f"  linked list : {linked_read:.6f} seconds, by walking")
print(f"  the walk was {linked_read / array_read:.0f} times slower")
print()
print("and both hold the same thing:", got == items[middle], pos == middle)

building 20000 items, adding each at the FRONT
  linked list : 0.0033 seconds
  python list : 0.1611 seconds
  the list was 49 times slower

reading item 10000, 200 times over
  python list : 0.000026 seconds, by arithmetic
  linked list : 0.118343 seconds, by walking
  the walk was 4508 times slower

and both hold the same thing: True True

Building at the front: the linked list wins by 58 times. Every insert(0, i) on a Python list moves all the items already there up by one, so building n items that way costs about n squared steps. Every Node(i, head) costs two assignments, so the linked list costs about n.

Reading the middle: the Python list wins by 4114 times. items[10000] is one multiplication and one memory read. Walking to node 10000 is ten thousand steps, and the nodes are scattered in memory so nearly every step is a cache miss.

Those two figures together are the honest answer, and it is worth stating as a rule:

Use an array when you will read by position. Use a linked list when you will

insert and remove at a position you are already holding.

And the practical footnote: in Python, almost always use the built-in list. It is implemented in C, its append is very fast, and collections.deque gives cheap insertion and removal at both ends. The linked list is on this syllabus because you cannot understand the built-in list, or a file system's block chain, or an operating system's ready queue, without being able to build one.

The cost of every operation

The table the examination asks for. n is the number of nodes.

Read the "delete a node you hold" row. Even when you are holding the node, a singly linked list cannot delete it in one step, because unlinking needs the node in front. That is the single strongest argument for a doubly linked list, and it is the subject of the next chapter but one.

Procedure

1. Write the class. Compile is not needed; run it with python3 sll.py.
2. Swap the two lines of prepend so the head moves first. Run it and note that the list is now

one node long.

1. Remove the if here is self.tail: self.tail = before line from remove, delete the last item,

and then append something. The new item goes after a node that is no longer in the list.

1. Add a get(position) method that returns the item at a position and raises IndexError past

the end.

1. Write the playlist. Remove the song that is playing and check the pointer moves on.
2. Write the measurement. Run it at N of 5000, 10000 and 20000 and note that the ratio grows with

N, which is what O(n squared) against O(n) means.

1. Turn the playlist into a circular list, so that the last node's nxt is the head, and

delete the wrap-round line from play_next. Be careful: every traversal must now stop on its own or it never ends.

Result

A singly linked list was built with prepend, append, insert after a value, search, contains, remove, length, iteration and reverse, each maintaining the head, the tail and the count. Removal was shown to require a trailing pointer, and reversal to need three pointers and no new nodes. The list was applied to a playlist in which the currently playing song is held as a node reference, so that additions and removals elsewhere do not disturb it. Against a Python list, building 20000 items at the front was 58 times faster with links, and reading the middle item was 4114 times slower.

Where marks are lost

• Using a Python list. The exercise is to build the structure.
• No tail, so append walks the list, and then saying append is O(1).
• Not moving the tail back when the last node is removed.
• Not handling the head as a special case in remove, so removing the first item does nothing

or crashes.

• No trailing pointer in remove, which cannot be made to work in a singly linked list.
• Losing the rest of the list in reverse by overwriting here.nxt before saving it.
• Forgetting here = here.nxt in a traversal, which never ends.
• Returning None for a value that is not found instead of -1 or an exception, and then not

being able to distinguish it from a stored None.

• Saying the linked list is faster, or slower, without saying at what. It is both, and the

marks are in the "at what".

For the journal

Write the aim, MU's own wording, and the picture of three nodes with their links and the trailing None, because that diagram is worth a mark on its own. Then the class in full and its run. Then the playlist with its output, and one sentence on why the playing pointer is a node and not an index. Then the measurement with both figures, your own machine's, and the cost table. The conclusion: a linked list trades position arithmetic for cheap insertion, so it is faster than an array at one end and thousands of times slower in the middle, and which to use is decided by what the program will do most.

Quick revision

• A node holds an item and a link; the last link is None; the list is a reference to the head.
• Keep head, tail and count, and maintain all three in every operation.
• prepend: build the node pointing at the old head, then move the head. Two assignments,

O(1).

• append is O(1) only because a tail is kept. Without one it is O(n).
• remove needs a trailing before pointer, because a node cannot reach its predecessor. Three

cases: it was the head, it was in the middle, it was the tail.

• reverse uses three pointers, before, here and after, and saves after before

overwriting here.nxt.

• __len__, __iter__ with yield, __contains__ and __repr__ make the class behave like a

Python container. Define __contains__ in terms of search so the two cannot disagree.

• A playlist holds the playing song as a node, not an index, so that changes elsewhere do not

move it. Removing the playing song must move the pointer on.

• Measured here: building at the front, links 58 times faster; reading the middle, array 4114

times faster.

• Costs: read O(n) against O(1); insert at the head O(1) against O(n); insert after a node you

hold O(1), which is the linked list's real advantage; delete a node you hold still O(n), which is the argument for a doubly linked list.

Questions you should be able to answer

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

2. Why does append need a tail pointer? Because without one it must walk from the head to the end, which is O(n), so building n items by appending would cost n squared steps. With a tail it is two assignments.

3. Why does remove need a trailing pointer? Because unlinking a node means changing the nxt of the node in front of it, and a singly linked node has no way to reach its predecessor. The trailing pointer is that predecessor.

4. Write the three lines that reverse a singly linked list. Save after = here.nxt, set here.nxt = before, then advance before = here and here = after. When the loop ends, before is the new head. The saving of after must come first.

5. The last node is removed and the tail is not updated. What goes wrong? The tail still points at a node that is no longer in the list, so the next append links the new node on to a detached node and it never appears.

6. Why is a playlist's current song a node reference rather than an index? Because removing or inserting a song elsewhere changes every index after it, and an index would then point at the wrong song. A node reference is unaffected.

7. Which is faster, an array or a linked list? Neither: they are faster at different things. Building 20000 items at the front, the linked list was 58 times faster here; reading the middle item, the Python list was 4114 times faster.

8. Give the one operation a linked list does in constant time that an array cannot. Inserting or deleting at a position you are already holding. An array has to shift everything after it.

9. Even holding the node, why can a singly linked list not delete it in one step? Because the deletion changes the previous node's link, and there is no way back from a node to its predecessor. A doubly linked list can, which is why it exists.