Data structures in Python

Linked List Lab

Pick an operation and step through it line by line. The diagram shows exactly which pointer each line of Python changes.

Singly linked: each node knows the next one

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0

The list object only stores head. Everything else is reached by following next until it is None.

Doubly linked: each node knows both neighbours

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

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

Keeping tail and prev costs extra memory, but makes work at both ends O(1).

a pointer (next / prev)changed by the highlighted linefield is Nonelist attribute (head, tail)local variablefaded = nothing references it (garbage)

Tip: the ← and → keys step too.

Cost of each operation

Operation	Python list	Singly linked	Doubly linked
Access by index	O(1)	O(n)	O(n), at most n/2 steps
Insert at front	O(n)	O(1)	O(1)
Insert at end	O(1) amortised	O(n), O(1) with a tail	O(1)
Remove from front	O(n)	O(1)	O(1)
Remove from end	O(1)	O(n)	O(1)
Remove a node you hold	n/a	O(n), needs the node before it	O(1)
Search / find	O(n)	O(n)	O(n)
Extra memory per item	lowest	1 reference	2 references

In everyday Python, collections.deque gives you doubly-linked behaviour at both ends. Writing your own is how you learn the pointer logic.