DSA Interview Prep · Lesson

Node Class and List Construction

Define a Node dataclass, build lists by linking nodes manually, and write insert/delete/print helpers to visualise pointer changes.

Node Class and List Construction is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

What Is a Linked List?

A linked list is a sequence of nodes where each node stores a value and a pointer to the next node. Unlike arrays, nodes are scattered in memory — there is no index-based O(1) access. In exchange, you get O(1) insertion and deletion at any known position without shifting elements.

In Python we represent each node with a small class holding val and next. Chaining nodes together forms the list; the last node's next is None to signal the end.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)

# Traverse and print
curr = head
while curr:
    print(curr.val, end=' -> ')
    curr = curr.next
print('None')

Building Lists from Arrays

In interviews you will often be given a list and asked to construct its linked-list equivalent, or vice versa. The helper functions build and to_list are worth memorising: build chains nodes from an array, and to_list walks the list to collect values for easy verification.

Building a linked list from n elements takes O(n) time and O(n) space. Using a dummy head node simplifies edge cases where the first node may change.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(arr):
    dummy = ListNode(0)
    curr = dummy
    for val in arr:
        curr.next = ListNode(val)
        curr = curr.next
    return dummy.next

def to_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

head = build([1, 2, 3, 4, 5])
print(to_list(head))  # [1, 2, 3, 4, 5]

Insert at Head and Tail

Inserting a new node at the head is O(1): create the node, point its next to the old head, and return the new node as the head. Inserting at the tail requires traversing to the last node (O(n)) and then linking the new node.

Using a dummy head node eliminates the special-case of an empty list for both insertions, because dummy.next is always the real head.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def insert_head(head, val):
    return ListNode(val, head)  # O(1)

def insert_tail(head, val):
    new_node = ListNode(val)
    if not head:
        return new_node
    curr = head
    while curr.next:
        curr = curr.next
    curr.next = new_node
    return head

head = None
for v in [1, 2, 3]:
    head = insert_tail(head, v)
head = insert_head(head, 0)

curr = head
while curr:
    print(curr.val, end=' -> ')
    curr = curr.next
print('None')  # 0 -> 1 -> 2 -> 3 -> None

Delete a Node by Value

To delete the first node with a given value, maintain a prev pointer one step behind curr. When curr.val == target, set prev.next = curr.next to bypass the node. A dummy head is especially helpful here because it eliminates the special case of deleting the actual head node — prev can always start at the dummy.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def delete_val(head, target):
    dummy = ListNode(0)
    dummy.next = head
    prev, curr = dummy, head
    while curr:
        if curr.val == target:
            prev.next = curr.next
            break
        prev, curr = curr, curr.next
    return dummy.next

def to_list(h):
    r = []
    while h:
        r.append(h.val)
        h = h.next
    return r

head = None
for v in [1, 2, 3, 2, 4]:
    dummy2 = ListNode(v)
    dummy2.next = head
    head = dummy2  # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))

Visualising Pointer Changes

A common mistake is losing track of a node when updating pointers. Always save next before overwriting it: saved = curr.next, then reassign. Draw the list as boxes connected by arrows and simulate each pointer update on paper before coding. This visual approach prevents accidental null-pointer errors during interviews.

Remember: in Python, reassigning curr.next does not affect curr itself, but losing the reference to curr.next before saving it means you can no longer traverse forward.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Demonstrate safe pointer update
def swap_first_two(head):
    if not head or not head.next:
        return head
    first  = head
    second = head.next
    # Save third before losing the reference
    third  = second.next
    # Rewire
    second.next = first
    first.next  = third
    return second

from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
    print(curr.val, end=' ')
    curr = curr.next
# 2 1 3 4

Singly vs Doubly Linked Lists

A singly linked list stores only a next pointer; traversal is one-directional. A doubly linked list stores both prev and next, enabling O(1) backward traversal and O(1) deletion given a direct node reference (no need for the prev-tracking loop).

Python's collections.deque is implemented as a doubly linked list, which is why it supports O(1) appendleft and popleft. In interviews you will implement singly linked lists; doubly linked lists appear in LRU cache design.

