Skip to content

Instantly share code, notes, and snippets.

@keitaoouchi

keitaoouchi/linkedlist.py

Created April 3, 2012 04:28
Show Gist options
  • Save keitaoouchi/2289299 to your computer and use it in GitHub Desktop.
Save keitaoouchi/2289299 to your computer and use it in GitHub Desktop.
Download ZIP
LinkedList implementation with python -- http://d.hatena.ne.jp/yuku_t/20110414/1302786396
Raw
linkedlist.py
# -*- coding: utf-8 -*-
from collections import Iterator, Sequence, MutableSequence
class MyLinkedList(MutableSequence):
def __init__(self, *value):
'''
>>> l = MyLinkedList(1,2,3)
>>> l.pop()
3
>>> l.pop()
2
>>> l.pop()
1
>>> l.pop()
Traceback (most recent call last):
...
IndexError
'''
self.head = None
self.last = None
self.length = 0
if value:
for v in value:
self.append(v)
def __contains__(self, value):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> 1 in l
True
>>> 2 in l
False
'''
for val in iter(self):
if val == value:
return True
return False
def __iter__(self):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> iterator = iter(l)
>>> isinstance(iterator, MyIterator)
True
>>> next(iterator)
1
>>> item = next(iterator)
Traceback (most recent call last):
...
StopIteration
>>> l.append(2)
>>> for i in l:
... print i
...
1
2
'''
return MyIterator(self.head)
def __len__(self):
'''
>>> l = MyLinkedList()
>>> len(l)
0
>>> l.append(1)
>>> len(l)
1
>>> l.append(2)
>>> len(l)
2
'''
return self.length
def __getitem__(self, key):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> l[0] # l.__getitem__(0)
1
>>> l[2]
Traceback (most recent call last):
...
IndexError
>>> l['string']
Traceback (most recent call last):
...
TypeError
>>> l.append(2)
>>> l[-2]
1
>>> l[2]
Traceback (most recent call last):
...
IndexError
>>> l[-3]
Traceback (most recent call last):
...
IndexError
'''
if not isinstance(key, int):
raise TypeError
length = len(self)
id = key if key >= 0 else length + key
if not 0 <= id < length:
raise IndexError
elif id == 0:
return self.head.value
elif id == len(self) - 1:
return self.last.value
else:
count = 0
cursor = self.head
while count < id:
cursor = cursor.next
count += 1
return cursor.value
def __setitem__(self, key, value):
'''
>>> l = MyLinkedList()
>>> l.append(1) # [1]
>>> l[0] = 2 # [2]
>>> l[0]
2
>>> l[1] = 2
Traceback (most recent call last):
...
IndexError
>>> l['string'] = 2
Traceback (most recent call last):
...
TypeError
>>> l.append(2) # [2, 2]
>>> l[-2] = 3 # [3, 2]
>>> l[0]
3
>>> l[2]
Traceback (most recent call last):
...
IndexError
>>> l[-3]
Traceback (most recent call last):
...
IndexError
'''
if not isinstance(key, int):
raise TypeError
length = len(self)
id = key if key >= 0 else length + key
if not 0 <= id < length:
raise IndexError
else:
count = 0
cursor = self.head
while count < id:
cursor = cursor.next
count += 1
cursor.value = value
def __delitem__(self, key):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> l.append(2)
>>> l[0]
1
>>> del l[0]
>>> l[0]
2
>>> del l[1]
Traceback (most recent call last):
...
IndexError
>>> del l['string']
Traceback (most recent call last):
...
TypeError
>>> del l[-1]
>>> l[0]
Traceback (most recent call last):
...
IndexError
'''
if not isinstance(key, int):
raise TypeError
length = len(self)
id = key if key >= 0 else length + key
if not 0 <= id < length:
raise IndexError
if id == 0:
self.head = self.head.next
elif id == len(self) - 1:
self.pop()
else:
count = 0
cursor = self.head
while count < id:
cursor = cursor.next
count += 1
prev = cursor.prev if cursor else None
next = cursor.next if cursor else None
if prev:
prev.next = next
if next:
next.prev = prev
self.length -= 1
def __iadd__(self, value):
'''
>>> l = MyLinkedList()
>>> l += 1
>>> l[0]
1
>>> l += 2
>>> l[1]
2
'''
self.append(value)
return self
def __reversed__(self):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> l.append(2)
>>> iterator = reversed(l)
>>> isinstance(iterator, MyReverseIterator)
True
>>> next(iterator)
2
>>> next(iterator)
1
>>> next(iterator)
Traceback (most recent call last):
...
StopIteration
>>> for i in reversed(l):
... print i
...
2
1
'''
return MyReverseIterator(self.last)
def append(self, value):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> l.append(2)
'''
if not len(self):
node = Node(value)
self.head = node
self.last = self.head
else:
node = Node(value)
node.prev = self.last
self.last.next = node
self.last = node
self.length += 1
def pop(self):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> l.append(2)
>>> l.pop()
2
>>> l.pop()
1
>>> l.pop()
Traceback (most recent call last):
...
IndexError
'''
if len(self):
self.length -= 1
result = self.last.value
self.last = self.last.prev
if len(self) <= 1:
self.head = self.last
return result
else:
raise IndexError
def reverse(self):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> l.append(2)
>>> l.reverse()
>>> l.head.next
1
>>> l.last.prev
2
>>> l.pop()
1
>>> l.head
2
>>> l.last
2
>>> l.pop()
2
'''
self.head = self.last
cursor = self.last
while cursor:
nexx = cursor.next
cursor.next = cursor.prev
cursor.prev = nexx
self.last = cursor
cursor = cursor.next
def index(self, value):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> l.append(2)
>>> l.append(1)
>>> l.index(1)
0
>>> l.index(2)
1
>>> l.index(3)
Traceback (most recent call last):
...
ValueError
'''
iterator = iter(self)
index = 0
try:
while next(iterator) != value:
index += 1
return index
except StopIteration:
raise ValueError
def insert(self, key, value):
'''
>>> l = MyLinkedList()
>>> l.insert(0,10)
>>> l.pop()
10
>>> len(l)
0
>>> l.append(1) # [1]
>>> l.insert(0, 2) # [2, 1]
>>> l.insert(1, 3) # [2, 3, 1]
>>> l.insert(-1, 4) # [2, 3, 4, 1]
>>> l.insert(-3, 6) # [2, 6, 3, 4, 1]
>>> l.insert(-5, 5) # [5, 2, 6, 3, 4, 1]
>>> l.pop()
1
>>> l.pop()
4
>>> l.pop()
3
>>> l.append(1) # [5, 2, 6, 1]
>>> l.insert(100, 2) # [5, 2, 6, 1, 2]
>>> l.pop()
2
>>> l.insert(-100, 0) # [0, 5, 2, 6, 1]
>>> l.pop()
1
>>> l.pop()
6
>>> l.pop()
2
>>> l.pop()
5
>>> l.pop()
0
'''
if not isinstance(key, int):
raise TypeError
length = len(self)
id = key if key >= 0 else length + key
if id >= length:
self.append(value)
else:
if id < 0:
id = 0
count = 0
cursor = self.head
while count < id:
cursor = cursor.next
count += 1
node = Node(value)
if cursor:
if cursor.prev:
cursor.prev.next = node
node.prev = cursor.prev
cursor.prev = node
node.next = cursor
if cursor is self.head:
self.head = node
self.length += 1
def count(self, value):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> l.append(2)
>>> l.append(1)
>>> l.count(1)
2
>>> l.count(3)
0
>>> 1 is 1.0
False
>>> 1 == 1.0
True
>>> l.count(1.0)
2
'''
count = 0
for val in iter(self):
if val == value:
count += 1
return count
def remove(self, value):
'''
>>> l = MyLinkedList()
>>> l.append(1)
>>> l.append(2)
>>> l.append(1)
>>> l.append(2)
>>> l.remove(2)
>>> l.pop()
2
>>> l.pop()
1
>>> l.pop()
1
>>> l.pop()
Traceback (most recent call last):
...
IndexError
>>> l.remove(2)
Traceback (most recent call last):
...
ValueError
'''
iterator = iter(self)
index = 0
try:
while next(iterator) != value:
index += 1
del self[index]
except StopIteration:
raise ValueError
def extend(self, seq):
'''
>>> l = MyLinkedList()
>>> l.extend([1,2,3])
>>> l.pop()
3
>>> l.pop()
2
>>> l.pop()
1
>>> from collections import Iterable
>>> isinstance([], Iterable)
True
>>> isinstance((), Iterable)
True
>>> isinstance({}, Iterable)
True
>>> isinstance(1, Iterable)
False
>>> isinstance('', Iterable)
True
>>> 'string'[1]
't'
'''
for val in seq:
self.append(val)
class MyIterator(Iterator):
def __init__(self, node):
self.cursor = node
def next(self):
if self.cursor:
result = self.cursor.value
self.cursor = self.cursor.next
return result
else:
raise StopIteration
__next__ = next
class MyReverseIterator(Iterator):
def __init__(self, node):
self.cursor = node
def next(self):
if self.cursor:
result = self.cursor.value
self.cursor = self.cursor.prev
return result
else:
raise StopIteration
__next__ = next
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
def __repr__(self):
return repr(self.value)
if __name__ == '__main__':
import doctest
doctest.testmod()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment