Linked List vs Array: Memory, Access Cost, and Insert/Delete

One sequence, two memory layouts

An array is one block. You ask the allocator for room for capacity elements and get a single contiguous run of bytes. Element i lives at base + i * sizeof(T). Nothing stores "where the next element is" because the next element is always right there.

array:   [ 10 ][ 20 ][ 30 ][ 40 ][  ?  ][  ?  ]
          ^base                    ^size=4, capacity=6

A linked list is many small blocks. Each element gets its own node, allocated separately, holding the value plus a pointer to the next node. The nodes can be anywhere in the heap, in any order. The only thing keeping the sequence together is the chain of pointers, and the only entry point is head.

head ──> [10|•]──> [20|•]──> [30|•]──> [40|nullptr]
         (0x6a10)  (0x71c0)  (0x6a40)  (0x8330)   <- unrelated addresses

Two consequences fall straight out of the pictures:

1. In the array, the address of element i is computable. One multiply, one add. That is O(1) random access, and it is why a[999] costs the same as a[0].
2. In the list, the address of node i is only discoverable by starting at head and following next i times. That is O(n) access, and no amount of clever coding removes it — the information simply is not stored anywhere.

The flip side is what it costs to make room. Inserting into the middle of an array means physically moving every later element one slot over, because the layout is the ordering. Inserting into a list means allocating one node and changing two pointers; nothing else in memory moves, because position is expressed by links, not by addresses.

The contrast table (and why each row is what it is)

n is the number of elements. "Known position" means you already hold the node pointer (list) or the index (array) — no searching included.

Three rows deserve a second look, because they are where marks and bugs are lost.

"O(1) insert" is a claim about rewiring, not about arriving. A linked list inserts in constant time once you are standing at the right node. Inserting at index 5000 of a list is O(n) to walk there plus O(1) to rewire — asymptotically the same O(n) as the array's shifting. The list only truly wins when you already have the pointer: at the head, at a cursor you kept while iterating, or at the tail if you maintain one.

Deleting from a singly linked list needs the previous node, not the victim. To unlink node X you must write prev->next = X->next, and a singly linked node offers no way back. Given only a pointer to X you must re-walk from head to find its predecessor — O(n). A doubly linked list stores prev and makes this genuinely O(1), at the cost of a second pointer per node.

Per-node overhead is bigger than students expect. A list of int on a 64-bit machine spends 4 bytes on data and 8 on the pointer, and each new typically rounds up and adds bookkeeping — so 32 bytes of heap for 4 bytes of payload is normal. An array of the same 4-byte ints costs 4 bytes each. Linked lists are not the memory-efficient option; they are the don't-copy-and-don't-need-a-contiguous-block option.

The array side: index arithmetic, shifting, and growth

Here is a minimal dynamic array so the three array costs are visible in code: constant-time indexing, linear-time shifting, and the copy that happens when capacity runs out.

Things to notice:

• insert_at copies backwards, from the end towards pos. Copying forwards would overwrite each element with the one before it and smear a single value across the tail. Direction matters whenever ranges overlap.
• The loop guard in erase_at is i + 1 < size_, not i < size_ - 1. With std::size_t (unsigned), size_ - 1 when size_ == 0 wraps around to a huge number — a classic off-by-one that turns into an out-of-bounds walk. Prefer adding to the left side over subtracting from the right when the type is unsigned.
• grow doubles rather than adding a constant. Doubling makes the copies rare enough that the average push_back is O(1) (amortised): growing to n elements copies about n elements in total. Growing by +1 each time would copy about n²/2 elements overall — the difference between a fast program and a slow one.
• Allocation with new int[cap] must be released with delete[], and the destructor is the place to do it.

#include <cstddef>

class IntArray {
public:
    explicit IntArray(std::size_t capacity)
        : data_(new int[capacity]), size_(0), capacity_(capacity) {}

    ~IntArray() { delete[] data_; }          // array form: delete[]

    IntArray(const IntArray&) = delete;      // owning raw memory: no accidental
    IntArray& operator=(const IntArray&) = delete;  // shallow copies

    std::size_t size() const { return size_; }

    // O(1): the address of element i is computed, not searched for.
    int& operator[](std::size_t i) { return data_[i]; }

    // O(n): every element from pos onwards physically moves right.
    void insert_at(std::size_t pos, int value) {
        if (pos > size_) return;             // pos == size_ is legal (append)
        if (size_ == capacity_) grow();
        for (std::size_t i = size_; i > pos; --i) {
            data_[i] = data_[i - 1];         // copy BACKWARDS
        }
        data_[pos] = value;
        ++size_;
    }

