~/blog
Linked List Input and Length

Jun 2, 2026•11 min read•By Mohammed Vasim
dsapythondata-structuresalgorithmsproblem-solving
The Problem

You have a sequence of values — integers from stdin, items from a list, rows from a file. You need to turn them into a linked list. And once you have the list, you need to know how many nodes it has.
Two operations in one post because they are the foundation for everything else in this section. You cannot test insert without first building a list, and you cannot verify insert without measuring length.
Taking Input

Two strategies for building a list from input values. The difference is whether you insert at the tail (preserving order) or at the head (reversing it).
Example 1 — tail insertion preserves order.
Input values: [10, 20, 30, 40]
text
Start:  head = None,  tail = None

Step 1 (val=10):
  head → [10 | None]
  tail → [10 | None]

Step 2 (val=20):
  head → [10 | →] [20 | None]
  tail → [20 | None]

Step 3 (val=30):
  head → [10 | →] [20 | →] [30 | None]
  tail → [30 | None]

Step 4 (val=40):
  head → [10 | →] [20 | →] [30 | →] [40 | None]
  tail → [40 | None]
```text

Each new node attaches to `tail.next`, then `tail` advances. The head stays the same after step 1. The input order `10, 20, 30, 40` is preserved in the list.

**Example 2 — head insertion reverses order.**

Same input, but each new node goes to the front:

```text
Start:  head = None

Step 1 (val=10):
  head → [10 | None]

Step 2 (val=20):
  head → [20 | →] [10 | None]

Step 3 (val=30):
  head → [30 | →] [20 | →] [10 | None]

Step 4 (val=40):
  head → [40 | →] [30 | →] [20 | →] [10 | None]
```text

The list is `40 → 30 → 20 → 10`. Reversed. Useful when order does not matter or when you specifically want the reverse.

**Example 3 — empty input.**

No values provided. The loop over the input never runs. `head` remains `None`.

This is a valid empty list. Every operation in this section must handle `head is None` without crashing.

### Code: Tail Insertion

```textpython
def take_input(values: list) -> Node:
    head = None
    tail = None

    for val in values:
        new_node = Node(val)
        if head is None:
            head = new_node
            tail = new_node
        else:
            tail.next = new_node
            tail = new_node

    return head
