Skip to content

Doubly Linked Lists

1
from typing import Any, Optional, Tuple

Define a node

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Node:
    def __init__(
        self,
        value: Any,
        next: Optional["Node"] = None,
        previous: Optional["Node"] = None,
    ) -> None:
        self.value = value
        self.next = next
        self.previous = previous

    def __str__(self) -> str:
        return str(self.value)

Create a Doubly Linked List

1
head = tail = Node(1)

Traverse the list - O(n)

1
2
3
4
cursor = head
while cursor:
    print(cursor, end=", ")
    cursor = cursor.next

1,

Display the linked list - O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def representation(head: Node) -> str:
    if head is None:
        return "[]"
    else:
        last = head
        return_string = f"[{last.value}"

        while last.next:
            last = last.next
            return_string += f", {last.value}"
        return_string += "]"

        return return_string


representation(head)

'[1]'

Prepend (insert at the beginning) - O(1)

1
2
3
4
5
6
7
8
def prepend(head: Node, tail: Node, value: Any) -> Tuple[Node, Node]:
    new_node = Node(value, next=head)
    head.previous = new_node
    return new_node, tail


head, tail = prepend(head, tail, 2)
representation(head)

'[2, 1]'

Append (insert at the end) - O(1)

1
2
3
4
5
6
7
8
def append(head: Node, tail: Node, value: Any) -> Tuple[Node, Node]:
    new_node = Node(value, previous=tail)
    tail.next = new_node
    return head, new_node


head, tail = append(head, tail, 10)
representation(head)

'[2, 1, 10]'