Linked List

from __future__ import annotations

from dataclasses import dataclass
from typing import Generic, TypeVar

T = TypeVar("T")

Node Object

We create the Node object below.

@dataclass(frozen=False, init=True)
class Node(Generic[T]):
    curr_node_value: T
    next_node: Node = None

One thing for me to visualize is the Node object is not just a single object.

If the Node object holds a single node, then our node object should hold a curr_node_value and the next_node attribute should point to None.

If the Node object holds more than one node, then we can imagine the whole Node object as a series of nodes. We can only access the nodes sequentially, starting from the first node.

Node object with 1 node and 2 nodes, respectively.

Create a Node object with a single value 1.

node = Node(1)
print(node.curr_node_value)
print(node.next_node)

1
None

Assign another value to the next node of the Node object, now this Node has 2 values.

node.next_node = Node(2)
print(node.next_node.curr_node_value)
print(node.next_node.next_node)

2
None

Singly Linked List

Base Class

The head node (the first node) of a Linked List is of a Node object.

The head entirely determines the entirety of the whole Linked List. Why?

Because knowing the head node of the Linked List, we will be able to know every single node that comes after it sequentially (if exists).

class SinglyLinkedList:
    head: Node

    def __init__(self) -> None:
        self.head = None
        
    def is_empty(self) -> bool:
        return self.head is None

Let us walk through how to add items to a Linked List.

1. Start with an empty linked list object. The head of the linked list is None.

# 1
llist = SinglyLinkedList()

2. We create 3 individual Node objects as of now, these 3 node object holds value of 1, 2 and 3 respectively. They are not linked, which can be verified by printing .next which returns None.

# 2
first_node= Node(1)
second_node = Node(2)
third_node = Node(3)

3. Now we assign the first node object first_node = Node(1) to the head attribute of the llist object. We further note that both first_node and llist.head now point to the same object and both are of type Node and each of them holds a value of \(1\). We also have to be clear that we did not link the head (first) node to the next (second) node yet.

   \[ \textbf{first_node} \to \textbf{None} \]

# 3
llist.head = first_node

print(llist.head)

assert id(llist.head) == id(first_node)
assert isinstance(llist.head, Node) == isinstance(first_node, Node)
assert llist.head.curr_node_value == first_node.curr_node_value == 1

Node(curr_node_value=1, next_node=None)

4. We now link the first node with the second by populating the next_node attribute of the head of the linked list llist (i.e. llist.head.next_node = second_node).

   We further note that both llist.head.next_node and second_node now point to the same object and both are of type Node and each of them holds a curr_node_value of \(2\).

   Now the linked list llist has connected the first node and the second node in a linear fashion:

   \[ \textbf{first_node} \to \textbf{second_node} \to \textbf{None} \]

   So to reiterate, our linked list llist at this stage is akin to a list [1, 2]. To access the first value of the linked list we can do llist.head.curr_node_value and to get the next value we can call llist.head.next_node.curr_node_value.

# 4
llist.head.next_node = second_node; # Link first node with second

print(llist.head)

assert id(llist.head.next_node) == id(second_node)
assert isinstance(llist.head.next_node, Node) == isinstance(second_node, Node)
assert llist.head.next_node.curr_node_value == second_node.curr_node_value == 2

Node(curr_node_value=1, next_node=Node(curr_node_value=2, next_node=None))

5. We now link the second node with the third by populating the next_node attribute of the second node of the linked list llist, but to do so, we must actually reach the second node. (i.e. llist.head.next_node.next_node = third_node).

   We further note that both llist.head.next_node.next_node and third_node now point to the same object and both are of type Node and each of them holds a curr_node_value of \(3\).

   Now the linked list llist has connected the second node and the third node in a linear fashion:

   \[ \textbf{first_node} \to \textbf{second_node} \to \textbf{third_node} \to \textbf{None} \]

   So to reiterate, our linked list llist at this stage is akin to a list [1, 2, 3]. To access the first value of the linked list we can do llist.head.curr_node_value and to get the next value we can call llist.head.next_node.curr_node_value and to get the third value, llist.head.next_node.next_node.value. There should be no confusion why we can chain attribute next_node here, since llist.head.next_node and llist.head.next_node.next_node are two different Node objects, so there won’t be any overwriting of the next_node attribute.

# 5
llist.head.next_node.next_node = third_node; # Link second node with the third node

print(llist.head)

assert id(llist.head.next_node.next_node) == id(third_node)
assert isinstance(llist.head.next_node.next_node, Node) == isinstance(third_node, Node)
assert llist.head.next_node.next_node.curr_node_value == third_node.curr_node_value == 3

Node(curr_node_value=1, next_node=Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=None)))

Append using Head and Temp Node Pointers

