Skip to content

Linear Data Structures

These structures store data in a sequential manner.

Singly Linked List

Bases: Generic[T]

A strictly typed, memory-optimized Singly Linked List.

Source code in pure_python_ds/linear/singly_linked_list.py 
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
class SinglyLinkedList(Generic[T]):
    """
    A strictly typed, memory-optimized Singly Linked List.
    """

    def __init__(self) -> None:
        self.head: Optional[ListNode[T]] = None
        self.tail: Optional[ListNode[T]] = None
        self._length: int = 0

    def __str__(self) -> str:
        """
        Provides a visual representation of the Linked List.
        Example: Future -> Systems -> Architect -> None
        """
        # We leverage our own generator to seamlessly loop through the values
        values = [str(node_val) for node_val in self]
        values.append("None")
        return " -> ".join(values)

    def __len__(self) -> int:
        """Allows the user to call len(linked_list) in O(1) time."""
        return self._length

    def append(self, value: T) -> None:
        """Adds a new node to the end of the list in O(1) time."""
        new_node = ListNode(value)
        if not self.head or not self.tail:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
        self._length += 1

    def prepend(self, value: T) -> None:
        """Adds a new node to the beginning of the list in O(1) time."""
        new_node = ListNode(value)
        if not self.head or not self.tail:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head = new_node
        self._length += 1

    def __iter__(self) -> Generator[T, None, None]:
        """
        Generator-based traversal.
        Allows users to run: `for val in linked_list:` with O(1) memory overhead.
        """
        current = self.head
        while current:
            yield current.value
            current = current.next

    def remove_head(self) -> Optional[T]:
        """Removes and returns the first node's value in O(1) time."""
        if not self.head:
            return None

        value = self.head.value
        self.head = self.head.next
        self._length -= 1

        if self._length == 0:
            self.tail = None

        return value

    def reverse(self) -> None:
        """Reverses the list in O(n) time and O(1) space."""
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

    def search(self, value: T) -> bool:
        """Returns True if value exists in the list, else False."""
        current = self.head
        while current:
            if current.value == value:
                return True
            current = current.next
        return False

    def remove(self, value: T) -> bool:
        """Removes the first occurrence of value from the list."""
        if not self.head:
            return False

        if self.head.value == value:
            self.head = self.head.next
            return True

        current = self.head
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                return True
            current = current.next
        return False

__iter__()

Generator-based traversal. Allows users to run: for val in linked_list: with O(1) memory overhead.

Source code in pure_python_ds/linear/singly_linked_list.py 
55
56
57
58
59
60
61
62
63
def __iter__(self) -> Generator[T, None, None]:
    """
    Generator-based traversal.
    Allows users to run: `for val in linked_list:` with O(1) memory overhead.
    """
    current = self.head
    while current:
        yield current.value
        current = current.next

__len__()

Allows the user to call len(linked_list) in O(1) time.

Source code in pure_python_ds/linear/singly_linked_list.py 
29
30
31
def __len__(self) -> int:
    """Allows the user to call len(linked_list) in O(1) time."""
    return self._length

__str__()

Provides a visual representation of the Linked List. Example: Future -> Systems -> Architect -> None

Source code in pure_python_ds/linear/singly_linked_list.py 
19
20
21
22
23
24
25
26
27
def __str__(self) -> str:
    """
    Provides a visual representation of the Linked List.
    Example: Future -> Systems -> Architect -> None
    """
    # We leverage our own generator to seamlessly loop through the values
    values = [str(node_val) for node_val in self]
    values.append("None")
    return " -> ".join(values)

append(value)

Adds a new node to the end of the list in O(1) time.

Source code in pure_python_ds/linear/singly_linked_list.py 
33
34
35
36
37
38
39
40
41
42
def append(self, value: T) -> None:
    """Adds a new node to the end of the list in O(1) time."""
    new_node = ListNode(value)
    if not self.head or not self.tail:
        self.head = new_node
        self.tail = new_node
    else:
        self.tail.next = new_node
        self.tail = new_node
    self._length += 1

prepend(value)

