Unrolled lists: link small blocks instead of single items

An unrolled linked list stores several logical items in each linked node. The link count falls because one pointer can serve a block, while insertion within a located block still shifts a bounded number of items in its local array. This implementation has a head, tail, total length, and a configurable maximum block size. Inserting into an overflowing block splits its items into two consecutive nodes; deletion unlinks an empty block and merges adjacent blocks when their combined items fit. It allows underfilled blocks, so it does not promise a minimum occupancy or a particular memory-density bound. Every item belongs to exactly one reachable block, no reachable block is empty, and the tail must be the last reachable node after a split, merge, or unlink.

Operational case

An incident queue contains alert-47, alert-19, alert-61, and alert-83. The operator inserts alert-29 at logical position two, then removes the former alert-19 entry. Both changes can split or merge short blocks without shifting the whole logical sequence. The resulting order is alert-47, alert-29, alert-61, alert-83. A caller who already holds a direct block reference can edit locally, but this API receives numeric positions; it must follow block links from the head to locate them. That distinction is why the lesson does not label indexed insertion as constant time.

Working Python program

class IncidentBlock:
    def __init__(self, items, next_block=None):
        self.items = items
        self.next = next_block


class UnrolledIncidentList:
    def __init__(self, block_capacity=4):
        if block_capacity < 2:
            raise ValueError("block capacity must be at least two")
        self.capacity = block_capacity
        self.head = None
        self.tail = None
        self.length = 0

    def __len__(self):
        return self.length

    def _locate(self, index):
        previous = None
        block = self.head
        remaining = index
        while block is not None:
            if remaining < len(block.items):
                return previous, block, remaining
            remaining -= len(block.items)
            previous, block = block, block.next
        raise IndexError("index outside incident list")

    def append(self, incident_id):
        if self.tail is None or len(self.tail.items) == self.capacity:
            block = IncidentBlock([])
            if self.tail is None:
                self.head = block
            else:
                self.tail.next = block
            self.tail = block
        self.tail.items.append(incident_id)
        self.length += 1

    def insert(self, index, incident_id):
        if not 0 <= index <= self.length:
            raise IndexError("insert outside incident list")
        if index == self.length:
            self.append(incident_id)
            return
        _, block, offset = self._locate(index)
        block.items.insert(offset, incident_id)
        self.length += 1
        if len(block.items) > self.capacity:
            middle = len(block.items) // 2
            following = IncidentBlock(block.items[middle:], block.next)
            block.items = block.items[:middle]
            block.next = following
            if self.tail is block:
                self.tail = following

    def delete(self, index):
        if not 0 <= index < self.length:
            raise IndexError("delete outside incident list")
        previous, block, offset = self._locate(index)
        removed = block.items.pop(offset)
        self.length -= 1
        if not block.items:
            if previous is None:
                self.head = block.next
            else:
                previous.next = block.next
            if self.tail is block:
                self.tail = previous
        elif block.next and len(block.items) + len(block.next.items) <= self.capacity:
            following = block.next
            block.items.extend(following.items)
            block.next = following.next
            if self.tail is following:
                self.tail = block
        return removed

    def at(self, index):
        if not 0 <= index < self.length:
            raise IndexError("index outside incident list")
        _, block, offset = self._locate(index)
        return block.items[offset]

    def values(self):
        result = []
        block = self.head
        while block is not None:
            result.extend(block.items)
            block = block.next
        return result


log = UnrolledIncidentList(block_capacity=3)
for incident in ("alert-47", "alert-19", "alert-61", "alert-83"):
    log.append(incident)
log.insert(2, "alert-29")
log.delete(1)
print("order=", log.values(), " third=", log.at(2), sep="")

Output

order=['alert-47', 'alert-29', 'alert-61', 'alert-83'] third=alert-61

Time, space, and tradeoff

Let B be the number of blocks and C the configured block capacity. Locating an arbitrary index scans up to B links; a local insertion, deletion, split, or merge can move O(C) items, so indexed edits cost O(B + C) time. Indexed reads cost O(B). Tail append is O(1) amortized with an O(C) allocation or Python-list growth at a block boundary. Traversal costs O(N) for N items, and storage is O(N + B) for item references and block links. Python's object allocation can outweigh theoretical cache benefits; this is a logical block model, not a measured low-level memory-layout claim.

Common Mistakes

Do not forget to update tail when splitting or deleting the last block.
Do not leave an empty block reachable after deletion.
Do not call indexed access constant time merely because each block is small.
Do not promise minimum occupancy when the implementation only merges blocks that fit.

Connected lessons

Compare its edit and lookup costs with Gap buffers: pay when the edit cursor crosses text, Ropes: share text chunks across immutable revisions, Segmented arrays: locate blocks through cumulative lengths, then run the sequence audit and contract quiz.