Insertion and Deletion With Two Links

class DNode:
    def __init__(self, data):
        self.prev = None
        self.data = data
        self.next = None


class DList:
    def __init__(self, values=()):
        self.head = self.tail = None
        self.n = 0
        for value in values:
            self.append(value)

    def append(self, value):
        node = DNode(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            node.prev = self.tail
            self.tail.next = node
            self.tail = node
        self.n += 1
        return node

    def insert_after(self, p, value):
        """Insert a new node after p. Four assignments, in a safe order."""
        n = DNode(value)
        s = p.next
        n.prev = p                      # 1. new node's links first
        n.next = s
        p.next = n                      # 3. then redirect the neighbours
        if s is not None:
            s.prev = n
        else:
            self.tail = n
        self.n += 1
        return n

    def insert_before(self, s, value):
        if s.prev is None:
            n = DNode(value)
            n.next = s
            s.prev = n
            self.head = n
            self.n += 1
            return n
        return self.insert_after(s.prev, value)

    def delete(self, x):
        """Delete a node we are holding. Two assignments, no walk."""
        p, s = x.prev, x.next
        if p is not None:
            p.next = s
        else:
            self.head = s
        if s is not None:
            s.prev = p
        else:
            self.tail = p
        x.prev = x.next = None          # so a stale node cannot be walked
        self.n -= 1

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

    def backward(self):
        out, walk = [], self.tail
        while walk is not None:
            out.append(walk.data)
            walk = walk.prev
        return out

    def check(self):
        if self.head is not None and self.head.prev is not None:
            return "BROKEN: head.prev"
        if self.tail is not None and self.tail.next is not None:
            return "BROKEN: tail.next"
        walk, seen = self.head, 0
        while walk is not None:
            seen += 1
            if walk.next is not None and walk.next.prev is not walk:
                return "BROKEN: chains disagree at %r" % (walk.data,)
            walk = walk.next
        if seen != self.n:
            return "BROKEN: counter %d, chain %d" % (self.n, seen)
        return "ok"


lst = DList(["A", "B", "D"])
print("start          :", lst.forward(), lst.backward(), lst.check())

b = lst.head.next
lst.insert_after(b, "C")
print("insert C after B:", lst.forward(), lst.backward(), lst.check())

lst.insert_after(lst.tail, "E")
print("insert E at end :", lst.forward(), lst.backward(), lst.check())

lst.insert_before(lst.head, "Z")
print("insert Z at head:", lst.forward(), lst.backward(), lst.check())

lst.delete(lst.head)
print("delete the head :", lst.forward(), lst.backward(), lst.check())

lst.delete(lst.tail)
print("delete the tail :", lst.forward(), lst.backward(), lst.check())

middle = lst.head.next
lst.delete(middle)
print("delete a middle :", lst.forward(), lst.backward(), lst.check())

only = DList(["solo"])
only.delete(only.head)
print("delete the only :", only.forward(), only.backward(), only.check(),
      "| head", only.head, "tail", only.tail)