Inserting and deleting in the middle

No gaps allowed

An array's power comes from its formula: element i is at base + i × size. That formula only holds if the elements sit side by side with no gaps. So when you insert or delete anywhere except the end, the array has to restore that property by moving elements.

To insert at index i, every element from i to the end moves one place right, opening a slot. To delete at index i, every element after it moves one place left, closing the gap. Either way, the number of moves is the number of elements after the position: n − i.

*Amortized for appends, as the previous lesson showed.

This is the answer to the first half of the opening question. list.pop() removes the last element and moves nothing. list.pop(0) removes the first and moves every other element left.

Shifting in the right order

The trace above inserts 4 at index 1. The loop copies from the back: first a[4] = a[3], then a[3] = a[2], then a[2] = a[1]. Going from the front instead would copy a[1] into a[2] and destroy the old a[2] before it had moved. The same care applies to deletion in the other direction: copy from the front, so each element moves into a slot that has already been vacated.

In practice, libraries don't move elements one at a time. They call a block copy such as C's memmove, which is written to handle overlapping source and destination and copies whole cache lines with vector instructions. Shifting a few thousand integers takes a microsecond or so. That is why, for small arrays, inserting in the middle of an array is often faster than inserting into a linked list, despite the O(n): the array's moves are sequential and cheap, while finding the position in a list means chasing pointers.

Deleting without shifting

Two tricks avoid shifting when you can afford them.

Swap with the last element. If the order of elements doesn't matter, as in a set of active connections or a bag of particles in a simulation, delete index i by moving the last element into it and decrementing the size. That is the last step of the trace: one move instead of three, and O(1) whatever the size. The practice problem Insert Delete GetRandom O(1) is built around this trick, combined with a hash map that remembers where each value sits.

Mark now, compact later. Instead of removing an element, mark it as deleted, with a flag or a special value, and skip marked elements when reading. When enough have accumulated, remove all of them in one pass. Databases and garbage collectors use this, and so do hash tables, whose tombstones you met in the hash tables module.

Removing many elements in one pass

The most common mistake with arrays is removing elements one at a time in a loop. Each removal searches and shifts, so removing k elements from an array of n costs up to O(k × n), which is O(n²) when many go.

The fix is to rebuild the array in a single pass with two indexes. A read index visits every element; a write index marks where the next kept element goes:

def remove_negatives(a):
    write = 0
    for read in range(len(a)):
        if a[read] >= 0:
            a[write] = a[read]
            write += 1
    del a[write:]          # drop the leftover tail

Every element is read once and moved at most once: O(n) time and O(1) extra space, and the kept elements stay in their original order. In Python, a = [x for x in a if x >= 0] does the same with a new list. This read-and-write pattern returns in the last lesson of this module.

When the middle is the main event

If a program mostly inserts and deletes at the front, use a structure that is built for it. A deque (double-ended queue) such as Python's collections.deque or Java's ArrayDeque stores its elements in a ring buffer whose start index can move, so adding or removing at either end is O(1). The stacks and queues module builds one.

If edits happen all over a long sequence, array-based tricks still win in surprising places. Text editors face exactly this problem, and many solve it with a gap buffer: the text is one array with a block of empty slots at the cursor. Typing fills the gap, and moving the cursor moves the gap by shifting only the characters it passes. Emacs works this way. Visual Studio Code uses a piece table instead: the original file is never modified, and edits are recorded as a list of pieces pointing into the original text and into a buffer of added text. Both avoid shifting a whole file for one keystroke.

For general-purpose ordered data with frequent inserts in the middle, the answer is a balanced tree or a skip list, which later levels of this track cover. For most everyday code, though, the right move is simpler: append at the end, remove in batches, and reach for a deque when the front is busy.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Inserting and deleting in the middle from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

def insert(a, i, x):
    for k in range(a.size, i, -1):
        a[k] = a[k - 1]
    a[i] = x
    a.size += 1

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.