DSA sheet · Linked List · Basic operations pattern

Design Linked List (Array → Linked List)

This is the very first coding video of the linked list playlist. The teacher builds a linked list out of an array, first with a loop and then with recursion. It looks like a small problem, but it teaches the three habits that every later linked list problem depends on: what a node really is (a value plus the address of the next node), why we never move head, and how a recursive call connects nodes on the way back. She also says clearly that she will solve every linked list problem both ways from now on, because good recursion skills pay off later in DP and backtracking.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run (operation table + drawings) → ⑨ complexity & remember

• Part 0 · Linked lists from scratch
• Part A · Build the list with a loop (iterative)
• Part B · Build the list with recursion
• Part C · Revision page

Part 0 · Linked lists from scratch

Why an array is not enough

An array keeps all its items side by side in memory, in one unbroken block. Because the block is unbroken, the computer can jump straight to item number i with simple maths. That is what we call indexing: arr[3] costs O(1).

A linked list does not need one unbroken block. Each item can sit anywhere in memory. So how do we find the next item? Each item also stores the address of the next item. An array slot holds only the data; a linked list item holds data + the address of the next item.

The teacher's memory picture

She gives each node a made-up memory address, to show what is really stored:

The three nodes are scattered (1001, 1003, 2004), but they are still a chain, because each one remembers where the next one is. If you hold the first node, you can reach the second, and from the second you can reach the third.

Drawing addresses every time is painful, so from now on we draw an arrow instead of an address:

[1] → [2] → [3] → None

The node class

A node is a small box with two things: val (the data) and next (the link to the next node, or None if there is no next node). We use LeetCode's class:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the data in this node
        self.next = next    # the next node, or None at the end

To make a node we just call the class: node = ListNode(5). We pass the value. We do not pass a next node, because at the moment of creating it we don't know who comes next, so next starts as None.

