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.

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]

All lessons in this course

← Back to DSA Interview Prep