Adds a new node to the beginning of the list in O(1) time.

Source code in pure_python_ds/linear/singly_linked_list.py 
44
45
46
47
48
49
50
51
52
53
def prepend(self, value: T) -> None:
    """Adds a new node to the beginning of the list in O(1) time."""
    new_node = ListNode(value)
    if not self.head or not self.tail:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head = new_node
    self._length += 1

remove(value)

Removes the first occurrence of value from the list.

Source code in pure_python_ds/linear/singly_linked_list.py 
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
def remove(self, value: T) -> bool:
    """Removes the first occurrence of value from the list."""
    if not self.head:
        return False

    if self.head.value == value:
        self.head = self.head.next
        return True

    current = self.head
    while current.next:
        if current.next.value == value:
            current.next = current.next.next
            return True
        current = current.next
    return False

remove_head()

Removes and returns the first node's value in O(1) time.

Source code in pure_python_ds/linear/singly_linked_list.py 
65
66
67
68
69
70
71
72
73
74
75
76
77
def remove_head(self) -> Optional[T]:
    """Removes and returns the first node's value in O(1) time."""
    if not self.head:
        return None

    value = self.head.value
    self.head = self.head.next
    self._length -= 1

    if self._length == 0:
        self.tail = None

    return value

reverse()

Reverses the list in O(n) time and O(1) space.

Source code in pure_python_ds/linear/singly_linked_list.py 
79
80
81
82
83
84
85
86
87
88
def reverse(self) -> None:
    """Reverses the list in O(n) time and O(1) space."""
    prev = None
    current = self.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    self.head = prev

search(value)

Returns True if value exists in the list, else False.

Source code in pure_python_ds/linear/singly_linked_list.py 
90
91
92
93
94
95
96
97
def search(self, value: T) -> bool:
    """Returns True if value exists in the list, else False."""
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Doubly Linked List

Bases: Generic[T]

A strictly typed, memory-optimized Doubly Linked List.

Source code in pure_python_ds/linear/doubly_linked_list.py 
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
class DoublyLinkedList(Generic[T]):
    """A strictly typed, memory-optimized Doubly Linked List."""

    def __init__(self) -> None:
        self.head: Optional[ListNode[T]] = None
        self.tail: Optional[ListNode[T]] = None
        self._length: int = 0

    def __len__(self) -> int:
        return self._length

    def is_empty(self) -> bool:
        return self._length == 0

    def append(self, value: T) -> None:
        """Adds a node to the end in O(1) time."""
        new_node = ListNode(value)
        if not self.head or not self.tail:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
        self._length += 1

    def prepend(self, value: T) -> None:
        """Adds a node to the beginning in O(1) time."""
        new_node = ListNode(value)
        if not self.head or not self.tail:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self._length += 1

    def remove_head(self) -> Optional[T]:
        """Removes the first node in O(1) time."""
        if not self.head:
            return None

        value = self.head.value
        if self.head is self.tail:  # Only one element
            self.head = None
            self.tail = None
        else:
            self.head = self.head.next
            if self.head:
                self.head.prev = None

        self._length -= 1
        return value

    def remove_tail(self) -> Optional[T]:
        """Removes the last node in O(1) time (Impossible in Singly Linked Lists!)."""
        if not self.tail:
            return None

        value = self.tail.value
        if self.head is self.tail:  # Only one element
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.prev
            if self.tail:
                self.tail.next = None  # Sever the tie

        self._length -= 1
        return value

    def __iter__(self) -> Generator[T, None, None]:
        """Forward generator traversal."""
        current = self.head
        while current:
            yield current.value
            current = current.next

    def __str__(self) -> str:
        """Visual representation showing bidirectional pointers."""
        values = [str(val) for val in self]
        return (
            "None <- " + " <-> ".join(values) + " -> None" if values else "Empty List"
        )

    def remove(self, value: T) -> bool:
        """Removes the first occurrence of value from the list."""
        current = self.head
        while current:
            if current.value == value:
                # If it's the head
                if current == self.head:
                    self.head = current.next
                    if self.head:
                        self.head.prev = None
                    else:
                        self.tail = None
                # If it's the tail
                elif current == self.tail:
                    self.tail = current.prev
                    if self.tail:
                        self.tail.next = None
                # If it's in the middle
                else:
                    if current.prev:
                        current.prev.next = current.next
                    if current.next:
                        current.next.prev = current.prev
                return True
            current = current.next
        return False

