-
Notifications
You must be signed in to change notification settings - Fork 16
/
linked_list.py
151 lines (123 loc) · 3.61 KB
/
linked_list.py
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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
class Node:
"""Node to store data"""
def __init__(self, data=None, next_node=None):
"""create a Node datatype
Args:
data ([type], optional): data to store. Defaults to None.
next_node ([type], optional): pointer to next Node. Defaults to None.
Example:
>>> node = Node("data", None)
>>> node.data
'data'
>>> print(node.next_node)
None
"""
self.data = data
self.next_node = next_node
class LinkedList:
"""Linked list to store data as list of nodes"""
def __init__(self):
"""Linked list
Example:
>>> ll = LinkedList()
>>> print(ll.head)
None
>>> print(ll.last_node)
None
"""
self.head = None
self.last_node = None
def print_ll(self):
"""Print entire linked list
Example:
>>> ll = LinkedList()
>>> ll.print_ll()
None
<BLANKLINE>
"""
ll_string = ""
node = self.head
if node is None:
print(None)
while node:
ll_string += f" {str(node.data)} ->"
if node.next_node is None:
ll_string += " None"
node = node.next_node
print(ll_string)
def insert_beginning(self, data):
"""Insert node at beginning of the linked list
Args:
data ([type]): data to store in node
Returns:
bool: [description]
Example:
>>> ll = LinkedList()
>>> ll.insert_beginning("Data 1")
True
>>> ll.insert_beginning("Data 2")
True
>>> ll.head.data
'Data 2'
"""
if self.head is None:
self.head = Node(data, None)
self.last_node = self.head
new_node = Node(data, self.head)
self.head = new_node
return True
def insert_at_end(self, data):
"""Insert node at the end of the linked list
Args:
data ([type]): data to store in node
Returns:
bool: [description]
Example:
>>> ll = LinkedList()
>>> ll.insert_at_end("Data 1")
True
>>> ll.insert_at_end("Data 2")
True
>>> ll.head.data
'Data 1'
>>> ll.last_node.data
'Data 2'
"""
if self.head is None:
self.insert_beginning(data)
if self.last_node is None:
node = self.head
while node.next_node:
node = node.next_node
node.next_node = Node(data, None)
self.last_node = node.next_node
else:
self.last_node.next_node = Node(data, None)
self.last_node = self.last_node.next_node
return True
def to_list(self) -> "list":
"""return linked list as python list
Returns:
list[Any]: list containing data from nodes
"""
lst = []
if self.head is None:
return lst
node = self.head
while node:
lst.append(node.data)
node = node.next_node
return lst
def get_user_by_id(self, user_id):
"""return user data stored in linked list by id
Args:
user_id (int): user id
Returns:
data: user data
"""
node = self.head
while node:
if node.data["id"] == int(user_id):
return node.data
node = node.next_node
return None