Node Structure and Pointer Design in DSA Python

Mental Model

A node is a small container that holds data and a pointer to the next node, linking them like a chain.

Analogy: Imagine a treasure map where each clue points you to the next clue, forming a path to the treasure.

Node1[data|->] -> Node2[data|->] -> Node3[data|->] -> null

Dry Run Walkthrough

Input: Create a linked list with nodes holding values 1, 2, and 3 linked in order

Goal: Build a chain of nodes where each node points to the next, ending with null

Step 1: Create first node with value 1 and pointer null

Node1[1|null]

Why: Start the chain with the first node pointing to nothing

Step 2: Create second node with value 2 and pointer null

Node1[1|null]   Node2[2|null]

Why: Prepare the next node to link after the first

Step 3: Set first node's pointer to second node

Node1[1|->] -> Node2[2|null]

Why: Link first node to second to form the chain

Step 4: Create third node with value 3 and pointer null

Node1[1|->] -> Node2[2|null]   Node3[3|null]

Why: Prepare the third node to add to the chain

Step 5: Set second node's pointer to third node

Node1[1|->] -> Node2[2|->] -> Node3[3|null]

Why: Link second node to third to complete the chain

Result:

Node1[1|->] -> Node2[2|->] -> Node3[3|null]

Annotated Code

DSA Python

class Node:
    def __init__(self, data):
        self.data = data  # store the value
        self.next = None  # pointer to next node, starts as None

# Create nodes
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

# Link nodes
node1.next = node2  # first node points to second
node2.next = node3  # second node points to third

# Function to print linked list

def print_list(head):
    current = head
    while current:
        print(current.data, end=' -> ')
        current = current.next
    print('null')

# Driver code
print_list(node1)

self.next = None # pointer to next node, starts as None

initialize pointer to null meaning no next node yet

node1.next = node2 # first node points to second

link first node to second node to form chain

node2.next = node3 # second node points to third

link second node to third node to continue chain

while current: print(current.data, end=' -> ') current = current.next

traverse nodes one by one printing data until end (null)

Output

1 -> 2 -> 3 -> null

Complexity Analysis

Time: O(n) because printing the list visits each node once

Space: O(n) because we create n nodes each holding data and pointer

vs Alternative: Compared to arrays, linked nodes use extra space for pointers but allow easy insertion without shifting elements

Edge Cases

Empty list (no nodes)

Printing shows just 'null' because head is None

DSA Python

while current:

Single node list

Prints the single node data followed by 'null'

DSA Python

while current:

When to Use This Pattern

When you need a flexible chain of elements where each points to the next, use node and pointer design to build linked lists.

Common Mistakes

Mistake: Forgetting to set the next pointer, leaving nodes unlinked
Fix: Always assign the next pointer to link nodes explicitly

Mistake: Setting next pointer to data instead of node
Fix: Ensure next points to a node object, not just the data value

Summary

It creates small containers called nodes that hold data and a pointer to the next node.

Use it when you want to build a chain of elements that can grow or shrink easily.

The key is each node points to the next, forming a linked chain like a treasure map of clues.

Practice

1. What does the next pointer in a linked list node represent?

easy

A. It points to the previous node in the list

B. It stores the data value of the node

C. It points to the next node in the list

D. It stores the size of the list

Solution

1. Step 1: Understand the role of next pointer

   The next pointer in a linked list node is used to connect the current node to the following node in the sequence.

2. Step 2: Differentiate from other node parts

   The data part stores the value, and next specifically points to the next node, not previous or size.

3. Final Answer:

   It points to the next node in the list -> Option C

4. Quick Check:

   next pointer = next node address [OK]

Hint: Remember: next always leads forward in the list [OK]

Common Mistakes:

• Confusing next with data storage
• Thinking next points backward
• Assuming next stores list size

2. Which of the following is the correct way to define a simple node class in Python with a data attribute and a next pointer?

easy

