Practical 14: Doubly Linked Lists

The four links of an insertion

Inserting a node between before and after means four assignments, and a program that makes three of them is broken in a way that only a backward traversal reveals:

node.prv = before          # 1. the new node looks back
node.nxt = after           # 2. and forward
before.nxt = node          # 3. the one behind looks at it
after.prv = node           # 4. and the one in front looks back at it

In the program, 1 and 2 are done by the Node constructor and 3 and 4 are the two lines after it. The two special cases are when before is None, so the new node is the head, and when after is None, so it is the tail; in each of those the missing assignment is replaced by moving head or tail.

The printed table of neighbours is the check, and it is worth putting in the journal. Every node's prv must be the node before it and its nxt the node after it. Read the run above: the head's prv is None, the tail's nxt is None, and every pair agrees.

unlink is the operation that justifies the whole structure

def unlink(self, node):
    if node.prv is None: self.head = node.nxt
    else:                node.prv.nxt = node.nxt
    if node.nxt is None: self.tail = node.prv
    else:                node.nxt.prv = node.prv
    node.prv = node.nxt = None

Four branches and no searching. Compare remove in [Practical 12: Singly Linked Lists], which had to walk the list with a trailing pointer to find the predecessor. Here the predecessor is node.prv, so given the node, deletion is a constant number of steps however long the list is.

That single property is why a doubly linked list is the structure under an LRU cache, under a process scheduler's queues, and under Python's own collections.deque. The [Practical 9: Memory Management, FIFO and LRU Page Replacement] chapter said that a real LRU implementation keeps the pages in a list and moves a page to the front when it is used. Moving a node to the front is an unlink and a prepend, and both are O(1) only in a doubly linked list.

node.prv = node.nxt = None at the end is not tidiness. An unlinked node that still points into the list lets a caller who kept a reference to it walk back into a structure it is no longer part of, and the bug that results is very hard to find.

node_at searches from the nearer end

if position <= self.count // 2:
    here = self.head;  step forwards `position` times
else:
    here = self.tail;  step backwards `count - 1 - position` times

A singly linked list must always start at the head, so reaching the last node of a list of 1000 takes 1000 steps. A doubly linked list takes one. It is still O(n) in the worst case, the middle, but the constant is halved, and it costs three lines.

MU's two applications, which are one structure

MU names browser history and undo-redo. They look different and they are the same idea: a doubly linked list with a cursor, where

• going back moves the cursor one step towards the head,
• going forward moves it one step towards the tail,
• and doing something new attaches a node after the cursor and

discards whatever was in front.

That last rule is the one students leave out, and it is what the second program demonstrates twice.

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


class BrowserHistory:
    """A doubly linked list with a pointer to the page you are on.
    Back and forward are one step each, which is the whole point."""

    def __init__(self, first_page):
        self.here = Node(first_page)

    def visit(self, page):
        """Going somewhere new throws away everything in FRONT of you."""
        node = Node(page, self.here, None)
        self.here.nxt = node                    # the old forward chain is dropped
        self.here = node

    def back(self):
        if self.here.prv is None:
            raise IndexError("there is nothing behind this page")
        self.here = self.here.prv
        return self.here.data

    def forward(self):
        if self.here.nxt is None:
            raise IndexError("there is nothing in front of this page")
        self.here = self.here.nxt
        return self.here.data

    def show(self):
        start = self.here
        while start.prv is not None:
            start = start.prv
        parts = []
        node = start
        while node is not None:
            parts.append(f"[{node.data}]" if node is self.here else node.data)
            node = node.nxt
        print("    " + "  <->  ".join(parts))


b = BrowserHistory("munotes.in")
b.visit("munotes.in/notes")
b.visit("munotes.in/notes/BSc-Computer-Science")
b.visit("munotes.in/syllabus")
print("after four pages, the current one in brackets")
b.show()

print()
print("back    ->", b.back())
print("back    ->", b.back())
b.show()
print("forward ->", b.forward())
b.show()

print()
print("now visit somewhere new from the middle")
b.visit("munotes.in/aibe")
b.show()
try:
    b.forward()
except IndexError as e:
    print("forward now: IndexError:", e)

print()
while True:
    try:
        b.back()
    except IndexError as e:
        print("going back to the start, then once more: IndexError:", e)
        break
b.show()


