Array vs Linked List — What's the Difference?

An array stores items contiguously in memory, so access by index is instant but inserting in the middle is slow; a linked list stores nodes connected by pointers, so insertion is cheap but access by position is slow.

The concept

Arrays give O(1) random access and great cache behaviour, but resizing or inserting shifts elements.

Linked lists give O(1) insert or delete at a known node and no resizing, but reaching the nth item requires walking n nodes and each node carries pointer overhead.

Memory layout

Practical examples

Array access

const a = [10, 20, 30]
a[2] // O(1)

Singly linked list node

class Node { constructor(v, next = null) { this.v = v; this.next = next } }
let head = new Node(10, new Node(20, new Node(30)))

Insert after a node

function insertAfter(node, v) { node.next = new Node(v, node.next) }

Complexity

op          array   linked list
access      O(1)    O(n)
insert mid  O(n)    O(1)*
append      O(1)*   O(1) with tail

Common mistakes

• Choosing a linked list for speed without needing mid-list inserts.
• Forgetting to handle the head when deleting.
• Leaking nodes by losing a pointer.

Key takeaways

• Array: fast index access, contiguous.
• Linked list: cheap splicing, slow search.
• Arrays win most of the time on modern hardware.

FAQ

What is a doubly linked list?

Nodes keep a pointer to both next and previous, enabling backward traversal.

Which uses less memory?

Arrays; lists add a pointer per node.