Custom List Class

The Problem

You call lst.append(5) and it works. Magic. But what actually happens? The list has a fixed chunk of memory; if it runs out of room, it needs a bigger chunk — and that means copying everything over. If it shrinks, it should give memory back.

Python's list handles all of this internally. Building your own version from scratch makes every hidden allocation, resize, and shift visible. You will write a class that supports append, insert, pop, remove, __len__, __getitem__, and __contains__ — the core of what makes a list a list.

The Class Structure

A dynamic array needs three internal variables:

• _capacity — how many elements fit without reallocating
• _size — how many elements are currently stored
• _data — the raw storage (a fixed-size Python list used as a C-style array)

class CustomList:
    def __init__(self):
        self._capacity = 1
        self._size = 0
        self._data = [None] * self._capacity

    def __len__(self):
        return self._size

    def __getitem__(self, index):
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")
        return self._data[index]

    def __setitem__(self, index, value):
        if index < 0 or index >= self._size:
            raise IndexError("Index out of bounds")
        self._data[index] = value

    def __str__(self):
        items = ", ".join(str(self._data[i]) for i in range(self._size))
        return f"[{items}]"

Line-by-line:

• self._capacity = 1 — start small. The list grows as needed.
• self._size = 0 — no elements yet.
• self._data = [None] * self._capacity — allocate the raw array. [None] * 1 gives [None].
• __len__ returns _size, not len(_data). The caller sees only the used slots.
• __getitem__ and __setitem__ validate the index against _size, not _capacity. An index past the last element is an error even if the underlying array has room.
• __str__ joins only the _size elements, ignoring empty capacity slots.

Append

Appending adds an element at the next available position. If the array is full, it doubles the capacity first.

Example 1 — five appends, starting empty

Initial state: capacity = 1, size = 0, data = [None]

Resizes happen at steps 2, 3, and 5. Each resize allocates a new block and copies all existing elements. The capacity doubles each time: 1 → 2 → 4 → 8.

Example 2 — append after a fresh resize (showing the copy)

Before resize: capacity = 2, size = 2, data = [10, 20]

Resize to capacity 4:

After resize: data = [10, 20, None, None], capacity = 4, size = 2.

Then data[2] = 30.

Example 3 — append without resize

Append 40 when capacity = 4, size = 3, data = [10, 20, 30, None]:

No resize needed. data[3] = 40. Size becomes 4.

Code

def append(self, value):
    if self._size == self._capacity:
        self._resize(self._capacity * 2)
    self._data[self._size] = value
    self._size += 1

Line-by-line:

• if self._size == self._capacity — the array is full. Nothing to shift into; we need more space.
• self._resize(self._capacity * 2) — double the capacity. Doubling makes the amortized cost O(1). A fixed increment (like +10) would make it O(n).
• self._data[self._size] = value — place the new value at the first unused slot.
• self._size += 1 — increment the element count.

Code trace — appending 20 to data = [10], capacity = 1, size = 1

Resize

Resizing allocates a new, larger array, copies every element from the old array, and discards the old one.

Code

def _resize(self, new_capacity):
    new_data = [None] * new_capacity
    for i in range(self._size):
        new_data[i] = self._data[i]
    self._data = new_data
    self._capacity = new_capacity

Line-by-line:

• new_data = [None] * new_capacity — allocate the fresh block.
• for i in range(self._size) — iterate over every used slot (not every capacity slot). Unused slots hold stale None and are not worth copying.
• new_data[i] = self._data[i] — copy each element.
• self._data = new_data — replace the old array reference. The old array becomes garbage.
• self._capacity = new_capacity — update the capacity.

Code trace — resizing from capacity 4 to 8

Before: capacity = 4, size = 4, data = [10, 20, 30, 40]

After: data = [10, 20, 30, 40, None, None, None, None], capacity = 8.

This is O(n) — every element is copied. The amortized argument works because resizes are rare: log₂ n resizes for n appends.

Insert

Inserting at a position shifts every element from that position onward one slot to the right, then places the new value.

Example 4 — insert at middle

Insert 99 at index 1 in data = [10, 20, 30, None] (capacity = 4, size = 3):

Example 5 — insert at head

Insert 99 at index 0 in [10, 20, 30, None]:

Every element shifts. Worst case.

Example 6 — insert at tail

Insert 99 at index 3 (the end, same as append) in [10, 20, 30, None]:

Zero shifts. Best case.

Example 7 — insert at middle with resize

Insert 99 at index 1 in [10, 20] (capacity = 2, size = 2):

Step 1: resize to 4 → [10, 20, None, None] Step 2: shift → [10, 20, 20, None] Step 3: shift → [10, 10, 20, None] Step 4: place → [10, 99, 20, None]

The resize happens first because there is no room to shift.

Code

def insert(self, index, value):
    if index < 0 or index > self._size:
        raise IndexError("Index out of bounds")

    if self._size == self._capacity:
        self._resize(self._capacity * 2)

    for i in range(self._size, index, -1):
        self._data[i] = self._data[i - 1]

    self._data[index] = value
    self._size += 1

Line-by-line:

• if index < 0 or index > self._size — validate. index == self._size means "insert at end" (append), which is valid.
• if self._size == self._capacity — only resize before shifting. If we shift first and then resize, the shifted data might get lost.
• for i in range(self._size, index, -1) — start from the last element and walk backward to the target position. The step -1 is critical: if we iterated forward, we would overwrite the next element before reading it.
• self._data[i] = self._data[i - 1] — copy the element one slot to the right.
• self._data[index] = value — the old occupant at index was copied to index + 1 in the first loop iteration. The position is safe to overwrite.
• self._size += 1 — one more element in the list.

Code trace — insert(1, 99) in data = [10, 20, 30, 40, None], size = 4, cap = 5

No resize needed (size 4 < cap 5).

After loop: data[1] = 99. size = 5.

Pop

Pop removes and returns the element at a given index (or the last element by default), then shifts everything after it left to fill the gap.

Example 8 — pop last

Pop from data = [10, 20, 30, None] at index 2 (last element):

No shift needed.

Example 9 — pop middle

Pop from data = [10, 20, 30, 40, None] at index 1:

Example 10 — pop triggering shrink

Starting with capacity = 16, size = 4. Pop the last element:

After the pop: size = 3. capacity (16) is more than 4 × size (12). The shrink condition fires: capacity halves to 8.

The shrink prevents the array from holding on to 16 slots when only 3 are used.

Code

def pop(self, index=None):
    if self._size == 0:
        raise IndexError("Pop from empty list")

    if index is None:
        index = self._size - 1

    if index < 0 or index >= self._size:
        raise IndexError("Index out of bounds")

    value = self._data[index]

    for i in range(index, self._size - 1):
        self._data[i] = self._data[i + 1]

    self._data[self._size - 1] = None
    self._size -= 1

    if self._capacity > 4 and self._size <= self._capacity // 4:
        self._resize(self._capacity // 2)

    return value

Line-by-line:

• if self._size == 0 — nothing to remove.
• if index is None: index = self._size - 1 — default to the last element.
• value = self._data[index] — save before overwriting.
• for i in range(index, self._size - 1) — iterate from the target position to the second-to-last element. Each iteration copies the element to the left.
• self._data[i] = self._data[i + 1] — shift left.
• self._data[self._size - 1] = None — clear the orphaned last slot.
• self._size -= 1 — one less element.
• if self._capacity > 4 and self._size <= self._capacity // 4 — if the array is less than 25% full, halve the capacity. The > 4 guard prevents shrinking below a minimum size.

Code trace — pop(1) in data = [10, 20, 30, 40, None], size = 4, cap = 5

No shrink (cap 5 is not > 4).

After loop: data[3] = None (already None). size = 3. Returns 20.

Remove

Remove finds the first occurrence of a value and deletes it by shifting everything after it left.

Example 11 — remove value from middle

Remove 30 from [10, 20, 30, 40, None] (size = 4):

Example 12 — remove value at head

Remove 10 from [10, 20, 30, None] (size = 3):

Two shifts. Worst case for remove.

Example 13 — remove value not present

Remove 99 from [10, 20, 30, None]:

Code trace — remove(10) in data = [10, 20, 30, 40, None], size = 4

Find phase — scan left to right:

Shift phase — shift elements left from index 0 onward:

After shift: data[3] = None. size = 3.

Code

def remove(self, value):
    for i in range(self._size):
        if self._data[i] == value:
            for j in range(i, self._size - 1):
                self._data[j] = self._data[j + 1]
            self._data[self._size - 1] = None
            self._size -= 1
            return
    raise ValueError("Value not found")

Line-by-line:

• for i in range(self._size) — scan every element.
• if self._data[i] == value — found the first match.
• for j in range(i, self._size - 1) — shift everything after the found position left by one.
• self._data[j] = self._data[j + 1] — copy the next element into the current slot.
• self._data[self._size - 1] = None — clear the orphaned last slot.
• self._size -= 1 — one less element.
• raise ValueError("Value not found") — the scan completed without finding the value.

Clear

Code

def clear(self):
    self._size = 0

This does not free the underlying array. The capacity stays the same. If you clear and then re-fill, no reallocation is needed.

Contains

Code

def __contains__(self, value):
    for i in range(self._size):
        if self._data[i] == value:
            return True
    return False

Makes value in custom_list work. Linear scan, O(n).

Putting It Together

cl = CustomList()
cl.append(10)          # [10]
cl.append(20)          # [10, 20]
cl.insert(1, 15)       # [10, 15, 20]
cl.append(30)          # [10, 15, 20, 30]
print(cl.pop())        # 30, list is [10, 15, 20]
print(cl.pop(0))       # 10, list is [15, 20]
cl.remove(15)          # [20]
print(20 in cl)        # True
print(99 in cl)        # False
cl.clear()             # []

Closing

Building a list from scratch demystifies the operations you use every day. The append that looks magic is a size check, an occasional resize, and a single write. The insert that looks slow is a loop that shifts memory. Every operation has a concrete cost that is visible in the code. The next time you call append, you will know exactly what is happening behind the call.