Data Structures: Linked Lists
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
# Implement a linked list
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
self.tail = self.head
self.length = 1
def append(self, value):
node = Node(value)
self.tail.next = self.node
self.tail = node
self.length += 1
return self.head
def prepend(self, value):
node = Node(value)
node.next = self.head
self.head = node
self.length += 1
return self.head
def printList(self):
array = []
currentNode = self.head
while currentNode:
array.append(currentNode.value)
currentNode = currentNode.next
return array
def insert(index, value):
if index == 0:
return self.prepend(value)
elif index >= self.length:
return self.append(value)
node = Node(value)
currentNode = self.head.next
prevNode = self.head
count = 1
while currentNode:
if index == count:
prevNode.next = node
node.next = currentNode
self.length += 1
break
prevNode = currentNode
currentNode = currentNode.next
count += 1
return self.printList()
def remove(index):
if index == 0:
self.head = self.head.next
self.head.prev = None
self.length -= 1
return self.printList()
currentNode = self.head.next
prevNode = self.head
count = 1
while currentNode:
if index == count:
prevNode.next = currentNode.next
self.length -= 1
break
prevNode = currentNode
currentNode = currentNode.next
count += 1
return self.printList()
def reverse(self):
currentNode = self.head
prevNode = None
self.tail = self.head
while currentNode:
temp = currentNode
currentNode = currentNode.next
temp.next = prevNode
prevNode = temp
self.head = temp
return self.printList()
class Node:
def __init__(self, value):
self.value = value
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self, value):
self.head = Node(value)
self.tail = self.head
self.length = 1
def append(self, value):
node = Node(value)
self.tail.next = node
node.prev = self.tail
self.tail = node
self.length += 1
return self.head
def prepend(self, value):
node = Node(value)
node.next = self.head
node.prev = None
self.head = node
self.length += 1
return self.head
def printList(self):
array = []
currentNode = self.head
while currentNode:
array.append(currentNode.value)
currentNode = currentNode.next
return array
def insert(index, value):
if index == 0:
return self.prepend(value)
elif index >= self.length:
return self.append(value)
node = Node(value)
currentNode = self.head.next
prevNode = self.head
count = 1
while currentNode:
if index == count:
prevNode.next = node
node.prev = prevNode
node.next = currentNode
currentNode.prev = node
self.length += 1
break
prevNode = currentNode
currentNode = currentNode.next
count += 1
return self.printList()
def remove(index):
if index == 0:
self.head = self.head.next
self.length -= 1
return self.printList()
currentNode = self.head.next
prevNode = self.head
count = 1
while currentNode:
if index == count:
prevNode.next = currentNode.next
currentNode.next.prev = prevNode
self.length -= 1
return self.printList()
prevNode = currentNode
currentNode = currentNode.next
count += 1
return self.printList()
Python
INFO