Linked List in Python
Subject: Data Structures and Algorithms · Language: Python · Level: intermediate · 8 min read
Build linked list logic in Python using Node class, head reference, traversal, insertion, deletion, searching, and reference handling.
A linked list is a data structure made of nodes. Each node stores data and a reference to the next node. Unlike a Python list, elements are not accessed directly by index. We start from the head and move node by node.
The first node is called the head. If the head is `None`, the linked list is empty. The head is important because it is the entry point to the whole list. If the head reference is lost, the list cannot be reached.
Insertion in a linked list means changing references. To insert at the beginning, the new node should point to the old head, and then head should move to the new node. The order of these steps matters.
Deletion also works by changing references. To delete a node, we connect the previous node to the node after the deleted node. Unlike arrays, we do not shift all later values one position left.
Traversal means visiting nodes one by one. We use a temporary reference like `current` and move it using `current = current.next`. This prevents losing the original head reference.
Linked lists are important because they teach reference-based thinking. This thinking is needed later in trees, graphs, stacks, queues, and many custom data structures. Drawing nodes on paper helps students understand the links clearly.
A linked list is a linear data structure made of nodes. Each node stores two things: the actual data and a reference to the next node.
A normal list in Python stores elements in an index-based sequence. A linked list stores elements as connected nodes. The connection between nodes is made using references.
Why Linked List Is Needed
A Python list already gives dynamic size, indexing, append, and many useful methods. Still, linked lists are taught in DSA because they explain a different way to organize memory and relationships between values.
In an array or Python list, elements are accessed using indexes. In a linked list, we usually start from the first node and move one node at a time.
This makes linked lists useful for learning insertion, deletion, references, and pointer-style thinking without using actual pointers like C or C++.
Array/List vs Linked List
A Python list allows direct access by index, such as `arr[3]`. A linked list does not allow direct index access in the same way.
To reach the fourth node in a linked list, we start from the head and move through the first, second, and third nodes before reaching the fourth.
The advantage of a linked list is that insertion and deletion can be efficient when the correct node reference is already available. The disadvantage is that searching and index-style access require traversal.
What Is a Node?
A node is the basic building block of a linked list. It stores data and a reference to the next node.
In Python, we usually create a `Node` class for this.
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
```
Here, `data` stores the value, and `next` stores the reference to the next node.
If `next` is `None`, it means there is no node after the current node.
Understanding None
In Python, `None` means no value or no object reference. In linked lists, `None` is used to mark the end of the list.
The last node's `next` is `None` because there is no next node after it.
Head Reference
`head` is a reference to the first node of the linked list. Traversal always starts from the head.
If `head` is `None`, the linked list is empty.
The head is very important. If we lose the head reference, we lose access to the entire linked list.
```python
head = Node(10)
```
This creates the first node and stores its reference in `head`.
Connecting Nodes
Nodes are connected by assigning the `next` reference.
```python
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
```
Here, the first node stores 10, the second stores 20, and the third stores 30. The first node points to the second node, and the second node points to the third node.
The structure looks like this:
```text
10 -> 20 -> 30 -> None
```
Traversal
Traversal means visiting each node one by one from the head to the end of the list.
We use a temporary variable, commonly named `current`, so that the original `head` is not changed.
```python
current = head
while current is not None:
print(current.data)
current = current.next
```
Sample Output for a list `10 -> 20 -> 30`
```text
10
20
30
```
The line `current = current.next` moves from the current node to the next node.
When `current` becomes `None`, traversal stops because the list has ended.
Why We Use current Instead of head
If we move `head` directly during traversal, the original first-node reference will be lost.
That is why we copy `head` into `current` and move `current`. This keeps `head` safe.
This is one of the most important habits in linked list problems.
Inserting at the Beginning
To insert a node at the beginning, create a new node, point it to the current head, and then update head.
```python
new_node = Node(5)
new_node.next = head
head = new_node
```
This operation is fast because we do not need to traverse the whole list.
If the old list was `10 -> 20 -> 30 -> None`, after insertion it becomes `5 -> 10 -> 20 -> 30 -> None`.
Inserting at the End
To insert at the end, move from head until the last node. The last node is the node whose `next` is `None`.
```python
current = head
while current.next is not None:
current = current.next
current.next = Node(40)
```
After this, the new node is connected after the last node.
If the list is empty, insertion at the end should make the new node the head.
Inserting After a Given Node
Sometimes we need to insert a new node after a specific node.
```python
new_node = Node(25)
new_node.next = current.next
current.next = new_node
```
The order of these two steps matters. First connect the new node to the next part of the list, then connect the current node to the new node.
If the order is wrong, part of the list may become disconnected.
Deleting the First Node
To delete the first node, move head to the next node.
```python
head = head.next
```
The old first node is skipped. Python's memory management can clean it up later if there are no references to it.
Deleting a Middle Node
To delete a middle node, find the node before it and connect that previous node to the node after the deleted node.
```python
previous.next = previous.next.next
```
This skips one node from the chain.
Unlike arrays, linked list deletion does not shift all later elements. The main work is changing references correctly.
Searching in a Linked List
Searching means checking whether a value exists in any node.
```python
current = head
found = False
while current is not None:
if current.data == target:
found = True
break
current = current.next
```
In the worst case, we may need to visit every node, so searching takes O(n) time.
Common Linked List Operations
- Traversal: visit every node one by one
- Insertion: add a node at the beginning, end, or middle
- Deletion: remove a node by changing references
- Searching: check whether a value exists
- Reversal: change links so the list direction becomes opposite
- Counting: count how many nodes are present
Most linked list problems are about carefully changing references. A small reference mistake can disconnect the list, create a cycle, or skip nodes accidentally.
Time Complexity
Traversal takes O(n) because every node may be visited once. Searching also takes O(n). Insertion at the beginning takes O(1). Insertion at the end takes O(n) if we do not maintain a tail reference.
If we maintain both `head` and `tail`, insertion at the end can become O(1), but beginners should first understand the basic traversal method.
Example Program
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
def print_list(head):
current = head
while current is not None:
print(current.data, end=" -> ")
current = current.next
print("None")
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
print_list(head)
```
Output
```text
10 -> 20 -> 30 -> None
```
This program manually creates three nodes and connects them. The `print_list` function starts from `head` and prints every node until `current` becomes `None`.
Linked List in Python Interviews
Interview linked list questions often ask you to reverse a linked list, find the middle node, detect a cycle, merge two sorted lists, remove duplicates, or delete a node.
All these problems depend on one core skill: moving references carefully without losing access to the list.
A linked list should be understood through references, not indexes. In an array or list, position matters because elements are stored in index order. In a linked list, each node knows only where the next node is located.
The `head` reference is the entry point of the list. If the head is lost, the full list becomes unreachable from your program. This is why linked list operations must update references carefully and in the correct order.
When inserting at the beginning, the new node should first point to the old head. Then head should move to the new node. If the order is reversed carelessly, the original list can become disconnected.
When deleting a node, we usually do not move all remaining values like an array. We change links so that the unwanted node is skipped. This is the main difference between array deletion and linked list deletion.
Linked list questions test patience and pointer thinking. Drawing nodes on paper is not a beginner trick; it is a professional debugging technique for reference-based structures.
Practice Question
Create a linked list with three nodes and print the sum of all node values. Then add one node at the beginning and print the updated list.