Linked List - Nodes
""" LINKED LIST - NODES
-----------------------
A Node is a small container that holds:
- data (the actual value)
- nextNode (a reference to the next node in memory)
Important:
- nodes are NOT stored next to each other in memory
- each node only knows where the NEXT node is
- we must follow the links step by step
Real-life analogy:
A treasure hunt clue that tells you:
- the message
- where the next clue is
-------------------------
"""
class Node:
def __init__(self, data):
self.data = data # The value stored in the node
self.next = None # Reference to the next node
# Example: Manual Node Linking
# ----------------------------
node1 = Node("Go to the oak tree")
node2 = Node("Look under the bench")
node3 = Node("Check the fountain")
node1.next = node2
node2.next = node3
print(node1.data, '->', node1.next.data)
print(node2.data, '->', node2.next.data)
# ------------------------------------------
# Go to the oak tree -> Look under the bench
# Look under the bench -> Check the fountain
Linked Lists - Operations
""" LINKED LIST - OPERATIONS
----------------------------
Concept:
- Keep track ONLY of the first node
- Traverses nodes by following next references
- Has no direct access by index (unlike arrays)
Time Complexity:
- Read (by index): O(n)
- Insert at beggining: O(1)
- Insert elsewhere: O(n)
Below:
- Linked list that stores a reference to the first node.
--------------------------------------------------------
"""
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, first):
self.first = first
# --------------------------
# READ value at index / O(n)
# --------------------------
def read(self, index):
current = self.first
i = 0
while i < index:
current = current.next
i += 1
return current
# ----------------------------
# INSERT value at index / O(n)
# ----------------------------
def insert(self, index, value):
node = Node(value)
# Insert at the beginning / O(1)
if index == 0:
node.next = self.first
self.first = node
return
# Insert elsewhere / O(n)
current = self.first
i = 0
# Stop at node BEFORE insertion point
while i < index - 1:
current = current.next
i += 1
node.next = current.next
current.next = node
# ---------------------
# Example Usage & Tests
# ---------------------
# Create nodes
n1 = Node("Start")
n2 = Node("Forest")
n3 = Node("River")
n4 = Node("Treasure")
# Link nodes
n1.next = n2
n2.next = n3
n3.next = n4
# Create linked list
hunt = LinkedList(n1)
# Insert new nodes
hunt.insert(0, "Map")
hunt.insert(3, "Cave")
# Read nodes
print(hunt.read(0).data) # Map
print(hunt.read(1).data) # Start
print(hunt.read(2).data) # Forest
print(hunt.read(3).data) # Cave
print(hunt.read(4).data) # River
print(hunt.read(5).data) # Treasure
Linked List - Insert Tail
""" LINKED LIST - INSERT AT TAIL
--------------------------------
Concept:
- We only store a reference to the FIRST node (head)
- Nodes know ONLY about the next node
- To insert at the tail, we must traverse the list
Key Insights:
- Assigning `current = self.head` does NOT copy the node
- `current` and `self.head point` to the SAME object
- Moving `current` does not move `self.head`
- Modifying the `current.next` MUTTATES the list itself (!)
Time Complexity:
- Insert at tail: O(n)
-----------------------
"""
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, head=None):
self.head = head
def insert_at_tail(self, value):
new_node = Node(value)
# -------------------------------------
# Case 1: Empty list
# The new node becames the first (head)
# -------------------------------------
if self.head is None:
self.head = new_node
# -----------------------------
# Case 2: Non-empty list
# Start traversal from the head
# -----------------------------
current = self.head
# ---------------------------------------------
# Move `current` until it reaches the last node
# (the node whose `next` is None)
# ---------------------------------------------
while current.next is not None:
current = current.next
# ------------------------------------------------
# We mutate the last node, extending the list that
# `self.head` already points to.
# ------------------------------------------------
current.next = new_node
# ---------------------
# Example Usage & Tests
# ---------------------
# Create nodes
n1 = Node("Start")
n2 = Node("Forest")
n3 = Node("River")
# Link nodes
n1.next = n2
n2.next = n3
# Create linked list
hunt = LinkedList(n1)
# Insert at tail
hunt.insert_at_tail("Cave")
hunt.insert_at_tail("Treasure")
# Traverse and print
current = hunt.head
while current:
print(current.data)
current = current.next
# --------------------
# Start
# Forest
# River
# Cave
# Treasure