Adding 3 nodes seems already quite tedious, we basically have to call next_node twice on top of the head to get a linked list of 1 -> 2 -> 3 -> None.

first = Node(1)
second = Node(2)
third = Node(3)
ll = SinglyLinkedList()
ll.head = first
ll.head.next_node = second
ll.head.next_node.next_node = third

print(ll.head)

Node(curr_node_value=1, next_node=Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=None)))

Confusion of Temp Pointer

We show how we can use a temp node that initially points to head, and how after traversing, the head will get updated with the desired node.

Let’s define a linked list with 1 -> 2 -> None and we add 3 to it.

first = Node(1)
second = Node(2)
third = Node(3)

ll = SinglyLinkedList()
ll.head = first
ll.head.next_node = second

temp_node = ll.head  # ll.head and temp has 1 -> 2 -> None

# if we want to add 3, we can do
# ll.head.next_node.next_node = third
# or we can do it on temp.

temp_node = temp_node.next_node  # temp_node is now 2 -> None and is ll.head.next_node
temp_node.next_node = third  # this is equivalent to ll.head.next_node.next_node = third
assert temp_node.next_node == ll.head.next_node.next_node # so this is equals to ll.head.next_node.next_node = third
# print(id(ll.head), id(temp_node), id(ll.head.next_node)) will indicate that they are the same.

# Note we just traverse once since our end goal is for temp_node to be the last node.

print(f"head          :    {ll.head}, \ntemp_node     :    {temp_node}")
print(id(ll.head), id(temp_node), id(ll.head.next_node))

head          :    Node(curr_node_value=1, next_node=Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=None))), 
temp_node     :    Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=None))
140402083722576 140402083722832 140402083722832

Let’s define a linked list with 1 -> 2 -> 3 -> None and we add 4 to it.

first = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)

ll = SinglyLinkedList()
ll.head = first
ll.head.next_node = second
ll.head.next_node.next_node = third

temp_node = ll.head # temp has 1 -> 2 -> 3 -> None

# add 4, we just traverse twice to reach the end

temp_node = temp_node.next_node # ll.head.next_node
temp_node = temp_node.next_node # ll.head.next_node.next_node
print(temp_node)

temp_node.next_node = fourth # ll.head.next_node.next_node.next_node = fourth!

print(f"head          :    {ll.head}, \ntemp_node     :    {temp_node}")
print(id(ll.head), id(temp_node), id(ll.head.next_node.next_node))

Node(curr_node_value=3, next_node=None)
head          :    Node(curr_node_value=1, next_node=Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=Node(curr_node_value=4, next_node=None)))), 
temp_node     :    Node(curr_node_value=3, next_node=Node(curr_node_value=4, next_node=None))
140402081511328 140402083129712 140402083129712

Note we traversed twice now since we need to two steps for temp_node to reach Node(curr_node_value=3, next_node=None).

One important thing to realize is that assigning attribute to temp_node will change head too.

You also need the temporary temp because if you just use head directly, then the head will be forever lost.

first = Node(1)
second = Node(2)
third = Node(3)

ll = SinglyLinkedList()
ll.head = first
ll.head.next_node = second

# if we want to add 3, we can do
# ll.head.next_node.next_node = third
# or we can do it on temp.

ll.head = ll.head.next_node  # temp_node is now 2 -> None and is ll.head.next_node
ll.head.next_node = third  # this is equivalent to ll.head.next_node.next_node = third

# Note we just traverse once since our end goal is for temp_node to be the last node.

print(f"head          :    {ll.head}")

head          :    Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=None))

Append

We first write an append method, which adds individual nodes to a linked list’s head, eventually, we can create another method called add_multiple_nodes which can call append multiple times.

We package our logic above into an append method below.

The key here is we keep track a temp_node that points to head, and traverse temp_node all the way to the last node.

Lastly, we assign temp_node.next_node = new_node so that our head is updated.

class SinglyLinkedList:
    head: Node

    def __init__(self) -> None:
        self.head = None
        
    def append(self, node_value: T) -> None:
        new_node = Node(node_value)
        
        if self.is_empty():
            self.head = new_node
            return

        # the head defines the whole linked list 1->2->3->None
        temp_node = self.head  # temp_node is now pointing to the first node Node(1)
        while temp_node.next_node is not None:
            print(temp_node)
            temp_node = temp_node.next_node
            print(temp_node)

        temp_node.next_node = new_node
        
    def is_empty(self) -> bool:
        return self.head is None

first = Node(1)
second = 2
third = 3
fourth  = 4

ll = SinglyLinkedList()
ll.head = first
ll.append(second)
ll.append(third)
ll.append(fourth)

print(ll.head)