    void push_back(int value) { insert_at(size_, value); }

    // O(n): close the hole by sliding the suffix left.
    void erase_at(std::size_t pos) {
        if (pos >= size_) return;
        for (std::size_t i = pos; i + 1 < size_; ++i) {
            data_[i] = data_[i + 1];
        }
        --size_;
    }

private:
    void grow() {
        std::size_t new_cap = (capacity_ == 0) ? 1 : capacity_ * 2;
        int* bigger = new int[new_cap];
        for (std::size_t i = 0; i < size_; ++i) bigger[i] = data_[i];
        delete[] data_;                      // free the old block...
        data_ = bigger;                      // ...only after copying out of it
        capacity_ = new_cap;
    }

    int* data_;
    std::size_t size_;      // elements in use
    std::size_t capacity_;  // slots allocated
};

The list side: nodes, head, tail, and the order of pointer writes

A node is a value plus a link. The list object owns head, and — because "append" is such a common operation — also a tail so push_back does not have to walk the whole chain.

The two insertion cases people mix up:

Insert at head. Point the new node at the old head first, then move head. If you do it the other way round (head = fresh; fresh->next = head;) you have made the node point at itself and leaked the entire rest of the list. Writing it as new Node(v, head_) makes the correct order impossible to get wrong.

Insert at tail. Two distinct situations: the list is empty (head and tail both become the new node) or it is not (tail_->next = fresh; tail_ = fresh;). Forgetting the empty case is the single most common linked-list bug — you either dereference a null tail_ and crash, or you set tail_ while leaving head_ null so the list looks permanently empty. Any operation that can empty or un-empty the list must keep head_ and tail_ consistent with each other.

Insert after a node is the O(1) case that justifies linked lists: one allocation, one link read, two link writes, no traversal. Note that it must also update tail_ when inserting after the last node.

Every new node's next must end up either pointing at a real node or at nullptr. A node whose next was never assigned holds garbage, and traversal will happily follow it off a cliff.

#include <cstddef>

struct Node {
    int value;
    Node* next;
    Node(int v, Node* n) : value(v), next(n) {}
};

class IntList {
public:
    IntList() : head_(nullptr), tail_(nullptr), size_(0) {}
    ~IntList() { clear(); }

    IntList(const IntList&) = delete;
    IntList& operator=(const IntList&) = delete;

    std::size_t size() const { return size_; }
    bool empty()      const { return head_ == nullptr; }
    Node* head()      const { return head_; }
    Node* tail()      const { return tail_; }

    // O(1) always.
    void push_front(int v) {
        Node* fresh = new Node(v, head_);   // link first...
        head_ = fresh;                      // ...then move head
        if (tail_ == nullptr) tail_ = fresh;  // list was empty
        ++size_;
    }

    // O(1) because we keep tail_. Without it this would be O(n).
    void push_back(int v) {
        Node* fresh = new Node(v, nullptr); // new last node terminates the list
        if (tail_ == nullptr) {
            head_ = tail_ = fresh;          // empty-list case
        } else {
            tail_->next = fresh;
            tail_ = fresh;
        }
        ++size_;
    }

    // O(1): the operation linked lists exist for.
    // p == nullptr is treated as "insert before the first element".
    void insert_after(Node* p, int v) {
        if (p == nullptr) { push_front(v); return; }
        p->next = new Node(v, p->next);     // splice in
        if (p == tail_) tail_ = p->next;    // appended at the end
        ++size_;
    }

    // O(n): there is no shortcut to the i-th node.
    Node* find(int v) const {
        for (Node* cur = head_; cur != nullptr; cur = cur->next) {
            if (cur->value == v) return cur;
        }
        return nullptr;
    }

private:
    Node* head_;
    Node* tail_;
    std::size_t size_;
};

Delete by value: previous pointer, unlink, free, fix the tail

Deletion is where the pointer discipline really shows, so do it as a fixed four-step ritual.

1. Walk with two pointers. cur is the candidate; prev trails one node behind. Stop when cur is null (not found) or cur->value matches. Because && short-circuits, cur != nullptr && cur->value != v never dereferences a null pointer — the null test must come first.
2. Unlink. If prev is null the victim is the head, so head_ = cur->next. Otherwise prev->next = cur->next. That single write is the entire "O(1) removal": nothing else moves.
3. Fix the tail. If the victim was tail_, the new tail is prev — which is correctly nullptr when the list had one element and is now empty. This is the step that gets skipped, and the symptom is nasty: tail_ becomes a dangling pointer to freed memory, and the next push_back writes through it. The list also stays properly null-terminated automatically here, because prev->next was assigned cur->next, which is nullptr when cur was last.
4. Free exactly once, and read nothing afterwards. delete cur; runs after cur->next has been copied out. Deleting first and then reading cur->next is use-after-free — it often "works" in testing, which is exactly what makes it dangerous.

