What is a linked list?
A linked list is a data structure in which elements (called nodes) are stored not sequentially in memory, but connected to each other by references (pointers).
Each node knows where the next element is located, and sometimes the previous one too.
1. Node structure
A single node usually contains:
- data (value) - the value itself,
- a reference (next) - the address of the next node.
javascript
[data | reference to the next]Example (singly linked list):
javascript
head → [10 | *] → [20 | *] → [30 | None]2. Types of linked lists
| Type | Features |
|---|---|
| Singly linked | Each node stores a reference only to the next element. Movement is forward only. |
| Doubly linked | Each node stores references to the previous and next. You can move in both directions. |
| Circular | The last node (tail) points to the first (head), forming a ring. |
3. Basic operations
| Operation | Complexity | Comment |
|---|---|---|
| Access by index | O(n) | You need to walk through all nodes up to the target one. |
| Insertion/deletion (given a known node) | O(1) | Only references are changed. |
| Searching for an element | O(n) | Sequential traversal. |
4. Difference from an array
| Criterion | Array | Linked list |
|---|---|---|
| Storage | Contiguous in memory | Scattered, connected by references |
| Access by index | O(1) | O(n) |
| Insertion/deletion | Slow (O(n)) | Fast (O(1)) |
| Size | Usually fixed | Can change dynamically |
5. Use cases
Linked lists are used when:
- frequent adding and removing of elements is required;
- the data size is unknown in advance;
- memory can be fragmented (for example, in systems programming).
Summary:
A linked list is a dynamic structure where elements are connected by references rather than laid out sequentially. It is flexible, but slower than an array for random access.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.