class DLNode:
    def __init__(self, val=0):
        self.val  = val
        self.prev = None
        self.next = None

# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b

# Traverse forward
curr = a
while curr:
    print(curr.val, end=' <-> ')
    curr = curr.next
print('None')

# Traverse backward from c
curr = c
while curr:
    print(curr.val, end=' <-> ')
    curr = curr.prev
print('None')

Length, Tail, and Printing Helpers

Three utility functions you should have on hand during any linked-list interview: length(head) counts nodes in O(n), tail(head) returns the last node in O(n), and print_list(head) formats the list for debugging. Having these ready lets you focus on the core algorithm rather than re-implementing helper logic.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def length(head):
    count = 0
    while head:
        count += 1
        head = head.next
    return count

def tail(head):
    while head and head.next:
        head = head.next
    return head

def print_list(head):
    parts = []
    while head:
        parts.append(str(head.val))
        head = head.next
    print(' -> '.join(parts) + ' -> None')

# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)

Two-Pointer Setup on Linked Lists

The two-pointer technique is as important for linked lists as it is for arrays, but the pointers are linked-list nodes rather than indices. Common setups include a slow and fast pointer (fast moves 2x faster) for finding midpoints and detecting cycles, and a predecessor and current pair for deletion and reversal.

Always initialise both pointers explicitly and handle the null-termination check carefully — fast and fast.next prevents null-pointer errors when fast is near the end.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Find middle node using slow-fast pointers
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow   # for even length, returns second of two middle nodes

nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]

print(find_middle(nodes[0]).val)  # 3 (middle of 1->2->3->4->5)

The Dummy Head Pattern

The dummy head (sentinel node) pattern is one of the most useful tricks in linked-list problems. By prepending a dummy node with value 0, you never need to special-case an empty list or a change at the true head. Your result is always dummy.next. This pattern appears in merge sorted lists, remove nth from end, partition list, and many others.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Remove all nodes with val == target (may include head)
def remove_all(head, target):
    dummy = ListNode(0)
    dummy.next = head
    curr = dummy
    while curr.next:
        if curr.next.val == target:
            curr.next = curr.next.next  # skip the node
        else:
            curr = curr.next
    return dummy.next

def to_list(h):
    r = []
    while h:
        r.append(h.val)
        h = h.next
    return r

nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
    nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head))  # [1, 2, 3, 4, 5]

Time and Space Complexity

Most linked list operations have these complexities. Access by index: O(n) — must traverse from head. Insert/delete at known node: O(1) — just rewire pointers. Insert/delete at position k: O(k) — traverse first. Search: O(n) — worst case entire list. Space is O(1) for all in-place operations (excluding extra data structures).

Contrast with arrays: arrays offer O(1) access but O(n) insert/delete due to shifting. Linked lists are better when insertions and deletions at arbitrary positions are frequent.

Interview Tips for Linked Lists

Before writing any linked list code, draw the list visually with boxes and arrows. Confirm edge cases aloud: empty list, single node, even vs odd length. Use a dummy head to simplify boundary conditions. Always check if not head early. After coding, trace your solution on a three-node list to catch pointer errors before the interviewer does.

Most linked list bugs come from one of three sources: forgetting to save next before overwriting it, off-by-one in the termination condition, or not handling the head-change edge case — the dummy node eliminates the third entirely.

Quick Check

Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.

Lesson Recap

In this lesson you learned: a linked list is built from Node objects with val and next fields, the dummy head pattern eliminates head-change edge cases, and the slow-fast two-pointer setup is the foundation of midpoint finding and cycle detection. Next up we tackle reversing a linked list — one of the most commonly asked pointer problems.

Frequently asked questions

Is the “Node Class and List Construction” lesson free?

Yes — the full text of “Node Class and List Construction” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.

What will I learn in “Node Class and List Construction”?

Define a Node dataclass, build lists by linking nodes manually, and write insert/delete/print helpers to visualise pointer changes. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start DSA Interview Prep?

No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Node Class and List Construction” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this DSA Interview Prep lesson?

Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to DSA Interview Prep