Designing a Flexible (Linked) List in Python

Start here Now we build our own linked list with a Python class called Node. We write four operations: check if empty, append at the end, insert at the start, and delete a value. Each one has a small trick — especially insert, because we are not allowed to change where the head points.

The Node class #

A list is a chain of nodes. Each node stores a value and a link to the next node.

class Node:
    def __init__(self, v = None):
        self.value = v        # the stored value
        self.next = None      # link to the next node (None = no next node)
        return

    def isempty(self):
        if self.value == None:
            return True
        else:
            return False

How we represent lists:

Design choice: an empty list is not None — it is a node whose value is None. That way, every list (even an empty one) is a Node object, and we can always call methods on it.

Append — add v at the end #

Idea:

1. If the list is empty, just put v into the head node's value.
2. Otherwise, walk to the last node (the one whose next is None).
3. Make its next point to a new node holding v.

    def appendi(self, v):        # append, iterative
        if self.isempty():
            self.value = v
            return
        temp = self
        while temp.next != None:  # walk to the last node
            temp = temp.next
        temp.next = Node(v)       # attach the new node
        return

Trace: start with l = Node().

Append takes O(n) time here, because we walk to the end each time. (A recursive version works the same way: if this is the last node, attach; otherwise ask self.next to append.)

Insert — add v at the start (the tricky one) #

We want v to become the first value. The obvious idea — make a new node and point the head to it — doesn't work, because the variable l outside the method still points to the old head node. We cannot change where the head points.

The trick: keep the head node where it is, but swap the values:

1. Create a new node holding v.
2. Exchange the values of the head node and the new node. Now the head holds v, and the new node holds the old first value v₀.
3. Re-link: new node points to what the head pointed to; head points to the new node.

    def insert(self, v):
        if self.isempty():
            self.value = v
            return
        newnode = Node(v)
        # Exchange values in self and newnode
        (self.value, newnode.value) = (newnode.value, self.value)
        # Switch links
        (self.next, newnode.next) = (newnode, self.next)
        return

Trace: l is 1 → 2 → 3. Call l.insert(0).

The head node is the same object as before (so l still works), but now it holds 0. Insert at the start takes O(1) time.

Delete — remove the first occurrence of v #

Idea: scan the list and look one step ahead. If the next node holds v, bypass it: point the current node's next to the node after it.

Problem: we can't bypass the first node (the head can't move). Fix: copy the second node's value into the head, then bypass the second node.

    def delete(self, v):          # delete, recursive
        if self.isempty():
            return
        if self.value == v:
            self.value = None
            if self.next != None:
                self.value = self.next.value   # copy the 2nd value into the head
                self.next = self.next.next     # bypass the 2nd node
            return
        else:
            if self.next != None:
                self.next.delete(v)            # delete from the rest of the list
                if self.next.value == None:    # the next node became empty
                    self.next = None           #   → cut it off
            return

Traces (all checked by running the code) #

(Exercise from the lecture: write an iterative version of delete.)

Summary of operations #

In one line: A linked list is a chain of Node objects; append walks to the end, insert swaps values so the head stays put, and delete looks one step ahead to bypass the node.

Exam words: Node, value, next, empty list (value None), singleton, appendi, insert at head, swap values, switch links, delete first occurrence, look ahead, bypass.

Quick check #