A. class Node:
def __init__(self, data):
self.data = data
self.next = None

B. class Node:
def __init__(self, data):
data = self.data
next = None

C. class Node:
def __init__(self):
self.data = None
self.next = None

D. class Node:
def __init__(self, data, next):
self.data = data
next = None

Solution

1. Step 1: Check correct attribute assignment

   class Node: def __init__(self, data): self.data = data self.next = None correctly assigns self.data = data and initializes self.next = None to indicate no next node yet.

2. Step 2: Identify errors in other options

   class Node: def __init__(self, data): data = self.data next = None assigns backwards, class Node: def __init__(self): self.data = None self.next = None misses data parameter, class Node: def __init__(self, data, next): self.data = data next = None does not assign self.next properly.

3. Final Answer:

   class Node: def __init__(self, data): self.data = data self.next = None -> Option A

4. Quick Check:

   Correct attribute setup = class Node: def __init__(self, data): self.data = data self.next = None [OK]

Hint: Use self.attribute = value inside __init__ [OK]

Common Mistakes:

• Not using self to assign attributes
• Forgetting to initialize next to None
• Swapping assignment order

3. What will be the output of the following code?

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

head = Node(10)
second = Node(20)
head.next = second
print(head.next.data)

medium

A. 20

B. Error

C. None

D. 10

Solution

1. Step 1: Understand node creation and linking

   Two nodes are created: head with data 10, second with data 20. Then, head.next points to second.

2. Step 2: Trace the print statement

   head.next.data accesses the data of the node after head, which is second, so it prints 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   head.next.data = 20 [OK]

Hint: Follow the next pointer to get next node's data [OK]

Common Mistakes:

• Printing head.data instead of head.next.data
• Confusing next pointer with data
• Expecting None because of uninitialized pointer

4. Identify the error in the following code snippet for a singly linked list node:

class Node:
    def __init__(self, data):
        self.data = data
        next = None

node1 = Node(5)
print(node1.next)

medium

A. The class name should be lowercase

B. The data attribute is missing

C. The print statement syntax is wrong

D. The next pointer is not assigned to self

Solution

1. Step 1: Check attribute assignment in __init__

   The code assigns next = None without self., so next is a local variable, not an attribute.

2. Step 2: Understand consequence on print

   Since node1.next was never set, it raises an AttributeError or prints None if accessed differently.

3. Final Answer:

   The next pointer is not assigned to self -> Option D

4. Quick Check:

   Missing self. causes attribute error [OK]

Hint: Always use self. to create object attributes [OK]

Common Mistakes:

• Forgetting self. before next
• Assuming local variable becomes attribute
• Ignoring error from missing attribute

5. You want to create a linked list with three nodes containing values 1, 2, and 3 respectively. Which code snippet correctly links the nodes?

hard

A. n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n1.next = n3
n3.next = n2
n2.next = None

B. n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n1.next = n2
n2.next = n3
n3.next = None

C. n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n1.next = None
n2.next = n1
n3.next = n2

D. n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n3.next = n2
n2.next = n1
n1.next = None

Solution

1. Step 1: Understand correct node linking order

   To create a linked list 1 -> 2 -> 3, n1.next should point to n2, and n2.next to n3. The last node n3.next should be None.

2. Step 2: Check each option's linking

   n1 = Node(1) n2 = Node(2) n3 = Node(3) n1.next = n2 n2.next = n3 n3.next = None correctly links nodes in order. The other options link nodes in wrong order or reverse.

3. Final Answer:

   n1.next = n2; n2.next = n3; n3.next = None -> Option B

4. Quick Check:

   Correct forward linking = n1 = Node(1) n2 = Node(2) n3 = Node(3) n1.next = n2 n2.next = n3 n3.next = None [OK]

Hint: Link nodes in order, last node points to None [OK]

Common Mistakes:

• Linking nodes in reverse order
• Not setting last node's next to None
• Mixing node references