DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).
Array Implementation of Lists
The simplest way to store a list, with one specific weakness — and one strength that is easy to overlook.
What an array gives you
Elements sit in contiguous memory, one after another. Because every element is the same size, the address of element i can be calculated rather than searched for:
address(i) = base_address + i × size_of_element
One multiplication and one addition — the SAME work
whether i is 0 or 999,999.
That is what O(1) random access means, and it is the
property a linked list cannot offer at any price.
Where it costs
Insert 9 at position 1 in [3, 5, 7, 8]:
before 3 5 7 8 _
shift → → → every later element moves
after 3 9 5 7 8
Insertion or deletion in the middle: O(n)
Insertion at the END (with room spare): O(1)
Insertion at the START: O(n) — worst case,
everything shifts
The trade is contiguity itself. Being packed together is exactly what makes address arithmetic possible, and exactly what makes insertion expensive — there is no gap to insert into without creating one. A linked list makes the opposite bargain: gaps everywhere, so insertion is cheap, but no arithmetic can find element i and you must walk to it.
The other cost: fixed size
A static array is allocated once. Too small and it overflows; too large and the unused space is wasted for the program's lifetime — and neither is knowable in advance for most real data.
A dynamic array solves this by allocating a bigger block when full, copying everything across, and continuing. The copy is O(n), but if the size doubles each time it happens rarely enough that the average cost per insertion stays constant.
💡 That doubling is worth understanding rather than accepting. Growing by a fixed amount — say ten slots — means a copy every ten insertions, and the copies get longer as the array grows, giving O(n) per insertion on average. Doubling makes each copy twice as rare as the array is large, and the two effects cancel: the amortised cost per insertion is O(1).
Choosing between array and linked list
Use an array when:
you index into it often → O(1) access
the size is known or stable
memory locality matters → contiguous data is
far faster to scan
Use a linked list when:
you insert and delete constantly, especially in the middle
the size varies unpredictably
you never need element i directly
Commonly confused
O(1) access and O(1) insertion. Arrays give the first, not the second.
Insertion at the end. O(1) only while spare capacity exists; the insertion that triggers a resize is O(n).
Deletion is cheaper than insertion. It is not — the same shift happens, just in the other direction.