(The teacher's Java code writes new Node(5). Python has no new keyword; calling the class is enough.)

Head, tail and None

• Head: the first node. Tail: the last node. The tail's next is None, which means "the list ends here".
• The head is the most important node. Everything else is reachable from it. So when a problem says "return the linked list", we return only the head, and the whole chain comes with it.

Walking the list

To move from a node to the one after it, we write curr = curr.next ("go to the address stored in my next"). We repeat that until we reach None.

[1] → [2] → [3] → None
 ↑
curr          after curr = curr.next:

[1] → [2] → [3] → None
       ↑
      curr

No index access. There is no list[3]. To reach the node at position i, you must walk i steps from the head, so it costs O(i), which is O(n) in the worst case. That is the price we pay for not needing one big block of memory.

Save before you break

A node only knows its next node. If you overwrite node.next while nothing else points at the old next node, that part of the list is lost forever (you have no way to reach it). Rule: before changing a .next, save the old next in a variable if you still need it. In this problem we only write into a .next that is None, so nothing gets lost; the next page (insert in the middle) is where this rule really bites.

Recursion on lists (needed for Part B)

A recursive function calls itself on a smaller piece of the problem. For a list, "smaller piece" usually means "the rest of the list after this node" (or "the rest of the array after index i"). Every call gets its own copy of its local variables, and Python keeps the waiting calls on the call stack. When a call returns, it hands its answer to the call that is waiting just below it.

Part A · Build the list with a loop (iterative)

GFG "Array to Linked List" (the sheet calls it Design Linked List)

1The question in simple words

You are given an array, for example arr = [1, 2, 3, 4, 5]. Make a linked list holding the same values in the same order, and return its head.

arr = [1, 2, 3, 4, 5]

answer:  [1] → [2] → [3] → [4] → [5] → None
          ↑
         head  (this is what we return)

2What the constraints tell us

• Array size: 1 to 10⁵. The teacher's usual rule: going past about 10⁸ operations risks TLE (Time Limit Exceeded). One pass over 10⁵ items is 10⁵ steps, far below the limit, so a linear O(n) solution is what we aim for. (An O(n²) idea would be 10¹⁰, too slow.)
• The size is at least 1, so the array is never empty here. The teacher still writes an empty-array check first, as a habit: with no elements there can be no list, so return None.

3Intuition: a train and a coupling worker

Think of a train. The engine is the head. To add coaches, a worker walks to the last coach and hooks a new one behind it, then steps onto the new coach, ready to hook the next one.

The engine never moves. Only the worker walks. In code, the engine is head and the worker is a second variable called curr (current).

4Building the logic from the example

Step 1: the empty case

If len(arr) == 0, there is nothing to build → return None.

Step 2: the first node

The list must start with arr[0], so head = ListNode(arr[0]). Its next is None for now.

[1] → None
 ↑
head

Step 3: hooking the second node

Where does node 2 go? Into the spot that is currently None, and that spot is exactly head.next. So head.next = ListNode(2).

[1] → [2] → None
 ↑
head

For node 3 we need to stand on node 2 and write into its next. So we must move forward one node each time.

Step 4: the trap, moving head itself

The first idea is to move head forward: head = head.next. Then head.next = ListNode(3), and so on. Let's see what that does:

[1] → [2] → [3] → None
       ↑
      head      ← nobody points at [1] any more!

We can't walk backwards in a linked list, and no variable remembers node 1. If we now return head, the list we hand back is just 2 → 3. Node 1 is lost.

Fix: leave head where it is and make a second name for the same node, curr = head (the teacher calls it an alias). We move curr, never head.

[1] → None
 ↑
head
curr        (two names, one node)

Step 5: the loop

Node 1 is already made from arr[0], so the loop starts at index 1 and goes to the end. In each round:

1. curr.next = ListNode(arr[i]): make the new node and hook it behind curr.
2. curr = curr.next: the worker steps onto the new last node.

5Approach steps

1. If the array is empty, return None.
2. Make head from arr[0].
3. Set curr = head (an alias, so head stays put).
4. For each index i from 1 to the end: hook ListNode(arr[i]) to curr.next, then move curr onto it.
5. Return head.

6Code (Python)

class Solution:
    def constructLL(self, arr):
        if len(arr) == 0:              # nothing to build
            return None
        head = ListNode(arr[0])        # first node, never moved
        curr = head                    # the worker that walks
        for i in range(1, len(arr)):
            curr.next = ListNode(arr[i])   # hook a new node at the end
            curr = curr.next               # step onto it
        return head                    # the head brings the whole chain

On screen, the teacher's first run failed because she forgot the new keyword in Java. In Python that mistake can't happen; ListNode(arr[i]) already makes the object.

7Code line by line

8Dry run: arr = [1, 2, 3, 4, 5]

Three snapshots, drawn in full:

[1] → None
 ↑
head
curr

[1] → [2] → [3] → None
 ↑           ↑
head        curr

[1] → [2] → [3] → [4] → [5] → None
 ↑                       ↑
head                    curr

See how head never leaves node 1 while curr runs ahead. That's the whole trick.

9Complexity & remember

• Time O(n): one loop, one new node per array value.
• Extra space O(1): just head, curr and i. (The n nodes themselves are the answer we were asked to build, so we don't count them as extra.)

Part B · Build the list with recursion

1The question in simple words

Exactly the same task: array in, head of an equal linked list out. Only the method changes.

2What the constraints tell us

• Time is still fine: one call per element, so O(n) calls.
• Python warning (my addition): each element adds one call to the call stack, so the stack gets n calls deep. Python stops at about 1000 nested calls by default (RecursionError). With n up to 10⁵, the recursive version would crash in Python unless you raise the limit with sys.setrecursionlimit, and even then a very deep stack can crash the program. This is one more reason the iterative version is the one to submit in Python. We learn the recursive one for the thinking.

3Intuition: "make my node, let someone else build the rest"

Picture a row of helpers, one per array index. Helper i does a tiny job:

1. Make one node holding arr[i].
2. Ask helper i + 1: "build the list for everything after me and give me its head."
3. Hook what comes back onto my node's next, then give my node back to whoever asked me.

The last helper (past the end of the array) has nothing to build, so it hands back None, which becomes the tail's next.

4Building the logic, the way the teacher derives it

Turn the loop body into a function

Her rule of thumb: whatever sits inside the loop becomes the body of the recursive function, and the loop variable becomes a parameter. The loop used index i to know which value to put in the node, so the function takes (arr, i). We start it with build(arr, 0).

Inside one call

First line: head = ListNode(arr[i]). For i = 0 that is node 1.

In the loop we wrote curr.next = ListNode(arr[i]). Here, the node for the next index must be built by the next call, so we replace the right side with a call: head.next = build(arr, i + 1).

Nodes are made going down, joined coming back up

The teacher points out a surprise. As the calls go deeper, nodes 1, 2, 3, 4, 5 all get created, but none of them are connected yet. Each call is stuck on the line head.next = build(...), waiting for the answer. The links only appear when the calls start returning.

going down (nothing linked yet):

call 0: [1] → None     waiting for build(arr, 1)
call 1: [2] → None     waiting for build(arr, 2)
call 2: [3] → None     waiting for build(arr, 3)
call 3: [4] → None     waiting for build(arr, 4)
call 4: [5] → None     waiting for build(arr, 5)
call 5: i == 5 == len(arr) → stop

The base case: when to stop and what to return

If we never stop, call 4 calls build(arr, 5), and arr[5] doesn't exist. So we stop when i == len(arr).

What should that call return? Whatever it returns lands in node 5's next. Node 5 is the last node, so its next must be None. → return None.

What does each normal call return?

Call 4 now has head = [5] and has just set 5.next = None. Call 3 is waiting to set 4.next, and it needs node 5. Which variable in call 4 holds node 5? Its head. So every call ends with return head.

5Approach steps

1. Call build(arr, 0).
2. In build(arr, i): if i == len(arr), return None.
3. Make head = ListNode(arr[i]).
4. Set head.next = build(arr, i + 1) (the rest of the list).
5. Return head.

6Code (Python)

class Solution:
    def constructLL(self, arr):
        return self.build(arr, 0)

    def build(self, arr, i):
        if i == len(arr):                    # past the last element
            return None                      # becomes the tail's next
        head = ListNode(arr[i])              # this call's own node
        head.next = self.build(arr, i + 1)   # the rest, built by the next call
        return head                          # give my node to the caller

7Code line by line

8Dry run: arr = [1, 2, 3, 4, 5]

"call i" means build(arr, i).

Newest call on top (red). A call leaves the stack once it returns its head to the call below it.

Snapshots of the links:

[1]   [2]   [3]   [4]   [5]
(each one's next is None)

[1]   [2]   [3] → [4] → [5] → None
             ↑
        call 2's head

[1] → [2] → [3] → [4] → [5] → None
 ↑
head (returned)

9Complexity & which one is better

• Time O(n): one call per element. Same as the loop.
• Space O(n): the call stack holds up to n + 1 waiting calls. The loop needed only O(1) extra.

So both are O(n) time, but the iterative version wins on space, and the teacher picks it as the better solution. She still teaches recursion on every problem, because getting comfortable with it now makes DP and backtracking much easier later.

Part C · Revision page

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

s = Solution()
print(to_list(s.constructLL([1, 2, 3, 4, 5])))   # [1, 2, 3, 4, 5]
print(to_list(s.constructLL([7])))               # [7]
print(s.constructLL([]))                         # None

Based on this video: Design Linked List | iterative & recursive