The same ritual generalises to removing several nodes in one pass: cache next before deleting, and advance prev only when you keep a node (see Exercise 2). Note the honest cost: this is O(n), because finding the node dominates. Only when someone hands you prev is deletion truly constant time.

// Removes the first node whose value == v. Returns false if absent.
bool IntList::remove_first(int v) {
    Node* prev = nullptr;
    Node* cur  = head_;

    while (cur != nullptr && cur->value != v) {  // null check FIRST
        prev = cur;
        cur  = cur->next;
    }
    if (cur == nullptr) return false;            // not in the list

    if (prev == nullptr) head_ = cur->next;      // victim was the head
    else                 prev->next = cur->next; // unlink: the O(1) part

    if (cur == tail_) tail_ = prev;              // victim was the tail
                                                 // (prev == nullptr => now empty)
    delete cur;                                  // free AFTER the last read
    --size_;
    return true;
}

Ownership: every new needs one delete, and delete[] is not delete

Manual data structures are exercises in ownership. The rule to internalise: whoever allocates a node decides who is responsible for freeing it, and that responsibility must be discharged exactly once.

For a linked list, the owner is the list object, and the destructor is where the debt is paid. clear() must cache next before each delete, otherwise it reads a pointer out of a node it has already destroyed.

The array/scalar distinction is a hard rule of the language, not a style preference:

Mixing them (delete on an array, or delete[] on a single object) is undefined behaviour. It typically leaks the elements after the first, corrupts the heap's bookkeeping, or crashes on an unrelated later allocation — the bug never points at the line that caused it. The two forms are not interchangeable because new[] may store an element count that only delete[] knows how to consume.

Two more habits that prevent whole categories of pain:

• Delete the copy constructor and copy assignment (or write them properly). A class holding a raw owning pointer gets a compiler-generated copy that duplicates the pointer, not the data. Two objects then free the same memory — a double free — and modifications through one are visible through the other. = delete turns a runtime disaster into a compile error.
• Do not read a pointer after freeing what it pointed to. Any other pointer aimed at that node — a saved cursor, a stale tail_, a variable in the caller — is now dangling. Setting a pointer to nullptr after deleting is a cheap way to make later misuse crash loudly and immediately instead of quietly corrupting data. Freeing nullptr is explicitly safe, so delete p; needs no null check.

In real code you would reach for std::vector and std::list/std::forward_list, or std::unique_ptr for the nodes, and none of this bookkeeping would be yours. Writing it by hand once is how you learn what those types are doing for you.

void IntList::clear() {
    Node* cur = head_;
    while (cur != nullptr) {
        Node* nxt = cur->next;  // save the link BEFORE destroying the node
        delete cur;             // scalar new -> scalar delete
        cur = nxt;
    }
    head_ = tail_ = nullptr;    // no dangling handles left behind
    size_ = 0;
}

IntList::~IntList() { clear(); }

// The array/scalar rule, side by side:
Node* one  = new Node(7, nullptr);
int*  many = new int[16];

delete   one;    // correct
delete[] many;   // correct
// delete[] one;  // UB
// delete   many; // UB (silently "works" often enough to be a trap)

Mistakes people actually make

Almost every linked-list bug is one of these, and almost every array bug is one of the last three.

Pointer rewiring

• Reassigning `head` before linking the new node, losing the rest of the list. Build the node with its next already set.
• Ignoring the empty-list case in push_back, or the single-element case in delete. Test with 0, 1, and 2 elements — that is where the special cases live.
• Forgetting to update `tail_` after deleting the last node, leaving tail_ dangling into freed memory.
• Leaving the new last node's `next` unset after a deletion or a split, so traversal runs into garbage. Every chain must end in an explicit nullptr.
• Deleting the node, then reading `node->next`. Save the link first.
• Losing the only pointer to a node before freeing it (e.g. cur = cur->next; on a node you meant to remove) — an immediate, unrecoverable leak.
• Comparing values when you meant nodes, or writing if (cur->next->value == v) without first checking cur->next != nullptr.

Ownership

• Double free via an accidental shallow copy — pass containers by reference, or delete the copy operations.
• `delete` vs `delete[]` mismatch.
• Freeing a node that another part of the program still points at. Decide who owns each node, and keep to it.
• Non-null but garbage: an uninitialised Node* p; is not nullptr. Initialise every pointer at declaration.

