What is a Linked List? How does it differ from an Array?

Difficulty: 2/10

linked list fundamentals, array vs linked list, memory layout

Linked List vs Array

A Linked List is a linear data structure composed of nodes, where each node stores data and one or more references to other nodes. Unlike an array, linked-list nodes do not need to occupy contiguous memory. This makes insertion and deletion efficient when the relevant node or predecessor is already known, but random access is inefficient.

javascript

1
Array: contiguous memory and O(1) indexed access.
2
Linked List: non-contiguous nodes connected through references.
3
Array insertion/deletion in the middle is generally O(n).
4
Linked List insertion/deletion can be O(1) when the required position or node reference is already available.
5
Linked Lists have additional memory overhead for node references.
6
Arrays generally provide better cache locality.

Scenario Questions

0-2 years experience

Follow-up Questions