-
Notifications
You must be signed in to change notification settings - Fork 43
/
doubly_linked.py
159 lines (115 loc) · 3.12 KB
/
doubly_linked.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
class Node:
def __init__(self, x):
self.val = x
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.cnt = 0
def addHead(self, x):
node = Node(x)
if self.cnt == 0:
self.head = node
self.tail = self.head
else:
node.next = self.head
self.head.prev = node
self.head = node
self.cnt += 1
def addTail(self, x):
node = Node(x)
if self.cnt == 0:
self.head = node
self.tail = self.head
else:
self.tail.next = node
node.prev = self.tail
self.tail = self.tail.next
self.cnt += 1
def insert(self, pos, x):
node = Node(x)
diff = self.cnt - pos
if diff < 0 or diff > self.cnt:
print("Invalid position")
return
elif diff == 0:
self.addTail(x)
elif diff == self.cnt:
self.addHead(x)
else:
cur = self.head
while pos > 1:
cur = cur.next
pos -= 1
node.next = cur.next
node.prev = cur
cur.next.prev = node
cur.next = node
self.cnt += 1
def removeHead(self):
if self.cnt == 0:
return
elif self.cnt == 1:
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev.next = None
self.head.prev = None
self.cnt -= 1
def removeTail(self):
if self.cnt == 0:
return
elif self.cnt == 1:
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next.prev = None
self.tail.next = None
self.cnt -= 1
def removePos(self, pos):
diff = self.cnt - pos
if diff < 0 or diff > self.cnt:
print("Invalid position")
return
elif diff == 0:
self.removeTail()
elif diff == self.cnt:
self.removeHead()
else:
cur = self.head
while pos > 1:
cur = cur.next
cur.next = cur.next.next
cur.next.prev = cur
cur = cur.next
self.cnt -= 1
def __getitem__(self, item):
if item < 0 or item > self.cnt - 1:
print("Invalid position")
return
else:
cur = self.head
while item > 0:
cur = cur.next
item -= 1
return cur.val
def size(self):
return self.cnt
def empty(self):
return self.cnt == 0
def printForward(self):
cur = self.head
while cur is not None:
print(cur.val, end=" ")
cur = cur.next
print("")
def printReverse(self):
cur = self.tail
while cur is not None:
print(cur.val, end = " ")
cur = cur.prev
print("")