DSA 36: Doubly Linked List [Part 4]

1. DoublyLinkedList (DLL)

DLL always keeps track of:

• head nodes,
• tail nodes,
• Not just head (Singly Linked List).

class Node():
    def __init__(self, data):
        self.data = data
        self.next_node = None
        self.prev_node = None
        
class DoublyLinkedList():
    def __init__(self, first_node: Node, last_node: Node):
        self.first_node = first_node
        self.last_node = last_node

2. Nodes & DoublyLinkedList: Setup

2.1 nodes Instances: Setup

node0 = Node("Once")
node1 = Node("Upon")
node2 = Node("A")
node3 = Node("Time")

node0.next_node=node1
node1.next_node=node2
node2.next_node=node3
node3.next_node=node0

node0.prev_node=node3
node1.prev_node=node0
node2.prev_node=node1
node3.prev_node=node2

2.2 double_linked_list Instance: Setup

dll = DoublyLinkedList(node0, node3)

3. append: DLL Instance Method

3.1 Incomplete Circular DLL (Ignore)

# TURSN OUT I WAS TRYING TO DO A CIRCULAR DLL FROM SCRATCH BEFORE THE STANDARD ONE
# def append_to_end_dll(doubly_linkedlist: DoublyLinkedList, new_node: Node)->None:
    
    
#     # ["once","upon","a","time"] -> ["once","upon","a","time","mate"]
#     ### A. Configure [new_node] to be [last_node]:
#     # [1] [new_node] -next-> [first_node]     # [2] [new_node] -prev-> [last_node] (current last node)
    
#     ### B. Configure [previous_last_node]: [next_node] to point to [new_node]
#     # previous_last_node.next_node -> new_node
    
#     ### C. Configure [first_node]: [prev_node] to point to [new_node]
#     # first_node.prev_node -> new_node
    
    
#     # NODE-POINTER STUFF
#     new_node.next_node = doubly_linkedlist.first_node       # [A1] # CIRCULAR VERSION ONLY
#     new_node.prev_node = doubly_linkedlist.last_node        # [A2]
    
#     doubly_linkedlist.last_node.next_node = new_node        # [B]
#     doubly_linkedlist.first_node.prev_node = new_node       # [C] # CIRCULAR VERSION ONLY
    
#     # DLL-POSITION STUFF
#     doubly_linkedlist.last_node=new_node
    
    
#     return None

3.2 Append for Standard DLL

• if not pythonic falsy syntax: previously introduced.

def append_to_end_dll(doubly_linkedlist: DoublyLinkedList, new_node: Node)->None:
    
    # [1] EMPTY DLL
    if not doubly_linkedlist.first_node: # ie first_node is None or falsy -> True
        doubly_linkedlist.first_node=new_node
        doubly_linkedlist.last_node=new_node
    
    # [2] NODE-POINTER STUFF
    # new_node.next_node = doubly_linkedlist.first_node       # [A1] CIRCULAR-ONLY
    new_node.prev_node = doubly_linkedlist.last_node        # [A2]
    
    doubly_linkedlist.last_node.next_node = new_node        # [B]
    # doubly_linkedlist.first_node.prev_node = new_node       # [C] CIRCULAR-ONLY
    
    # [3] DLL-NODE-POSITION STUFF
    doubly_linkedlist.last_node=new_node
    
    return None

3.3 Test

dll = DoublyLinkedList(node0, node3)
print(dll.last_node.data)
append_to_end_dll(dll, Node("mate"))
print(dll.last_node.data)
append_to_end_dll(dll, Node("lads"))
print(dll.last_node.data)

Time
mate
lads