-
Notifications
You must be signed in to change notification settings - Fork 0
/
doubly_ll.py
163 lines (119 loc) · 3.45 KB
/
doubly_ll.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
161
162
163
class Node:
def __init__(self,value):
self.value = value
self.next = None
self.prev = None
class DoublyLinkedList():
def __init__(self,value):
new_node = Node(value)
self.head = new_node
self.tail = new_node
self.length = 1
def append(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.length += 1
def pop(self):
if self.length == 0:
return None
temp = self.tail
self.tail = self.tail.prev
self.tail.next = None
temp.prev = None
self.length -= 1
if self.length == 0:
self.head = None
self.tail = None
return temp.value
def prepend(self, value):
new_node = Node(value)
if self.head is None:
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.length += 1
def pop_first(self):
if self.length == 0:
return None
temp = self.head
self.head = self.head.next
self.head.prev = None
temp.next = None
self.length -= 1
if self.length == 0:
self.head = None
self.tail = None
return temp
def get(self, index):
if index < 0 or index >= self.length:
return None
if index < self.length/2:
temp = self.head
for _ in range(index):
temp = temp.next
else:
temp = self.tail
for i in range(self.length - 1, index, -1): #reverse counting
temp = temp.prev
return temp
def set_value(self, value, index):
temp = self.get(index)
if temp:
temp.value = value
return True
return False
def insert(self, index, value):
if index < 0 or index > self.length:
return False
if index == 0:
return self.prepend(value)
if index == self.length:
return self.append(value)
before = self.get(index - 1)
after = before.next
new_node = Node(value)
after.prev = new_node
before.next = new_node
new_node.next = after
new_node.prev = before
self.length += 1
return True
def remove(self,index):
if index < 0 or index >= self.length:
return False
if index == 0:
return self.pop_first()
if index == self.length - 1:
return self.pop()
temp =self.get(index)
temp.next.prev = temp.prev
temp.prev.next = temp.next
temp.next = None
temp.prev = None
self.length -= 1
return temp
def print_list(self):
temp = self.head
while temp is not None:
print(temp.value)
temp = temp.next
doubly_ll = DoublyLinkedList(2)
doubly_ll.append(3)
doubly_ll.append(4)
doubly_ll.append(5)
doubly_ll.append(6)
# doubly_ll.pop()
doubly_ll.prepend(1)
# doubly_ll.pop_first()
# print(doubly_ll.get(3))
doubly_ll.insert(2, 555)
doubly_ll.print_list()