forked from TheAlgorithms/Python
- Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdeque_doubly.py
More file actions
Latest commit
143 lines (123 loc) · 3.98 KB
/
Copy pathdeque_doubly.py
File metadata and controls
143 lines (123 loc) · 3.98 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
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
"""
Implementing Deque using DoublyLinkedList ...
Operations:
1. insertion in the front -> O(1)
2. insertion in the end -> O(1)
3. remove from the front -> O(1)
4. remove from the end -> O(1)
"""
class_DoublyLinkedBase:
"""A Private class (to be inherited)"""
class_Node:
__slots__="_data", "_next", "_prev"
def__init__(self, link_p, element, link_n):
self._prev=link_p
self._data=element
self._next=link_n
defhas_next_and_prev(self):
return (
f" Prev -> {self._previsnotNone}, Next -> {self._nextisnotNone}"
)
def__init__(self):
self._header=self._Node(None, None, None)
self._trailer=self._Node(None, None, None)
self._header._next=self._trailer
self._trailer._prev=self._header
self._size=0
def__len__(self):
returnself._size
defis_empty(self):
returnself.__len__() ==0
def_insert(self, predecessor, e, successor):
# Create new_node by setting it's prev.link -> header
# setting it's next.link -> trailer
new_node=self._Node(predecessor, e, successor)
predecessor._next=new_node
successor._prev=new_node
self._size+=1
returnself
def_delete(self, node):
predecessor=node._prev
successor=node._next
predecessor._next=successor
successor._prev=predecessor
self._size-=1
temp=node._data
node._prev=node._next=node._data=None
delnode
returntemp
classLinkedDeque(_DoublyLinkedBase):
deffirst(self):
"""return first element
>>> d = LinkedDeque()
>>> d.add_first('A').first()
'A'
>>> d.add_first('B').first()
'B'
"""
ifself.is_empty():
raiseException("List is empty")
returnself._header._next._data
deflast(self):
"""return last element
>>> d = LinkedDeque()
>>> d.add_last('A').last()
'A'
>>> d.add_last('B').last()
'B'
"""
ifself.is_empty():
raiseException("List is empty")
returnself._trailer._prev._data
# DEque Insert Operations (At the front, At the end)
defadd_first(self, element):
"""insertion in the front
>>> LinkedDeque().add_first('AV').first()
'AV'
"""
returnself._insert(self._header, element, self._header._next)
defadd_last(self, element):
"""insertion in the end
>>> LinkedDeque().add_last('B').last()
'B'
"""
returnself._insert(self._trailer._prev, element, self._trailer)
# DEqueu Remove Operations (At the front, At the end)
defremove_first(self):
"""removal from the front
>>> d = LinkedDeque()
>>> d.is_empty()
True
>>> d.remove_first()
Traceback (most recent call last):
...
IndexError: remove_first from empty list
>>> d.add_first('A') # doctest: +ELLIPSIS
<data_structures.linked_list.deque_doubly.LinkedDeque object at ...
>>> d.remove_first()
'A'
>>> d.is_empty()
True
"""
ifself.is_empty():
raiseIndexError("remove_first from empty list")
returnself._delete(self._header._next)
defremove_last(self):
"""removal in the end
>>> d = LinkedDeque()
>>> d.is_empty()
True
>>> d.remove_last()
Traceback (most recent call last):
...
IndexError: remove_first from empty list
>>> d.add_first('A') # doctest: +ELLIPSIS
<data_structures.linked_list.deque_doubly.LinkedDeque object at ...
>>> d.remove_last()
'A'
>>> d.is_empty()
True
"""
ifself.is_empty():
raiseIndexError("remove_first from empty list")
returnself._delete(self._trailer._prev)