Skip to content

Singly Linked Lists

1
from typing import Any, Optional

Define a node

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

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

Create a Singly Linked List

1
2
3
4
5
6
7
8
head = Node(1)
a = Node(2)
b = Node(3)
c = Node(4)

head.next = a
a.next = b
b.next = c

Traverse the list - O(n)

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

1, 2, 3, 4,

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, 2, 3, 4]'

Search for a value - O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def includes(head: Node, value: Any) -> bool:
    cursor = head
    while cursor:
        if value == cursor.value:
            return True
        cursor = cursor.next

    return False


includes(head, 2), includes(head, 10)

(True, False)