Repository navigation
Expand file tree
/
Copy pathsingly_linked_list.py
More file actions
105 lines (84 loc) · 3.24 KB
/
Copy pathsingly_linked_list.py
File metadata and controls
105 lines (84 loc) · 3.24 KB
1
2
3
4
5
6
7
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
from src.data_structures.singly_linked_list_node import SinglyLinkedListNode
class SinglyLinkedList[T]:
"""Singly Linked List.
(https://en.wikipedia.org/wiki/Linked_list): Singly linked lists contain nodes which have a data field
as well as 'next' field, which points to the next node in line of nodes. Operations that can be
performed on singly linked lists include insertion, deletion and traversal.
Benefits:
* Dynamic data structure that can expand or shrink as needed
* Requires no extra space (memory efficient)
* Does not require a continuous block of memory like arrays
Drawbacks:
* Operations take O(N) time (Ex: Search)
* Tracking of pointers takes up additional memory
"""
def __init__(self):
self._head: SinglyLinkedListNode[T] = SinglyLinkedListNode[T](None)
def all_values(self) -> list[T]:
"""Return a list of every value in the list, in order from head to tail."""
values = []
node = self._head.next
while node:
if node.data:
values.append(node.data)
node = node.next
return values
# O(N)
def append(self, data: T) -> None:
"""Add a new node containing data to the end of the list."""
node = SinglyLinkedListNode(data)
last_node = self._head
while last_node:
if not last_node.next:
break
last_node = last_node.next
last_node.next = node
# O(N)
def get(self, index: int) -> T | None:
"""Return the data stored at index, or None if the index is out of bounds."""
current_node = self._head.next
count = 0
while current_node:
if count == index:
break
current_node = current_node.next
count += 1
if current_node is None or count != index:
return None
return current_node.data
def insert(self, data: T, index: int) -> None:
"""Insert a new node containing data before the node currently at index."""
node = SinglyLinkedListNode(data)
current_node = self._head
count = 0
while current_node:
if count == index:
next_node = current_node.next
node.next = next_node
current_node.next = node
return
current_node = current_node.next
count += 1
raise IndexError("Index out of bounds")
def remove(self, index: int) -> None:
"""Remove the node at index by linking its predecessor directly to its successor."""
count = 0
current_node = self._head
while current_node:
if count == index:
remove_node = current_node.next
if remove_node and remove_node.next:
current_node.next = remove_node.next
return
current_node.next = None
current_node = current_node.next
count += 1
# O(N)
def size(self) -> int:
"""Return the number of nodes in the list."""
count = 0
current_node = self._head.next
while current_node:
count += 1
current_node = current_node.next
return count