__iter__()

Forward generator traversal.

Source code in pure_python_ds/linear/doubly_linked_list.py 
80
81
82
83
84
85
def __iter__(self) -> Generator[T, None, None]:
    """Forward generator traversal."""
    current = self.head
    while current:
        yield current.value
        current = current.next

__str__()

Visual representation showing bidirectional pointers.

Source code in pure_python_ds/linear/doubly_linked_list.py 
87
88
89
90
91
92
def __str__(self) -> str:
    """Visual representation showing bidirectional pointers."""
    values = [str(val) for val in self]
    return (
        "None <- " + " <-> ".join(values) + " -> None" if values else "Empty List"
    )

append(value)

Adds a node to the end in O(1) time.

Source code in pure_python_ds/linear/doubly_linked_list.py 
22
23
24
25
26
27
28
29
30
31
32
def append(self, value: T) -> None:
    """Adds a node to the end in O(1) time."""
    new_node = ListNode(value)
    if not self.head or not self.tail:
        self.head = new_node
        self.tail = new_node
    else:
        self.tail.next = new_node
        new_node.prev = self.tail
        self.tail = new_node
    self._length += 1

prepend(value)

Adds a node to the beginning in O(1) time.

Source code in pure_python_ds/linear/doubly_linked_list.py 
34
35
36
37
38
39
40
41
42
43
44
def prepend(self, value: T) -> None:
    """Adds a node to the beginning in O(1) time."""
    new_node = ListNode(value)
    if not self.head or not self.tail:
        self.head = new_node
        self.tail = new_node
    else:
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node
    self._length += 1

remove(value)

Removes the first occurrence of value from the list.

Source code in pure_python_ds/linear/doubly_linked_list.py 
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
def remove(self, value: T) -> bool:
    """Removes the first occurrence of value from the list."""
    current = self.head
    while current:
        if current.value == value:
            # If it's the head
            if current == self.head:
                self.head = current.next
                if self.head:
                    self.head.prev = None
                else:
                    self.tail = None
            # If it's the tail
            elif current == self.tail:
                self.tail = current.prev
                if self.tail:
                    self.tail.next = None
            # If it's in the middle
            else:
                if current.prev:
                    current.prev.next = current.next
                if current.next:
                    current.next.prev = current.prev
            return True
        current = current.next
    return False

remove_head()

Removes the first node in O(1) time.

Source code in pure_python_ds/linear/doubly_linked_list.py 
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def remove_head(self) -> Optional[T]:
    """Removes the first node in O(1) time."""
    if not self.head:
        return None

    value = self.head.value
    if self.head is self.tail:  # Only one element
        self.head = None
        self.tail = None
    else:
        self.head = self.head.next
        if self.head:
            self.head.prev = None

    self._length -= 1
    return value

remove_tail()

Removes the last node in O(1) time (Impossible in Singly Linked Lists!).

Source code in pure_python_ds/linear/doubly_linked_list.py 
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
def remove_tail(self) -> Optional[T]:
    """Removes the last node in O(1) time (Impossible in Singly Linked Lists!)."""
    if not self.tail:
        return None

    value = self.tail.value
    if self.head is self.tail:  # Only one element
        self.head = None
        self.tail = None
    else:
        self.tail = self.tail.prev
        if self.tail:
            self.tail.next = None  # Sever the tie

    self._length -= 1
    return value

Stack

Bases: Generic[T]

A strictly typed, memory-optimized Stack (LIFO).

