Nodes
Connected data dispersed through memory are name
nodes.
class Node:
def __init__(self, data):
self.data = data
self.nextNode = None
node1 = Node("once")
node2 = Node("upon")
node3 = Node("a")
node4 = Node("time")
node1.nextNode = node2
node2.nextNode = node3
node3.nextNode = node4
print(node1.data, node1.nextNode.data)
print(node3.data, node3.nextNode.data)
Linked Lists
Each node has an extran information, the memory address of the
next node in the list.
Inserting and deleting at the
beginning of the list takes O(1) steps.
class LinkedList:
def __init__(self, firstNode):
self.firstNode = firstNode
def read(self, i):
node = self.firstNode
index = 0
while index < i:
index += 1
node = node.nextNode
return node
def insert(self, i, value):
newNode = Node(value)
if i == 0:
newNode.nextNode = self.firstNode
self.firstNode = newNode
return
currNode = self.firstNode
currIndex = 0
while currIndex < i-1:
currNode = currNode.nextNode
currIndex += 1
newNode.nextNode = currNode.nextNode
currNode.nextNode = newNode
return
list = LinkedList(node1)
list.insert(0, "start")
list.insert(4, "purple")
print(list.read(0).data)
print(list.read(1).data)
print(list.read(2).data)
print(list.read(3).data)
print(list.read(4).data)
print(list.read(5).data)
Double Linked Lists
It is a linked list with
two links that points to the previous and next node.
Insertion and deletion at the
beggining and end takes O(1) steps.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoubleLinkedList:
def __init__(self, first, last):
self.first = first
self.last = last
def insert_at_end(self, value):
newNode = Node(value)
newNode.prev = self.last
self.last.next = newNode
self.last = newNode
node1 = Node("once")
node2 = Node("upon")
node3 = Node("a")
node4 = Node("time")
node1.next = node2
node2.next = node3
node3.next = node4
node2.prev = node1
node3.prev = node2
node4.prev = node3
print("Node1 =", node1.data, "| Next =", node1.next.data)
print("Node2 =", node2.data, "| Prev =", node2.prev.data, "| Next =", node2.next.data)
print("Node3 =", node3.data, "| Prev =", node3.prev.data, "| Next =", node3.next.data)
print("Node4 =", node4.data, "| Prev =", node4.prev.data, "\n")
list = DoubleLinkedList(node1, node4)
list.insert_at_end("purple")
print("Double Linked List | Insert at the end:")
print("Node4 =", node4.data, "| Prev =", node4.prev.data, "| Next =", node4.next.data)
Queue
Double Linked Lists are
perfect data structure for a queue (insert at end, remove from front).
class DoubleLinkedList:
def __init__(self, first, last):
self.first = first
self.last = last
def insert_at_end(self, value):
newNode = Node(value)
newNode.prev = self.last
self.last.next = newNode
self.last = newNode
def remove_from_front(self):
self.first = self.first.next
class Dequeue:
def __init__(self, startNode, endNode):
self.data = DoubleLinkedList(startNode, endNode)
def append(self, item):
self.data.insert_at_end(item)
def popleft(self):
self.data.remove_from_front()
queue = Dequeue(node1, node4)
print("Init --")
print("First =", queue.data.first.data, "| last =", queue.data.last.data)
print("Second =", queue.data.first.next.data, "\n")
print("Append last & Remove first --")
queue.append("extra")
queue.popleft()
print("First =", queue.data.first.data, "| last =", queue.data.last.data)