Node(curr_node_value=1, next_node=Node(curr_node_value=2, next_node=None))
Node(curr_node_value=2, next_node=None)
Node(curr_node_value=1, next_node=Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=None)))
Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=None))
Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=None))
Node(curr_node_value=3, next_node=None)
Node(curr_node_value=1, next_node=Node(curr_node_value=2, next_node=Node(curr_node_value=3, next_node=Node(curr_node_value=4, next_node=None))))

Traversing a Linked List

A Wrong Attempt

We first show a wrong attempt. The logic in traverse is as follows:

1. We want to terminate the printing when we reach the last node, that is to say, when the last node is reached, the .next_node attribute should return None.

2. We start off with the head node self.head and print self.head.curr_node_value in the first while loop to get the first node value.

3. Subsequently, we overwrite self.head to be self.head.next_node after printing, so when the next while loop happens, printing self.head.curr_node_value actually points to self.head.next_node.curr_node_value. The logic continues until we reach the last node.

class LinkedList:
    """
    The LinkedList object is initialized with a head node.

    The `head` node (the first node) of a **Linked List** is of a `Node` object.
    The `head` **entirely determines** the entirety of the whole **Linked List**.
    Because knowing the head node of the **Linked List**, we will be able to know every single node that comes after it sequentially (if exists).

    Attributes:
        head (Node): The head node of the linked list.
    """

    head: Node = None

    def __init__(self) -> None:
        self.head = None

    def traverse(self) -> None:
        """Traverse the linked list and print the values of each node.

        Examples:
            >>> first = Node(1)
            >>> second = Node(2)
            >>> third = Node(3)
            >>> ll = LinkedList()
            >>> ll.head = first
            >>> ll.head.next_node = second
            >>> ll.head.next_node.next_node = third
            >>> ll.traverse(ll.head)
        """
        
        while self.head is not None:
            print(self.head.curr_node_value)
            self.head = self.head.next_node
            
            if self.head is None:
                print("None")

>>> first = Node(1)
>>> second = Node(2)
>>> third = Node(3)
>>> ll = LinkedList()
>>> ll.head = first
>>> ll.head.next_node = second
>>> ll.head.next_node.next_node = third
>>> ll.traverse()

1
2
3
None

The code above works fine, but is not ideal since if we want to access llist.head.curr_node_value after calling llist.traverse(), there will be AttributeError: 'NoneType' object has no attribute 'value' since we already set self.head to None in our last loop. Thus, we should change the code a bit where we assign a temp variable to self.head.

temp_node = self.head
while temp_node is not None:
    print(temp_node.curr_node_value)
    temp_node = temp_node.next_node

    if temp_node is None:
        print("None")

isinstance(ll.head, type(None))
# print(ll.head.curr_node_value)

True

Static Method

Since I am just starting out on this topic, I want to keep the traverse method as a standalone function. This is easier for me to debug.

class LinkedList:
    """
    The LinkedList object is initialized with a head node.

    The `head` node (the first node) of a **Linked List** is of a `Node` object.
    The `head` **entirely determines** the entirety of the whole **Linked List**.
    Because knowing the head node of the **Linked List**, we will be able to know every single node that comes after it sequentially (if exists).

    Attributes:
        head (Node): The head node of the linked list.
    """

    head: Node = None

    def __init__(self) -> None:
        self.head = None

    @staticmethod
    def traverse(head_node: Node) -> None:
        """Traverse the linked list and print the values of each node.

        Args:
            head_node (Node): The head node of a linked list.

        Examples:
            >>> first = Node(1)
            >>> second = Node(2)
            >>> third = Node(3)
            >>> ll = LinkedList()
            >>> ll.head = first
            >>> ll.head.next_node = second
            >>> ll.head.next_node.next_node = third
            >>> ll.traverse(ll.head)
        """

        temp_node = head_node

        while temp_node is not None:
            print(temp_node.curr_node_value)
            temp_node = temp_node.next_node
            if temp_node is None:
                print("None")

>>> first = Node(1)
>>> second = Node(2)
>>> third = Node(3)
>>> ll = LinkedList()
>>> ll.head = first
>>> ll.head.next_node = second
>>> ll.head.next_node.next_node = third
>>> ll.traverse(ll.head)

1
2
3
None

Further Readings

• Linked List | Set 1 (Introduction) (GeeksforGeeks)

• Amazon Coding Interview Question: Reverse a Linked List (Leetcode 206 in Python)

• How to Implement a Linked List in Python

• https://towardsdatascience.com/a-complete-guide-to-linked-lists-in-python-c52b6cb005

• https://runestone.academy/ns/books/published/pythonds3/BasicDS/ImplementinganUnorderedListLinkedLists.html

• https://realpython.com/linked-lists-python/

• https://codereview.stackexchange.com/questions/256319/singly-linked-list-python-code/