```text

Line by line:

- `head = None; tail = None` — the list starts empty. Both pointers are `None`.
- `for val in values` — iterate over the input sequence. This could be a list, a generator, or parsed stdin tokens.
- `new_node = Node(val)` — create a new stand-alone node. Its `.next` is `None`.
- `if head is None` — this is the first node ever. Both `head` and `tail` must point to it because there is only one node so far.
- `head = new_node; tail = new_node` — set both pointers. Without setting `tail` here, the first node would not be reachable from `tail` on subsequent iterations.
- `else: tail.next = new_node` — attach the new node after the current last node.
- `tail = new_node` — advance `tail`. Without this, every subsequent node would overwrite `tail.next` of the same node, and only two nodes would ever exist.

**Edge case — empty list.** The loop body never executes. `head` remains `None`. Any caller that expects a valid `Node` must check for `None`.

**Edge case — single value.** The `if` branch runs. Both `head` and `tail` point to the same node. If a subsequent function tries to advance `tail` before checking, it will reach `None` immediately — which is correct.

### Code Trace — `take_input([10, 20, 30, 40])`

Let us build the list step by step. Start with empty pointers, then for each value: create a node, attach it, advance the tail.

| Iteration | val | Action | head | tail | List state |
|---|---|---|---|---|---|
| 1 | 10 | head=tail=new_node(10) | → 10 | → 10 | [10\|→] |
| 2 | 20 | tail.next=new_node(20), tail=20 | → 10 | → 20 | [10\|→][20\|→] |
| 3 | 30 | tail.next=new_node(30), tail=30 | → 10 | → 30 | [10\|→][20\|→][30\|→] |
| 4 | 40 | tail.next=new_node(40), tail=40 | → 10 | → 40 | [10\|→][20\|→][30\|→][40\|None] |

After the loop, `head` points to `10 → 20 → 30 → 40 → None`. `tail` points to `40`.

**Time:** O(n) — one node created and one pointer set per element. **Space:** O(n) — n new nodes allocated.

Let us visualise each iteration:

<svg role="img" aria-label="take_input iteration 1: val=10, new_node created, head and tail both point to node with data=10, next points to None" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 300 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="50" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="100" y="45">10</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="100" y="62">node1</text>
  <path d="M 145 40 L 175 40" marker-end="url(#arrow5)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="185" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="225" y="45">None</text>
  <path d="M 60 70 L 60 85" stroke="#3b82f6" stroke-width="2"></path>
  <polygon fill="#3b82f6" points="60,90 55,80 65,80"></polygon>
  <text fill="#3b82f6" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="60" y="98">head</text>
  <path d="M 100 70 L 100 85" stroke="#22c55e" stroke-width="2"></path>
  <polygon fill="#22c55e" points="100,90 95,80 105,80"></polygon>
  <text fill="#22c55e" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="100" y="98">tail</text>
  <defs><marker id="arrow5" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="take_input iteration 2: val=20, tail.next=new_node(20), tail advances to node2. List is 10→20" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 400 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/2000/svg">
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="70" y="62">node1</text>
  <path d="M 115 40 L 145 40" marker-end="url(#arrow6)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="205" y="62">node2</text>
  <path d="M 250 40 L 280 40" marker-end="url(#arrow6)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="290" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="330" y="45">None</text>
  <path d="M 30 70 L 30 85" stroke="#3b82f6" stroke-width="2"></path>
  <polygon fill="#3b82f6" points="30,90 25,80 35,80"></polygon>
  <text fill="#3b82f6" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="30" y="98">head</text>
  <path d="M 165 70 L 165 85" stroke="#22c55e" stroke-width="2"></path>
  <polygon fill="#22c55e" points="165,90 160,80 170,80"></polygon>
  <text fill="#22c55e" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="165" y="98">tail</text>
  <defs><marker id="arrow6" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="take_input iteration 3: val=30, tail.next=new_node(30), tail advances to node3. List is 10→20→30" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 500 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="70" y="62">node1</text>
  <path d="M 115 40 L 145 40" marker-end="url(#arrow7)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dbeafe" rx="6" stroke="#3b82f6" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="205" y="62">node2</text>
  <path d="M 250 40 L 280 40" marker-end="url(#arrow7)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="340" y="45">30</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="340" y="62">node3</text>
  <path d="M 385 40 L 415 40" marker-end="url(#arrow7)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="425" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="465" y="45">None</text>
  <path d="M 30 70 L 30 85" stroke="#3b82f6" stroke-width="2"></path>
  <polygon fill="#3b82f6" points="30,90 25,80 35,80"></polygon>
  <text fill="#3b82f6" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="30" y="98">head</text>
  <path d="M 300 70 L 300 85" stroke="#22c55e" stroke-width="2"></path>
  <polygon fill="#22c55e" points="300,90 295,80 305,80"></polygon>
  <text fill="#22c55e" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="300" y="98">tail</text>
  <defs><marker id="arrow7" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="take_input iteration 4: val=40, tail.next=new_node(40), tail advances to node4. List is 10→20→30→40. Done." style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="70" y="62">node1</text>
  <path d="M 115 40 L 145 40" marker-end="url(#arrow8)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="205" y="62">node2</text>
  <path d="M 250 40 L 280 40" marker-end="url(#arrow8)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="340" y="45">30</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="340" y="62">node3</text>
  <path d="M 385 40 L 415 40" marker-end="url(#arrow8)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#dcfce7" rx="6" stroke="#22c55e" stroke-width="1.5" x="425" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="475" y="45">40</text>
  <text fill="#64748b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="475" y="62">node4</text>
  <path d="M 520 40 L 550 40" marker-end="url(#arrow8)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="560" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="595" y="45">None</text>
  <path d="M 30 70 L 30 85" stroke="#3b82f6" stroke-width="2"></path>
  <polygon fill="#3b82f6" points="30,90 25,80 35,80"></polygon>
  <text fill="#3b82f6" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="30" y="98">head</text>
  <path d="M 435 70 L 435 85" stroke="#22c55e" stroke-width="2"></path>
  <polygon fill="#22c55e" points="435,90 430,80 440,80"></polygon>
  <text fill="#22c55e" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="435" y="98">tail</text>
  <defs><marker id="arrow8" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

## Finding Length

Length requires a full traversal. There is no shortcut — a linked list does not know its own size unless you explicitly maintain a counter.

**Example 4 — counting nodes in an empty list.**

```text
head → None
count = 0
```text

The traversal loop does not run. Returns 0.

**Example 5 — counting nodes in a 4-element list.**

```text
head → [10 | →] [20 | →] [30 | →] [40 | None]
```text

| Step | current (before) | action | count (after) | current (after) |
|---|---|---|---|---|
| 1 | node(10) | count += 1 → 1 | 1 | node(20) |
| 2 | node(20) | count += 1 → 2 | 2 | node(30) |
| 3 | node(30) | count += 1 → 3 | 3 | node(40) |
| 4 | node(40) | count += 1 → 4 | 4 | None |

`current` is `None`. Loop exits. Returns 4.

Let us visualise each step of the length walk:

<svg role="img" aria-label="length Step 1: current=node(10), count becomes 1, current advances to node(20)" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <path d="M 115 40 L 145 40" marker-end="url(#larrow1)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <path d="M 250 40 L 280 40" marker-end="url(#larrow1)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="290" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="330" y="45">30</text>
  <path d="M 365 40 L 395 40" marker-end="url(#larrow1)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="405" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="445" y="45">40</text>
  <path d="M 480 40 L 510 40" marker-end="url(#larrow1)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="520" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="560" y="45">None</text>
  <path d="M 30 70 L 30 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="30,90 25,80 35,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="30" y="98">current</text>
  <text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="14" text-anchor="middle" x="70" y="85">count=1</text>
  <defs><marker id="larrow1" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="length Step 2: current=node(20), count becomes 2, current advances to node(30)" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/2000/svg">
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <path d="M 115 40 L 145 40" marker-end="url(#larrow2)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <path d="M 250 40 L 280 40" marker-end="url(#larrow2)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="330" y="45">30</text>
  <path d="M 365 40 L 395 40" marker-end="url(#larrow2)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="405" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="445" y="45">40</text>
  <path d="M 480 40 L 510 40" marker-end="url(#larrow2)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="520" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="560" y="45">None</text>
  <path d="M 165 70 L 165 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="165,90 160,80 170,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="165" y="98">current</text>
  <text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="14" text-anchor="middle" x="205" y="85">count=2</text>
  <defs><marker id="larrow2" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="length Step 3: current=node(30), count becomes 3, current advances to node(40)" style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <path d="M 115 40 L 145 40" marker-end="url(#larrow3)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <path d="M 250 40 L 280 40" marker-end="url(#larrow3)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="330" y="45">30</text>
  <path d="M 365 40 L 395 40" marker-end="url(#larrow3)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="405" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="445" y="45">40</text>
  <path d="M 480 40 L 510 40" marker-end="url(#larrow3)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="520" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="560" y="45">None</text>
  <path d="M 300 70 L 300 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="300,90 295,80 305,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="300" y="98">current</text>
  <text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="14" text-anchor="middle" x="330" y="85">count=3</text>
  <defs><marker id="larrow3" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

<svg role="img" aria-label="length Step 4: current=node(40), count becomes 4, current advances to None. Loop exits." style="display: block; margin: 1em auto; font-family: ui-sans-serif, sans-serif;" viewBox="0 0 600 100" xmlns="http://www.w3.org/2000/svg" width="100%" xmlns:xlink="http://www.w3.org/1999/xlink">
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="20" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="70" y="45">10</text>
  <path d="M 115 40 L 145 40" marker-end="url(#larrow4)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="155" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="205" y="45">20</text>
  <path d="M 250 40 L 280 40" marker-end="url(#larrow4)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#e2e8f0" stroke-width="1.5" x="290" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="330" y="45">30</text>
  <path d="M 365 40 L 395 40" marker-end="url(#larrow4)" stroke="#3b82f6" stroke-width="1.5"></path>
  <rect fill="#fef3c7" rx="6" stroke="#f59e0b" stroke-width="1.5" x="405" y="25"></rect>
  <text fill="#334155" font-family="ui-monospace,monospace" font-size="16" font-weight="600" text-anchor="middle" x="445" y="45">40</text>
  <path d="M 480 40 L 510 40" marker-end="url(#larrow4)" stroke="#94a3b8" stroke-width="1.5"></path>
  <rect fill="#f1f5f9" rx="6" stroke="#94a3b8" stroke-width="1" x="520" y="25"></rect>
  <text fill="#94a3b8" font-family="ui-monospace,monospace" font-size="14" text-anchor="middle" x="560" y="45">None</text>
  <path d="M 415 70 L 415 85" stroke="#f59e0b" stroke-width="2"></path>
  <polygon fill="#f59e0b" points="415,90 410,80 420,80"></polygon>
  <text fill="#f59e0b" font-family="ui-sans-serif,sans-serif" font-size="12" text-anchor="middle" x="415" y="98">current</text>
  <text fill="#334155" font-family="ui-sans-serif,sans-serif" font-size="14" text-anchor="middle" x="445" y="85">count=4</text>
  <defs><marker id="larrow4" markerheight="6" markerunits="stroke-width" markerwidth="6" orient="auto" refx="6" refy="3"><path d="M0,0 L6,3 L0,6" fill="none"></path></marker></defs>
</svg>

### Code

```textpython
def length(head: Node) -> int:
    count = 0
    current = head
    while current:
        count += 1
        current = current.next
    return count
