In [29]:
def rstr(o):
return o.__rstr__()
class DoubleLinkedList(object):
"""
Double linked list.
"""
# Dunder Methods...
def __init__(self):
self.head = None
self.tail = None
def __str__(self):
return ','.join(str(x) for x in self)
def __rstr__(self):
return ','.join(str(x) for x in self.reverse_iterator)
def __iter__(self):
return self.iterator
# Public Instance Properties...
@property
def iterator(self):
return (x.data for x in self._iterator)
@property
def reverse_iterator(self):
return (x.data for x in self._reverse_iterator)
@property
def is_empty(self):
return self.head is None
@property
def size(self):
return sum(1 for x in self.iterator)
# Public Instance Methods...
def prepend(self, data):
new_node = self._DoubleLinkedListNode(data)
if self.is_empty:
self.head = new_node
self.tail = new_node
else:
new_node.next_node = self.head
self.head.prev_node = new_node
self.head = new_node
def append(self, data):
new_node = self._DoubleLinkedListNode(data)
if self.is_empty:
self.head = new_node
self.tail = new_node
else:
new_node.prev_node = self.tail
self.tail.next_node = new_node
self.tail = new_node
def insert(self, index, data):
index = max(0, index)
if index == 0:
self.prepend(data)
else:
new_node = self._DoubleLinkedListNode(data)
try:
it = self._iterator
for i in range(index):
node = next(it)
if node.next_node:
new_node.next_node = node.next_node
new_node.prev_node = node
node.next_node.prev_node = new_node
node.next_node = new_node
else:
self.append(data)
except StopIteration:
self.append(data)
def pop(self):
if not self.is_empty:
data = self.tail.data
self.tail.prev_node.next_node = None
self.tail = self.tail.prev_node
return data
def popleft(self):
if not self.is_empty:
data = self.head.data
self.head.next_node.prev_node = None
self.head = self.head.next_node
return data
def remove(self, data):
for node in self._iterator:
if node.data == data:
if node == self.head:
self.popleft()
elif node == self.tail:
self.pop()
else:
node.next_node.prev_node = node.prev_node
node.prev_node.next_node = node.next_node
def index_of(self, data):
for i, node in enumerate(self):
if node == data:
return i
# Protected Instance Properties...
@property
def _iterator(self):
return self._iterator_impl(self.head, lambda x: x.next_node)
@property
def _reverse_iterator(self):
return self._iterator_impl(self.tail, lambda x: x.prev_node)
# Protected Instance Methods...
def _iterator_impl(self, start, get_next):
it = start
while True:
yield it
next_node = get_next(it)
if next_node == None:
break
it = next_node
# Protected Sub Classes...
class _DoubleLinkedListNode:
def __init__(self, data):
self.next_node = None
self.prev_node = None
self.data = data
def __str__(self):
return str(self.data)
l = DoubleLinkedList()
l.append(10)
l.append(20)
l.append(30)
print rstr(l), '\t', rstr(l)
l.insert(1, 0.25)
print str(l), '\t', rstr(l)
print l.pop()
print str(l), '\t', rstr(l)
print l.popleft()
print str(l), '\t', rstr(l)
print l.index_of(999)
print l.index_of(0.25)
print l.index_of(20)
l.append(1000)
l.append(1000000)
print str(l), '\t', rstr(l)
l.remove(1000)
print str(l), '\t', rstr(l)
l.remove(1000000)
print str(l), '\t', rstr(l)
l.remove(0.25)
print str(l), '\t', rstr(l)