Array and buffer

• Off-by-one on the last index: valid indices are 0 .. size-1; a[size] is out of bounds. In erase_at, prefer i + 1 < size over i < size - 1 so an empty container cannot underflow an unsigned type.
• Shifting in the wrong direction: insert copies from the back forwards; erase copies from the front backwards.
• Circular-buffer full-vs-empty ambiguity: with only head and tail indices, head == tail means both "empty" and "full". Resolve it by storing a count (used in Exercise 3) or by deliberately leaving one slot unused. And wrap with if (i == capacity) i = 0; or %, never by letting the index run past the end.
• Holding a pointer or reference into an array across a resize. After grow() reallocates, every old pointer into the buffer is dangling — the same hazard as std::vector iterator invalidation.

Which one should you reach for?

Choose an array (or std::vector) by default. It wins on indexing, on binary search, on memory per element, and — for anything you scan repeatedly — on raw speed, because contiguous memory is what caches and prefetchers are built for. Chasing pointers across the heap can cost a cache miss per node, and a miss is worth roughly a hundred arithmetic operations. This is why a std::vector frequently beats a std::list even on workloads with mid-sequence insertions: shifting a few thousand contiguous bytes is often cheaper than one scattered allocation plus the misses that follow it.

Choose a linked list when the specific things it is good at are the things you do:

• You constantly insert or remove at the front (stacks, queues, LRU eviction).
• You are already holding a cursor at the point of modification while iterating, and you modify a lot.
• Existing pointers or references to elements must stay valid across insertions and deletions — an array's reallocation invalidates them all, whereas a list node never moves.
• You need to splice whole runs between sequences in constant time.
• You cannot afford a large contiguous block, or cannot tolerate the latency spike of an O(n) copy at an unpredictable moment (a concern in real-time systems).

The honest summary for an essay answer: arrays trade flexible structure for computed addresses; linked lists trade computed addresses for flexible structure. The array pays at modification time by moving data; the list pays at access time by walking links and at storage time by carrying a pointer per element. Neither is "faster" — they charge you in different currencies, and the right choice is whichever currency your program spends least.

Exercises with solutions

Work through each question before opening the solution below it.

bool IntList::insert_at(std::size_t pos, int v) {
    if (pos > size_) return false;        // pos == size_ IS valid (append)
    if (pos == 0)     { push_front(v); return true; }   // fixes head_
    if (pos == size_) { push_back(v);  return true; }   // fixes tail_

    Node* prev = head_;                   // prev is at index 0
    for (std::size_t step = 1; step < pos; ++step) {
        prev = prev->next;                // ends at index pos - 1
    }
    prev->next = new Node(v, prev->next); // splice: 2 pointer writes
    ++size_;
    return true;
}

std::size_t IntList::remove_all(int v) {
    std::size_t removed = 0;
    Node* prev = nullptr;
    Node* cur  = head_;

    while (cur != nullptr) {
        Node* nxt = cur->next;              // save the link BEFORE any delete
        if (cur->value == v) {
            if (prev == nullptr) head_ = nxt;      // removing the head
            else                 prev->next = nxt; // unlink
            if (cur == tail_) tail_ = prev;        // removing the tail
            delete cur;
            --size_;
            ++removed;
            // prev deliberately NOT advanced: it must keep trailing a *live* node
        } else {
            prev = cur;                     // advance prev only on survivors
        }
        cur = nxt;
    }
    return removed;
}

#include <cstddef>

class RingBuffer {
public:
    explicit RingBuffer(std::size_t capacity)
        : data_(new int[capacity]), capacity_(capacity), head_(0), count_(0) {}
    ~RingBuffer() { delete[] data_; }          // array form

    RingBuffer(const RingBuffer&) = delete;    // owning raw memory
    RingBuffer& operator=(const RingBuffer&) = delete;

    bool empty() const { return count_ == 0; }
    bool full()  const { return count_ == capacity_; }
    std::size_t size() const { return count_; }

    bool push(int v) {
        if (full()) return false;
        std::size_t tail = head_ + count_;      // one past the last element
        if (tail >= capacity_) tail -= capacity_;  // wrap
        data_[tail] = v;
        ++count_;
        return true;
    }

    bool pop(int& out) {
        if (empty()) return false;
        out = data_[head_];
        ++head_;
        if (head_ == capacity_) head_ = 0;      // wrap
        --count_;
        return true;
    }

private:
    int* data_;
    std::size_t capacity_;
    std::size_t head_;   // index of the front element
    std::size_t count_;  // number of elements in use
};

Related pages