Skip to content

Instantly share code, notes, and snippets.

@MyGodIsHe
Created August 2, 2016 10:27
Show Gist options
  • Save MyGodIsHe/825df4757b50f68c5302d93ee959eec8 to your computer and use it in GitHub Desktop.
Save MyGodIsHe/825df4757b50f68c5302d93ee959eec8 to your computer and use it in GitHub Desktop.
Doubly linked list on python
class Item(object):
def __init__(self, data):
self.prev = None
self.next = None
self.data = data
def delete(self):
if self.prev != None:
self.prev.next = self.next
if self.next != None:
self.next.prev = self.prev
def after(self, item):
if self.next != None:
self.next.prev = item
item.prev = self
item.next = self.next
self.next = item
def before(self, item):
if self.prev != None:
self.prev.next = item
item.prev = self.prev
item.next = self
self.prev = item
class List(object):
def __init__(self):
self.head = None
self.tail = None
def append(self, data):
if self.tail != None:
self.tail.after(Item(data))
self.tail = self.tail.next
else:
self.head = Item(data)
self.tail = self.head
def insert(self, index, data):
index = self.__check(index)
counter = 0
i = self.head
while i != None:
if counter == index:
i.before(Item(data))
if i == self.head:
self.head = self.head.prev
return
i = i.next
counter += 1
raise IndexError('list index out of range')
def __check(self, index):
assert isinstance(index, int)
if index < 0:
index = len(self) + index
return index
def __enumerate(self):
counter = 0
i = self.head
while i != None:
yield counter, i
i = i.next
counter += 1
def __iter__(self):
i = self.head
while i != None:
yield i.data
i = i.next
def __reversed__(self):
i = self.tail
while i != None:
yield i.data
i = i.prev
def __contains__(self, data):
for i in self:
if i == data:
return True
return False
def __len__(self):
counter = 0
for _ in self:
counter += 1
return counter
def __getitem__(self, index):
if isinstance(index, slice):
if index.start == None:
start = 0
else:
start = self.__check(index.start)
if index.stop == None:
stop = len(self)
else:
stop = self.__check(index.stop)
if index.step == None:
step = 1
else:
step = index.step
assert isinstance(step, int) and step > 1
items = []
for n, i in self.__enumerate():
if n >= start and n < stop:
if (n - start) % step == 0:
items.append(i.data)
return items
else:
index = self.__check(index)
for n, i in self.__enumerate():
if n == index:
return i.data
raise IndexError('list index out of range')
def __setitem__(self, index, value):
index = self.__check(index)
for n, i in self.__enumerate():
if n == index:
i.data = value
return
raise IndexError('list assignment index out of range')
def __delitem__(self, index):
index = self.__check(index)
for n, i in self.__enumerate():
if n == index:
if i == self.head:
self.head = self.head.next
if i == self.tail:
self.tail = self.tail.prev
i.delete()
return
raise IndexError('list assignment index out of range')
def __repr__(self):
return ', '.join(map(str, self))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment