# The Chain Builder

> Links connect in sequence - build the chain from scratch.

Canonical URL: <https://datadriven.io/problems/the_chain_builder>

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

Implement a singly linked list via an operations list. Operations: ['insert', val] appends val to the end, ['find', val] returns True if val is in the list else False. Return a parallel list of return values: None for insert, True/False for find.

## Worked solution and explanation

### Why this problem exists in real interviews

Implementing a linked list from scratch tests **node-based data structures**, pointer manipulation, and whether you understand how insertion and search work at the reference level.

---

### Break down the requirements

#### Step 1: Define a Node class

Each node holds a value and a reference to the next node.

#### Step 2: Implement insert at the tail

Traverse to the last node and set its next pointer to the new node.

#### Step 3: Implement find by traversal

Walk the list from head to tail, comparing each node's value.

---

### The solution

**Node-based singly linked list with insert and find**

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
    def insert(self, val):
        new_node = Node(val)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = new_node
    def find(self, val):
        current = self.head
        while current is not None:
            if current.val == val:
                return True
            current = current.next
        return False
```

> **Time and Space Complexity**
>
> **Time:** Insert is O(n) for tail insertion (O(1) if you maintain a tail pointer). Find is O(n) in the worst case.
> 
> **Space:** O(n) for n nodes.

> **Interviewers Watch For**
>
> Whether you mention that maintaining a `self.tail` pointer would make insert O(1). Showing this awareness scores points even if you implement the simpler version.

> **Common Pitfall**
>
> Forgetting to handle the empty-list case in `insert`. When `self.head` is None, the new node becomes the head.

---

## Common follow-up questions

- How would you implement delete by value? _(Tests pointer manipulation: find the predecessor and update its next to skip the target node.)_
- How would you reverse the linked list? _(Tests iterative three-pointer reversal: prev, current, next.)_
- What are the tradeoffs vs. a Python list? _(Tests understanding that linked lists have O(1) insert/delete at known positions but O(n) random access, while Python lists have O(1) access but O(n) insert/delete.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_chain_builder)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.