myLinkedList_doubly
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175
class Node():
def __init__(self, value, next_node=None, prev_node=None):
self.value = value
self.next_node = next_node
self.prev_node = prev_node
class LinkedList():
def __init__(self, value_first_item):
self.head = Node(value_first_item)
self.length = 1
self.tail = self.head
def get_head(self):
return self.head.value
def get_tail(self):
return self.tail.value
def append(self, value):
new_node = Node(value, next_node=None, prev_node=self.tail)
self.tail.next_node = new_node
self.tail = new_node
self.length+=1
def prepend(self, value):
new_node = Node(value, next_node=self.head)
self.head.prev_node = new_node
self.head = new_node
self.length+=1
def traverse_to_index(self, index):
if index > self.length-1:
return None
raise IndexError("index out of boundaries")
curr_node = self.head
curr_index = 0
if index == 0:
return curr_node
while curr_node.next_node != None:
curr_node = curr_node.next_node
curr_index+=1
if curr_index == index:
return curr_node
def traverse_to_index_backwards(self, index):
if index > self.length-1:
return None
raise IndexError("index out of boundaries")
curr_node = self.tail
curr_index = self.length-1
while curr_node.prev_node != None:
if curr_index == index:
break
curr_node = curr_node.prev_node
curr_index-=1
return curr_node
def traverse(self, index):
if index > (self.length/2):
return self.traverse_to_index_backwards(index)
else:
return self.traverse_to_index(index)
def get(self, index):
""" get the value of a specific index in the linked list."""
if index < 0:
return None
raise IndexError("No negative indexes")
elif index > self.length-1:
return None
raise IndexError("index out of boundaries")
elif index == self.length:
return self.get_tail()
elif index == 0:
return self.get_head()
return self.traverse(index).value
def insert(self, value, index):
""" Insert a new node in the middle of the list"""
if index < 0:
raise IndexError("No negative indexes")
elif index > self.length-1:
raise IndexError("index out of boundaries")
new_node = Node(value)
curr_node = self.traverse(index)
new_node.next_node = curr_node
new_node.prev_node = curr_node.prev_node
prev_node = new_node.prev_node
prev_node.next_node = new_node
curr_node.prev_node = new_node
self.length+=1
def printLinkedList(self):
curr_node = self.head
curr_index = 0
print(f"{curr_index}: {curr_node.value}")
while curr_node.next_node != None:
curr_node = curr_node.next_node
curr_index+=1
print(f"{curr_index}: {curr_node.value}")
print("Hello World!")
myLinkedList = LinkedList(5)
myLinkedList.append(10)
myLinkedList.append(15)
assert(myLinkedList.get_head() == 5)
assert(myLinkedList.get_tail() == 15)
assert(myLinkedList.traverse_to_index(2).value == 15)
myLinkedList.append(20)
assert(myLinkedList.traverse_to_index(3).value == 20)
assert(myLinkedList.traverse_to_index(4) == None)
assert(myLinkedList.traverse_to_index(0).value == 5)
assert(myLinkedList.traverse_to_index_backwards(3).value == 20)
assert(myLinkedList.traverse_to_index_backwards(4) == None)
assert(myLinkedList.get(index=0) == 5)
assert(myLinkedList.get(index=1) == 10)
assert(myLinkedList.get(index=2) == 15)
assert(myLinkedList.get(index=3) == 20)
assert(myLinkedList.get(index=4) == None)
myLinkedList.prepend(2)
assert(myLinkedList.get(index=0) == 2)
assert(myLinkedList.get(index=1)== 5)
assert(myLinkedList.get(index=2) == 10)
assert(myLinkedList.get(index=3) == 15)
assert(myLinkedList.get(index=4) == 20)
assert(myLinkedList.get(index=5) == None)
myLinkedList.insert(value=7,index=2)
assert(myLinkedList.get(index=0) == 2)
assert(myLinkedList.get(index=1)== 5)
assert(myLinkedList.get(index=2)== 7)
assert(myLinkedList.get(index=3) == 10)
assert(myLinkedList.get(index=4) == 15)
assert(myLinkedList.get(index=5) == 20)
assert(myLinkedList.get(index=6) == None)
# assert(myLinkedList.get_head() == 2)
# assert(myLinkedList.get(0) == 2)
# assert(myLinkedList.get(2)==7)
# myLinkedList.printLinkedList()
print("Good-bye Cruel World")
Python
INFO