Linked list vs array: count the search before insertion

Adding an item after E needs two link changes. Finding E may need a walk through the list first. Those are separate pieces of work, and counting only the first is how “constant-time insertion” becomes misleading.

Locate the node, then change two links#

A singly linked list stores values in nodes, each with a link to the next node. Its head identifies the first node. To reach a later position, follow those links; the list provides no array-style calculation that jumps straight to an index.

In this illustrative example, the list is A → B → C → D → E → F. Insert X after E by first setting X.next = E.next, then E.next = X. The result is A → B → C → D → E → X → F. Saving E’s old successor before replacing its link keeps F reachable.

If you only know index 4, using zero-based positions, follow four links from A to reach E. If E is already in hand, that search disappears. Predict which count changes, then switch the starting information below.

Count the walk before the splice

The list is A → B → C → D → E → F. Insert X after E. Predict which work disappears when E is already in hand.

Starting informationOnly index 4Already hold node E

Index 4: follow A → B → C → D → E (4 hops), then set X.next = F and E.next = X (2 link writes).

Enable JavaScript to change the trace. The initial worked result above remains readable.

Six singly linked nodes; counts exclude allocation and cache effects. A contiguous insertion after E shifts F once, so these counts alone do not predict speed.

The splice is O(1) link work; locating an arbitrary node is O(n) in a singly linked list. These counts exclude allocation and memory access delays. A doubly linked node also links to its predecessor, which supports backward traversal and local removal when the node is already known. Singly linked removal usually needs the predecessor too.

Compare the complete operation#

For the same six values in an array, inserting X after E shifts only F to the right, assuming spare capacity. That is one element move, whereas inserting at the front shifts all six. “Array insertion is O(n)” describes growth with the number of shifted elements; it does not mean every insertion moves the whole array. Growing an array can add a separate reallocation cost.

Iterating without edits visits n elements in either structure. Removing many items changes the accounting: repeated middle deletions from an array can shift the remaining suffix each time and cost O(n²). An array can instead filter or compact in one pass. A linked-list traversal can unlink known nodes without those shifts, provided the iterator or code maintains the needed predecessor links.

For a straight scan, contiguous element storage often has a locality advantage: a cache line can bring several adjacent elements into memory. Separately allocated nodes may require pointer-dependent memory reads. These are useful reasons to benchmark an array-backed structure first, not a proof that it wins every removal workload. Arrays of references also still follow references to access the objects themselves.

Java 21 documents LinkedList as a doubly linked List and Deque. End operations avoid an indexed search; iterator-based edits can use an already located position. This API does not hand callers its internal node objects. A deque interface also does not require linked nodes: Python’s deque uses a different layout.

Linked nodes can also implement the ends of a stack or FIFO queue, or a bucket in a chained hash table. The useful question is whether the next operation already has the node or end it needs. A structure’s name does not remove the search cost.

Repeated indexing can repeat the search#

Consider reading every position by independently asking for index 0, then 1, up to n − 1. A singly linked list that restarts at its head makes 0 + 1 + … + (n − 1) hops: n(n − 1)/2, or O(n²). For six nodes that is 15 hops. One forward traversal instead follows five links to visit the same six nodes.

Java LinkedList searches from the nearer end for indexed access. This reduces the number of links crossed, but repeatedly calling get(i) for all indices still adds up to O(n²). Use an iterator or an enhanced for-loop when you need one sequential pass.

For a small implementation that makes those pointer operations explicit, see building a linked list in Python.

An iterator’s position does not make unrelated edits safe. Java documents these iterators as fail-fast: structural changes outside their supported editing methods can trigger ConcurrentModificationException. The detection is best-effort and intended to expose bugs. It is not a concurrency guarantee or a condition to rely on for correctness.

Questions people also ask

5 QUESTIONS

▸ Is inserting into a linked list really O(1)?

The insertion is. Getting to the place you want to insert is not, and the two are almost always the same operation in practice. If you already hold a reference to the node — because you kept one, or because you are mid-traversal — then splicing in a new node is a couple of pointer writes and the size of the list does not matter. If all you have is an index or a value, you pay a walk to find it first, and that walk is O(n).

▸ When is a linked list actually the right choice?

Consider it when you can keep a node or iterator position and make frequent local edits. Node identity can remain stable while neighbouring links change, but that is not a promise of a fixed physical address in every runtime. Arrays of references can also preserve the identity of referenced objects. For indexed access or straight scans, start by evaluating an array-backed structure.

▸ Why is a linked list slower than an array if both are O(n) to scan?

It can be slower because each next-node address depends on reading the current node, and separately allocated nodes may be far apart in memory. Contiguous arrays often make sequential reads easier to prefetch. Both scans are O(n), but that does not predict elapsed time. Allocation, element layout and the actual workload still need measurement.

▸ What is the difference between a singly and a doubly linked list?

A singly linked node knows only its successor; a doubly linked node knows both neighbours. The second pointer costs memory on every node and buys two things: walking backwards, and removing a node you already hold without first finding the one before it. Java's LinkedList is doubly linked, which lets its Deque operations remove from either end without a search.

▸ Does Java's LinkedList walk from the start every time I index it?

No. Java documents traversal from whichever end is closer to the index. Middle access still takes O(n), and independently calling get(i) for every position still takes O(n²) overall. An iterator keeps its current position instead of repeating the indexed search.