-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDoublyLinkedList.py
More file actions
272 lines (227 loc) · 5.94 KB
/
DoublyLinkedList.py
File metadata and controls
272 lines (227 loc) · 5.94 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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
#
#Author : amit
#Created Date : 05-May -2018
#
'''
This program demonstrate the creation and some other functionalies of Doubly Linked List like:
1. push
2. push to the left
3. pop
4. pop from the left
5. search an element
6. remove a element by value
7. get the length of the list
8. generator to iterate over the list
9. clear/empty a list
'''
# Represent of a single node in a list
class Node:
def __init__(self, data=None, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self, data=None):
self.head = None
self.tail = None
self.count = 0
if data:
node = Node(data)
self.head = node
self.tail = node
self.count = 1
def push(self, data):
node = Node(data, prev= self.tail)
if not self.tail:
self.head = node
self.tail = node
else:
self.tail.next = node
self.tail = node
self.count += 1
def push_left(self, data):
node = Node(data, next=self.head)
if not self.head:
self.head = node
self.tail = node
else:
self.head.prev = node
self.head = node
self.count += 1
def pop(self):
if self.count == 0:
raise IndexError('List is Empty')
value = self.tail.data
# self.tail.prev.next = None
if self.count == 1:
self.tail = None
self.head = None
else:
self.tail = self.tail.prev
self.tail.next = None
self.count -= 1
return value
def pop_left(self):
if self.count == 0:
raise IndexError('List is Empty')
value = self.head.data
if self.count == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
self.count -= 1
return value
def iter(self):
current = self.head
while current:
value = current.data
current = current.next
yield value
def get_length(self):
return self.count
def search(self, data):
if self.count == 0:
raise IndexError('List is Empty')
for val in self.iter():
if val == data:
return True
return False
def remove(self, data):
if self.count == 0:
raise IndexError('List is Empty')
if self.head.data == data:
if self.pop_left():
return True
# prev = self.head
current = self.head.next
while current:
if current.data == data:
if current == self.tail:
current.prev.next = None
self.tail = current.prev
else:
current.prev.next = current.next
current.next.prev = current.prev
self.count -= 1
return True
current = current.next
return False
def clear(self):
self.head = None
self.tail = None
self.count = 0
# The function to test above created list.
def test():
print('Creating a new doubly linked list with 1 as first element')
new_list = DoublyLinkedList(1)
assert new_list is not None
assert new_list.get_length() == 1
print('-'*60)
print('adding the element 2,4,6,8,10 to end of the list')
new_list.push(2)
new_list.push(4)
new_list.push(6)
new_list.push(8)
new_list.push(10)
assert new_list.get_length() == 6
print('-'*60)
print('adding the element 3,5,7,9,11 to beginning of the list')
new_list.push_left(3)
new_list.push_left(5)
new_list.push_left(7)
new_list.push_left(9)
new_list.push_left(11)
assert new_list.get_length() == 11
print('-'*60)
print('seraching the element 32 in list. Must return False')
print(new_list.search(32))
print('-'*60)
print('seraching the element 2 in list. Must return True')
print(new_list.search(2))
assert new_list.get_length() == 11
print('-'*60)
print('Printing the list of length %d'%new_list.get_length())
i = 1
for item in new_list.iter():
print('index %d and value is -> %d'%(i ,item))
i += 1
print('-'*60)
print('Pop the last item from the list return value must be 10')
print(new_list.pop())
assert new_list.get_length() == 10
print('-'*60)
print('Pop the first item from the list return value must be 11')
print(new_list.pop_left())
assert new_list.get_length() == 9
print('-'*60)
print('Printing the list of length %d'%new_list.get_length())
i = 1
for item in new_list.iter():
print('index %d and value is -> %d'%(i ,item))
i += 1
print('-'*60)
print('Remove by value the first item')
new_list.remove(9)
assert new_list.get_length() == 8
i = 1
for item in new_list.iter():
print('index %d and value is -> %d'%(i ,item))
i += 1
print('-'*60)
print('Remove by value the last item')
new_list.remove(8)
assert new_list.get_length() == 7
i = 1
for item in new_list.iter():
print('index %d and value is -> %d'%(i ,item))
i += 1
print('-'*60)
print('Remove by value the any item')
if new_list.remove(8):
assert new_list.get_length() == 6
else:
assert new_list.get_length() == 7
i = 1
for item in new_list.iter():
print('index %d and value is -> %d'%(i ,item))
i += 1
print('-'*60)
print('Remove by value of a repeated itme')
new_list.push(1)
if new_list.remove(1):
assert new_list.get_length() == 7
else:
assert new_list.get_length() == 8
i = 1
for item in new_list.iter():
print('index %d and value is -> %d'%(i ,item))
i += 1
print('-'*60)
print('Clearing the list . Length must be 0 for the list')
new_list.clear()
assert new_list.get_length() == 0
assert new_list.head == None
assert new_list.tail == None
print('-'*60)
# Testing with the list of only on item
# Uncomment the below code block to test for functionalies with list of only one element
# singleElementList = DoublyLinkedList(90)
# print('Removing the LAST ITEM from the list return value must be 11')
# print(singleElementList.pop())
# assert singleElementList.get_length() == 0
# print('Removing the FIRST ITEM from the list must raise IndexError')
# print(singleElementList.pop_left())
# assert singleElementList.get_length() == 0
# print('-'*60)------------- HITING THIS
# print('Search the list')
# singleElementList.search(10)
# print('-'*60)
# print('Printing the list of length %d'%singleElementList.get_length())
# i = 1
# for item in singleElementList.iter():
# print('index %d and value is -> %d'%(i ,item))
# i += 1
# print('-'*60)
test()