Programming

  minte9
LearnRemember



Data Structures / Linked Lists 

What is a linked list?
What is the advantage of using linked lists?
What is a double linked list?
What can be a double linked list used for?

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
"""




References