What is a singly linked list (singly linked list)?
A singly linked list is a data structure in which each element (node) stores:
- a value (data),
- a reference (pointer) to the next node in the list.
The last element points to None (or null), which marks the end of the list.
1. What it looks like
javascript
head → [10 | *] → [20 | *] → [30 | None]headis a pointer to the first node;- each node stores its data and the address of the next one;
Noneon the last node is a sign that the list has ended.
2. How the data is stored
Elements are not laid out sequentially in memory.
Each node is created dynamically and can be located anywhere,
and the connections between them are created through pointers (next).
Example (conditional addresses):
javascript
[10 | next=2056]
[2056]: [20 | next=3172]
[3172]: [30 | next=None]3. Basic operations
| Operation | Complexity | Description |
|---|---|---|
| Access by index | O(n) | You need to walk through all nodes up to the target one. |
| Insertion at the beginning | O(1) | Only head is reassigned. |
| Insertion at the end | O(n) | You need to reach the last node. |
| Deletion of a node | O(n) | You need to find the previous element. |
4. Advantages
- Simple implementation.
- Fast insertion and deletion at the beginning (O(1)).
- The size of the list can change dynamically.
5. Disadvantages
- Slow access to elements (O(n)).
- You cannot move backward (there are no references to previous nodes).
- Extra memory is spent on storing pointers.
6. Example in Python
python
class Node:
def __init__(self, data):
self.data = data
self.next = None
# creating the list 10 → 20 → 30
n1 = Node(10)
n2 = Node(20)
n3 = Node(30)
n1.next = n2
n2.next = n3
head = n1Summary:
A singly linked list is a dynamic data structure in which each element stores data and a reference to the next one. It is efficient for insertions and deletions, but slow for access by index.
Short Answer
Interview readyPremium
A concise answer to help you respond confidently on this topic during an interview.