class Editor:
    """Undo and redo over the same idea: one list, one cursor."""

    def __init__(self):
        self.text = ""
        self.done = Node(("start", "", ""))     # a sentinel we never undo past
        self.here = self.done

    def type(self, s):
        before = self.text
        self.text = self.text + s
        self.record(("type", s, before))

    def delete(self, n):
        if n > len(self.text):
            raise ValueError(f"there are only {len(self.text)} characters")
        before = self.text
        self.text = self.text[:-n]
        self.record(("delete", before[-n:], before))

    def record(self, action):
        node = Node(action, self.here, None)
        self.here.nxt = node                    # anything redoable is dropped
        self.here = node

    def undo(self):
        if self.here.prv is None:
            raise IndexError("there is nothing to undo")
        what, part, before = self.here.data
        self.text = before
        self.here = self.here.prv
        return what, part

    def redo(self):
        if self.here.nxt is None:
            raise IndexError("there is nothing to redo")
        self.here = self.here.nxt
        what, part, before = self.here.data
        if what == "type":
            self.text = before + part
        else:
            self.text = before[:-len(part)]
        return what, part


e = Editor()
e.type("Computer ")
e.type("Science ")
e.type("Practical 3")
print()
print("the text:", repr(e.text))

print("undo     ->", e.undo(), "text now", repr(e.text))
print("undo     ->", e.undo(), "text now", repr(e.text))
print("redo     ->", e.redo(), "text now", repr(e.text))

print()
e.type("Module 2")
print("typing after an undo drops the redo chain; text:", repr(e.text))
try:
    e.redo()
except IndexError as ex:
    print("redo now: IndexError:", ex)

print()
e.delete(8)
print("after delete(8):", repr(e.text))
print("undo the delete ->", e.undo(), "text now", repr(e.text))

after four pages, the current one in brackets
    munotes.in  <->  munotes.in/notes  <->  munotes.in/notes/BSc-Computer-Science  <->  [munotes.in/syllabus]

back    -> munotes.in/notes/BSc-Computer-Science
back    -> munotes.in/notes
    munotes.in  <->  [munotes.in/notes]  <->  munotes.in/notes/BSc-Computer-Science  <->  munotes.in/syllabus
forward -> munotes.in/notes/BSc-Computer-Science
    munotes.in  <->  munotes.in/notes  <->  [munotes.in/notes/BSc-Computer-Science]  <->  munotes.in/syllabus

now visit somewhere new from the middle
    munotes.in  <->  munotes.in/notes  <->  munotes.in/notes/BSc-Computer-Science  <->  [munotes.in/aibe]
forward now: IndexError: there is nothing in front of this page

going back to the start, then once more: IndexError: there is nothing behind this page
    [munotes.in]  <->  munotes.in/notes  <->  munotes.in/notes/BSc-Computer-Science  <->  munotes.in/aibe

the text: 'Computer Science Practical 3'
undo     -> ('type', 'Practical 3') text now 'Computer Science '
undo     -> ('type', 'Science ') text now 'Computer '
redo     -> ('type', 'Science ') text now 'Computer Science '

typing after an undo drops the redo chain; text: 'Computer Science Module 2'
redo now: IndexError: there is nothing to redo

after delete(8): 'Computer Science '
undo the delete -> ('delete', 'Module 2') text now 'Computer Science Module 2'

Browser history

Follow the run. Four pages are visited, so the cursor is at the fourth. Two backs move it to the second, and forward moves it to the third; the pages in front are still there, which is why the forward button is not greyed out.

Then visit("munotes.in/aibe") from the middle, and the page that was in front is gone. The list now ends at the new page, and forward raises. That is exactly what a real browser does: go back twice, follow a different link, and the forward button goes grey. A program that appends at the tail instead of after the cursor keeps a forward history the user can never legitimately reach.

The last part goes back to the first page and then once more, and the error says there is nothing behind it. A real browser greys the back button out; a program raises, and the caller decides what to show.

Undo and redo

The same three rules with different words:

And the run shows the fourth row firing: after two undos and one redo, typing Module 2 makes redo raise, because the action that was redoable has been replaced.

Each node records what was done and what the text was before, which is what makes undo possible: ("type", "Practical 3", "Computer Science ") says the action, the part it added, and the text to go back to. Storing the state before is the simplest correct scheme and it is what the program does. The alternative is to store only the action and reverse it, which uses less memory and is harder to get right for an action like "replace all".

The sentinel node. self.done starts as a node holding ("start", "", "") that nothing ever undoes past, so undo needs no special case for the beginning: it raises when self.here.prv is None, and that is only true at the sentinel. A sentinel or dummy node is the standard trick for removing the special cases from a linked structure, and it is worth knowing by name.

The cost of each operation

The three rows in bold are the whole argument for the structure.

Procedure

1. Write the class and run it. Print the list forwards and backwards after every operation.
2. Delete the line after.prv = node from insert_at (it is here.prv = node in the listing).

Run it: the forward traversal is right and the backward one is wrong. That is the bug to recognise.