```text

Line by line:

- `count = 0` — no nodes counted yet.
- `current = head` — start at the first node. If `head` is `None`, the loop never runs.
- `while current:` — keep going until `current` becomes `None`. This is the only way to know the list has ended.
- `count += 1` — one more node visited.
- `current = current.next` — advance to the next node. If this was the last node, `current.next` is `None`, which terminates the next loop check.

**Edge case — empty list.** Returns 0. A consuming function that calls `length` before indexing into the list will get 0 and can avoid out-of-bounds errors.
**Edge case — single node.** Returns 1.
**Edge case — cycle.** If the list has a cycle, this function never terminates. Floyd's cycle detection (in the advanced section) can detect the cycle before counting.

**Time:** O(n) — every node visited once. **Space:** O(1) — a single integer regardless of list size.

### Recursive Length

The recursive version makes the self-similar structure explicit:

```textpython
def length_recursive(head: Node) -> int:
    if head is None:
        return 0
    return 1 + length_recursive(head.next)
```text

`1` for the current node, plus the length of the rest. The base case returns 0 for an empty list.

**Time:** O(n). **Space:** O(n) for the call stack — each recursive call adds a frame. For a 1000-node list, this means 1000 frames. The iterative version uses O(1) space and is the safer choice.

## Usage

```textpython
head = take_input([10, 20, 30, 40, 50])
print(length(head))    # 5
print(length_recursive(head))  # 5
```text

This pattern — build a list, perform an operation, verify — is how every subsequent post in this section works.



→ [LeetCode 707: Design Linked List](https://leetcode.com/problems/design-linked-list/) tests both input construction and length as part of the full implementation.
Linked List Input and Length

The Problem

Taking Input

Comments (0)

Leave a comment
