Created
August 2, 2016 10:27
-
-
Save MyGodIsHe/825df4757b50f68c5302d93ee959eec8 to your computer and use it in GitHub Desktop.
Doubly linked list on python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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