minte9 LearnRemember

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

# Output nodes
print(node1.data, node1.nextNode.data) # once upon
print(node3.data, node3.nextNode.data) # time
``````

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)

# We are inserting at the beginning
if i == 0:
newNode.nextNode = self.firstNode
self.firstNode = newNode # O(1) / Look Here
return

# We are inserting anywhere other than beggining
currNode = self.firstNode
currIndex = 0

# Find the node before where the new node will go
while currIndex < i-1:
currNode = currNode.nextNode
currIndex += 1

# Set new node next link
newNode.nextNode = currNode.nextNode

# Modify the link of the previus node
currNode.nextNode = newNode
return

# New list
list = LinkedList(node1)

# Insert at index
list.insert(0, "start")
list.insert(4, "purple")

# Output values
print(list.read(0).data) # start
print(list.read(1).data) # once
print(list.read(2).data) # upon
print(list.read(3).data) # a
print(list.read(4).data) # purple
print(list.read(5).data) # time
``````

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

# Output nodes (prev, next)
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")

# New list
list = DoubleLinkedList(node1, node4)

# Insert at end
list.insert_at_end("purple")

# Output node 4
print("Double Linked List | Insert at the end:")
print("Node4 =", node4.data, "| Prev =", node4.prev.data, "| Next =", node4.next.data)

"""
Node1 = once | Next = upon
Node2 = upon | Prev = once | Next = a
Node3 = a | Prev = upon | Next = time
Node4 = time | Prev = a

Double Linked List | Insert at the end:
Node4 = time | Prev = a | Next = purple
"""
``````

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()

# New queue
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")

# Append, popleft
print("Append last & Remove first --")
queue.append("extra")
queue.popleft()

print("First =", queue.data.first.data, "| last =", queue.data.last.data)

"""
Init --
First = once | last = time
Second = upon

Append last & Remove first --
First = upon | last = extra
"""
``````

Last update: 277 days ago