Arrays and linked lists under an editing workload

Inserting beside a known linked-list node takes constant pointer work. Inserting at position 50,000 in a linked list can first require walking through 50,000 nodes. For a developer choosing a representation for an editor or ordered collection, that difference is the main qualification behind the familiar claim that linked lists have fast insertion.

Compare two precise operations. One receives a numeric index and must insert a new item before that position. The other already holds a reference to a node and inserts immediately after it. Those interfaces supply different information. A fair comparison includes the cost of obtaining whatever location the operation needs.

Follow one insertion in an array

Start with the sequence [A, B, C, D, E] and insert X at index two. An array representation moves E one position to the right, then D, then C, before storing X. Moving from the right prevents an assignment from overwriting the next value that still needs to move.

def insert_with_shift_count(values, index, item):
    if not 0 <= index <= len(values):
        raise IndexError(index)
    values.append(None)
    shifts = 0
    for position in range(len(values) - 1, index, -1):
        values[position] = values[position - 1]
        shifts += 1
    values[index] = item
    return shifts

values = ["A", "B", "C", "D", "E"]
assert insert_with_shift_count(values, 2, "X") == 3
assert values == ["A", "B", "X", "C", "D", "E"]

This instructional code counts the movement of existing elements. It does not count possible allocation work performed by Python’s append, and it is not a replacement for the built-in insert. For a list of length n, insertion at index i moves n - i existing references. Inserting at the end moves none; inserting at the front moves all of them.

A fixed-size backing array may also run out of capacity. A dynamic array then allocates a larger region and copies references. Geometric growth makes the extra cost of repeated end appends amortized O(1), but an individual resize still costs O(n). Open Data Structures’ array chapter separates these resizing costs from shifts within the array.

Follow the same edit in a linked list

For a singly linked list, suppose cursor already refers to the node containing B. Allocate a node containing X, set its successor to the old successor of B, then make B point to X. The nodes containing C, D, and E remain where they were.

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


def insert_after(cursor, value):
    node = Node(value, cursor.next)
    cursor.next = node
    return node

The order of these assignments preserves the route to the rest of the list. If you replace cursor.next before saving its old target, the suffix can become unreachable. The returned node can become the cursor for a second nearby insertion. Holding that reference is what lets a run of edits avoid repeating a search from the head.

View full-size image ↗

The diagram shows logical links, not physical memory locations. Nodes can be scattered throughout memory. A simple drawing with evenly spaced boxes should not be read as a promise that their values are adjacent in RAM.

Price the workload instead of one operation

Imagine an illustrative editor that stores 100,000 tokens, jumps to a random token index 1,000 times, and performs one insertion after each jump. An array provides each indexed jump in O(1), but its insertions can shift a large suffix. A linked list avoids those shifts once positioned, yet every jump can require a long walk. Both representations can spend Θ(n) per jump-and-insert pair under this workload.

Now change the workload. Jump to a location once, retain a cursor, and type 1,000 adjacent tokens. A linked list traverses once and performs constant pointer work for each subsequent insertion. An array may repeatedly move the same suffix. This pattern supplies an actual reason to consider a cursor-based structure.

Read behavior changes the decision again. Array iteration usually benefits from contiguous storage of its elements or references. A linked traversal loads the next pointer before it can discover the next node, and each node needs pointer storage and allocation bookkeeping. These are implementation and hardware considerations, not changes to the asymptotic bound. Python lists contain references to objects, so contiguous references do not imply that the referenced objects themselves are contiguous.

Retain the position while inserting a batch

A small trace makes the repeated-suffix cost measurable. Start with ABCDE, place the cursor after B, and insert XYZ in that order. For an array, advance the insertion index after each edit. The original suffix CDE remains to the right, so each of the three insertions moves three references. The total is nine shifts, excluding allocation and writes of the new values themselves.

For the linked representation, locate B once and move the cursor to each newly inserted node. The following fixture uses a sentinel node before A so the construction also works for an empty initial sequence. The sentinel is a structural helper, not a stored editor token.

def make_chain(values):
    sentinel = Node(None)
    tail = sentinel
    for value in values:
        tail = insert_after(tail, value)
    return sentinel


def chain_values(sentinel):
    result, node = [], sentinel.next
    while node is not None:
        result.append(node.value)
        node = node.next
    return result

array = list('ABCDE')
position, shifts = 2, 0
for item in 'XYZ':
    shifts += insert_with_shift_count(array, position, item)
    position += 1
assert array == list('ABXYZCDE') and shifts == 9

head = make_chain('ABCDE')
cursor, hops = head.next, 0
while cursor.value != 'B':
    cursor = cursor.next
    hops += 1
for item in 'XYZ':
    cursor = insert_after(cursor, item)
assert chain_values(head) == list('ABXYZCDE')
assert hops == 1 and cursor.value == 'Z'

View full-size image ↗

The search starts at A, so following A’s next link reaches B in one hop. Fixture construction and conversion back to a Python list are outside the edit count. Each linked insertion allocates one node and writes two next-link fields: the new node’s successor and the previous cursor’s successor. Nine moved array references, one search hop, three allocations and six next-link writes are different kinds of work. The trace does not claim a measured speed ratio between them.

Failing to advance the linked cursor changes the result. If every insertion stays after B, inserting X, then Y, then Z produces ABZYXCDE. The operation itself still follows its contract; the caller used the wrong cursor policy for typing a forward sequence. Keeping an array insertion index fixed would reverse the batch for the same reason.

For a batch of k adjacent insertions before an unchanged suffix of length s, this elementary array routine performs k * s shifts. A bulk operation could open a gap once and move that suffix only once. That is another interface with another implementation, not evidence that every array edit must repeat the work. The local linked edit performs constant link work per insertion after positioning, while allocation and later scans still need to be considered.

Try inserting at the beginning, at the end and into an empty sequence. Use the sentinel as the predecessor for a front insertion. Predict both the resulting order and the number of existing references moved. Then deliberately keep the cursor fixed to see which contract your editor actually needs.

Specify deletion and cursor validity too

A singly linked list cannot generally remove a known node in constant time if it lacks the predecessor reference. Removing the successor of a known node is easy. A doubly linked list stores a predecessor as well, allowing local unlinking while using more memory and requiring more pointer updates. The linked-list chapter discusses this distinction between indexed access and adjacent edits.

The editor also needs rules for retained positions. Does a cursor identify a particular token, or the gap before a token? What happens if that token is deleted? An array index can shift meaning after an insertion. A node reference can remain stable across unrelated insertions, then become invalid when that node is removed. These are observable API contracts, not details to leave to the container.

For a production text editor, gap buffers, piece tables, and tree-based sequences offer additional combinations of locality, cursor editing, and indexing. The simple array-versus-list exercise is useful because it teaches you to write the operation sequence first. Record how often you jump, scan, and edit near a retained position, then compare structures against those operations with allocation and cursor behavior included.