-
Notifications
You must be signed in to change notification settings - Fork 0
/
double_linklist.py
160 lines (131 loc) · 4.74 KB
/
double_linklist.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
152
153
154
155
156
157
158
159
160
from typing import Any, Optional
class Node:
"""
Represents a node in a doubly linked list.
"""
def __init__(self, data: Any) -> None:
"""
Initializes a new instance of the Node class.
Args:
data: The data to be stored in the node.
"""
self.data = data
self.next_node: Optional[Node] = None
self.previous_node: Optional[Node] = None
class DoublyLinkedList:
"""
Represents a doubly linked list.
"""
def __init__(self, first_node: Optional[Node] = None, last_node: Optional[Node] = None) -> None:
"""
Initializes a new instance of the DoublyLinkedList class.
Args:
first_node: The first node of the list.
last_node: The last node of the list.
"""
self.first_node: Optional[Node] = first_node
self.last_node: Optional[Node] = last_node
def insert_at_end(self, value: Any) -> None:
"""
Inserts a new node with the given value at the end of the linked list.
Args:
value: The value to be inserted.
"""
new_node = Node(value)
if self.first_node is None:
# If there are no elements yet in the linked list
self.first_node = new_node
self.last_node = new_node
else:
# If the linked list already has at least one node
new_node.previous_node = self.last_node
self.last_node.next_node = new_node
self.last_node = new_node
def remove_from_front(self) -> Optional['Node']:
"""
Remove the node from the front of the doubly linked list.
Returns:
Optional[Node]: The removed node, or None if the list is empty.
"""
removed_node = self.first_node
if self.first_node:
self.first_node = self.first_node.next_node
return removed_node
def print_list(self) -> None:
"""
Print the data of each node in the doubly linked list.
"""
current_node = self.first_node
while current_node:
print(current_node.data)
current_node = current_node.next_node
def print_in_reverse(self) -> None:
"""
Print the data of each node in the doubly linked list in reverse order.
"""
current_node = self.last_node
while current_node:
print(current_node.data)
current_node = current_node.previous_node
def get_last(self) -> Optional[Any]:
"""
Get the data of the last node in the doubly linked list.
Returns:
Optional[Any]: The data of the last node, or None if the list is empty.
"""
current_node = self.first_node
while current_node and current_node.next_node:
current_node = current_node.next_node
return current_node.data if current_node else None
def reverse(self) -> None:
"""
Reverse the order of nodes in the doubly linked list in-place.
"""
previous_node = None
current_node = self.first_node
while current_node:
next_node = current_node.next_node
current_node.next_node = previous_node
previous_node = current_node
current_node = next_node
self.first_node = previous_node
def delete_middle_node(self, node: 'Node') -> None:
"""
Delete a node in the middle of the doubly linked list, given only access to that node.
Args:
node (Node): The node to be deleted.
"""
if node and node.next_node:
node.data = node.next_node.data
node.next_node = node.next_node.next_node
class Queue:
"""
A Queue class implemented using a doubly linked list.
"""
def __init__(self) -> None:
"""
Initialize an empty Queue.
"""
self.data = DoublyLinkedList()
def enqueue(self, element: Any) -> None:
"""
Add an element to the end of the Queue.
Args:
element (Any): The element to be added.
"""
self.data.insert_at_end(element)
def dequeue(self) -> Optional[Any]:
"""
Remove an element from the front of the Queue.
Returns:
Optional[Any]: The removed element, or None if the Queue is empty.
"""
removed_node = self.data.remove_from_front()
return removed_node.data if removed_node else None
def read(self) -> Optional[Any]:
"""
Read the element at the front of the Queue without removing it.
Returns:
Optional[Any]: The front element, or None if the Queue is empty.
"""
return self.data.first_node.data if self.data.first_node else None