Source code in pure_python_ds/linear/stack.py 
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Stack(Generic[T]):
    """A strictly typed, memory-optimized Stack (LIFO)."""

    def __init__(self):
        self._container = SinglyLinkedList[T]()

    def __len__(self) -> int:
        return len(self._container)

    def push(self, value: T) -> None:
        """Pushes an item onto the top of the stack in O(1) time."""
        self._container.prepend(value)

    def pop(self) -> Optional[T]:
        """Removes and returns the top item in O(1) time."""
        return self._container.remove_head()

    def __str__(self) -> str:
        return f"Stack Top -> {self._container}"

    def peek(self) -> Optional[T]:
        if not self._container.head:
            return None
        return self._container.head.value

pop()

Removes and returns the top item in O(1) time.

Source code in pure_python_ds/linear/stack.py 
21
22
23
def pop(self) -> Optional[T]:
    """Removes and returns the top item in O(1) time."""
    return self._container.remove_head()

push(value)

Pushes an item onto the top of the stack in O(1) time.

Source code in pure_python_ds/linear/stack.py 
17
18
19
def push(self, value: T) -> None:
    """Pushes an item onto the top of the stack in O(1) time."""
    self._container.prepend(value)

Queue

Bases: Generic[T]

A strictly typed, memory-optimized Queue (FIFO).

Source code in pure_python_ds/linear/queue.py 
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Queue(Generic[T]):
    """A strictly typed, memory-optimized Queue (FIFO)."""

    def __init__(self):
        self._container = SinglyLinkedList[T]()

    def __len__(self) -> int:
        return len(self._container)

    def enqueue(self, value: T) -> None:
        """Adds an item to the back of the queue in O(1) time."""
        self._container.append(value)

    def dequeue(self) -> Optional[T]:
        """Removes and returns the front item in O(1) time."""
        return self._container.remove_head()

    def __str__(self) -> str:
        return f"Queue Front -> {self._container}"

dequeue()

Removes and returns the front item in O(1) time.

Source code in pure_python_ds/linear/queue.py 
21
22
23
def dequeue(self) -> Optional[T]:
    """Removes and returns the front item in O(1) time."""
    return self._container.remove_head()

enqueue(value)

Adds an item to the back of the queue in O(1) time.

Source code in pure_python_ds/linear/queue.py 
17
18
19
def enqueue(self, value: T) -> None:
    """Adds an item to the back of the queue in O(1) time."""
    self._container.append(value)

Min / Max Heap

Bases: Generic[T]

Source code in pure_python_ds/linear/heap.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class MinHeap(Generic[T]):
    def __init__(self):
        self.heap: List[T] = []

    def push(self, val: T) -> None:
        self.heap.append(val)
        self._bubble_up(len(self.heap) - 1)

    def pop(self) -> Optional[T]:
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        root = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._bubble_down(0)
        return root

    def _bubble_up(self, index: int):
        parent = (index - 1) // 2
        # Min-Heap check: Child < Parent
        if index > 0 and self.heap[index] < self.heap[parent]:
            self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
            self._bubble_up(parent)

    def _bubble_down(self, index: int):
        smallest = index
        left, right = 2 * index + 1, 2 * index + 2

        for child in [left, right]:
            if child < len(self.heap) and self.heap[child] < self.heap[smallest]:
                smallest = child

        if smallest != index:
            self.heap[index], self.heap[smallest] = (
                self.heap[smallest],
                self.heap[index],
            )
            self._bubble_down(smallest)

    @property
    def size(self) -> int:
        return len(self.heap)

    @classmethod
    def heapify(cls, data: List[T]) -> "MinHeap[T]":
        """Transforms an unsorted list into a MinHeap in O(n) time."""
        instance = cls()
        instance.heap = list(data)
        for i in range(len(instance.heap) // 2 - 1, -1, -1):
            instance._bubble_down(i)
        return instance

heapify(data) classmethod

Transforms an unsorted list into a MinHeap in O(n) time.

Source code in pure_python_ds/linear/heap.py 
55
56
57
58
59
60
61
62
@classmethod
def heapify(cls, data: List[T]) -> "MinHeap[T]":
    """Transforms an unsorted list into a MinHeap in O(n) time."""
    instance = cls()
    instance.heap = list(data)
    for i in range(len(instance.heap) // 2 - 1, -1, -1):
        instance._bubble_down(i)
    return instance