-
Notifications
You must be signed in to change notification settings - Fork 1
/
linkedlist.py
143 lines (122 loc) · 3.24 KB
/
linkedlist.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
from listnode.node import Node
from itertools import chain
class LinkedList:
head = None
tail = None
size = 0
double = False
def __init__(self, iterable=None, double=False):
self.double = double
if iterable:
left = right = None
nodes = (Node(item) for item in iterable)
for n in nodes:
self.head = n if self.isempty() else self.head
right = n
if left:
left.next = right
if self.double:
right.prev = left
left = right
self.size += 1
self.tail = n
def __iter__(self):
n = self.head
while n:
yield n
n = n.next
def __len__(self):
return self.size
def __eq__(self, other):
if len(self) != len(other):
return False
for n1, n2 in zip(self, other):
if n1 != n2:
return False
return True
def __bool__(self):
return not(self.isempty())
def __str__(self):
return 'head({})...tail({})'.format(self.head.data, self.tail.data)
def isempty(self):
return self.size == 0
def inserthead(self, data=None, node=None):
if data:
node = Node(data)
node.next = self.head
self.head = node
elif node:
node.next = self.head
self.head = node
else:
raise TypeError("Provide either the data value or the Node object")
self.size += 1
def inserttail(self, data=None, node=None):
if self.isempty():
n = Node(data)
self.tail = self.head = n
else:
if data:
node = Node(data)
self.tail.next = node
node.next = None
if self.double:
node.prev = self.tail
self.tail = node
elif node:
self.tail.next = node
node.next = None
if self.double:
node.prev = self.tail
self.tail = node
else:
raise TypeError("Provide either the data value or the Node object")
self.size += 1
insert = inserttail
def preinsert(self, target_node, a_node):
# Insert a_node before the target_node in a given linkedlist.
for n in self:
if n.next == target_node:
a_node.next = n.next
if self.double:
a_node.prev = n
a_node.next.prev = a_node
n.next = a_node
break
def postinsert(self, target_node, a_node):
# Insert a_node after the target_node in a given linkedlist.
a_node.next = target_node.next
target_node.next = a_node
if self.double:
a_node.next.prev = a_node
a_node.prev = target_node
def iscycle(self):
# returns True if a cycle exists in the LinkedList.
if self.isempty():
return False
h1 = h2 = self.head
while h1 and h2:
h1 = self.next
h2 = self.next.next
if h1 == h2:
return True
return False
def getnode(self, pos=None, data=None):
if pos:
if 1 <= pos <= len(self):
# get the i'th node.
n = self.head
while pos != 1:
n = n.next
pos -= 1
else:
raise TypeError("There are not that many nodes in the linked list")
elif data:
n = self.head
while n:
if n.data == data:
break
n = n.next
else:
raise TypeError("Provide either the position or the data in the node object")
return n