1. Add a middle() method that returns the item in the middle, using node_at.
2. Write the browser history. Go back twice, visit a new page, and confirm that forward raises.
3. Add an is_back_possible() and is_forward_possible() to it, which is what a real browser

uses to grey the buttons out.

1. Write the editor. Type three things, undo twice, redo once, type something, and confirm the

redo chain is gone.

1. Make the list circular and doubly linked: the head's prv is the tail and the tail's nxt

is the head. Note that unlink then needs no branches at all, and that every traversal must count rather than wait for None.

Result

A doubly linked list was built with forward and backward traversal and with insertion and deletion at the head, the tail and a given position, each maintaining both links in both directions. A node held by the caller was unlinked in a constant number of steps, which a singly linked list cannot do. node_at was made to search from whichever end is nearer. The same structure with a cursor was then used for browser history and for undo and redo, and in both the rule that doing something new discards what was in front of the cursor was demonstrated, with forward and redo raising afterwards.

Where marks are lost

• Fixing one link and not the other. The list then reads correctly forwards and wrongly

backwards, and only a backward traversal finds it.

• Not moving head or tail when the node inserted or removed was at an end.
• Not clearing prv and nxt on an unlinked node, leaving a dangling reference into the

list.

• Appending at the tail in the browser history instead of after the cursor, so a forward

history survives that should have been discarded.

• No error when there is nothing to go back to, so the cursor walks off the end.
• Storing only the action in the editor and not the state before, and then getting the

reversal wrong.

• Claiming a doubly linked list has no disadvantage. It uses one extra reference a node and

every operation has twice as many links to fix.

• Saying deletion is O(1). It is O(1) given the node; finding the node is still O(n).

For the journal

Write the aim, MU's own wording, and the picture of three nodes with both sets of arrows and the two Nones at the ends. Then the class and its run, including the table of every node's prv and nxt, because that table is the proof that both links are maintained. Then the browser history with its run, and circle the point where visiting a new page from the middle discards the pages in front. Then the editor, and the table showing that it is the same three rules with different words. The conclusion: a second link per node buys backward traversal and constant-time deletion of a node you hold, and costs one reference per node and twice the care in every operation.

Quick revision

• Every node has prv and nxt. The head's prv and the tail's nxt are None.
• An insertion means four link assignments, and the two special cases are at the head and the

tail. A program that makes three of them is wrong backwards only.

• unlink(node) is four branches and no searching: O(1) given the node. That is the whole reason

for the structure.

• Clear an unlinked node's links, or it points into a list it has left.
• node_at searches from the nearer end, so the worst case is n over 2 rather than n.
• Browser history and undo-redo are the same structure: a list with a cursor. Back and forward

move it; doing something new attaches after it and discards everything in front.

• A sentinel node at the start removes the special case from undo.
• The editor stores, for each action, what was done and the state before it, which is the simplest

correct undo.

• Costs against a singly linked list: deletion at the tail and deletion of a held node go from

O(n) to O(1), and backward traversal becomes possible. The cost is one reference a node.

• A doubly linked list is what sits under an LRU cache and under collections.deque.

Questions you should be able to answer

1. What does a doubly linked list have that a singly linked list does not? A second link in each node, pointing at the previous node. That allows backward traversal and lets a node the caller is holding be deleted in a constant number of steps.

2. How many link assignments does inserting a node between two others take? Four: the new node's two links, the previous node's nxt and the next node's prv. Missing the last one leaves a list that is right forwards and wrong backwards.

3. Why is deleting the tail O(1) here and O(n) in a singly linked list? Because the tail's predecessor is tail.prv, one step away. A singly linked list has to walk from the head to find it.

4. Is deletion O(1)? Given the node, yes. Finding the node by its value is still O(n); the constant time is in the unlinking, not the searching.

5. What are the disadvantages of a doubly linked list? One extra reference per node, so more memory, and every insertion and deletion has twice as many links to maintain, so more code and more chances to get it wrong.

6. In a browser history, what happens when you go back twice and then follow a new link? The pages that were in front of the cursor are discarded and the new page is attached after the cursor, so the forward button becomes unusable. Appending at the tail instead would leave a forward history the user should not have.

7. Why are browser history and undo-redo the same structure? Both are a doubly linked list with a cursor: back and undo move it one way, forward and redo the other, and a new page or a new action attaches after the cursor and throws away what was in front.

8. What is a sentinel node, and what does it buy here? A dummy node at the start that holds no real data. It means undo needs no special case for the beginning of the history: the sentinel is the node whose prv is None.

9. How can node_at be faster in a doubly linked list? By starting from whichever end is nearer: from the head for the first half and from the tail backwards for the second. The worst case becomes n over 2 instead of n.