/
Linked Lists
A linked list is a linear data structure where each element (node) contains a value and a reference (pointer) to the next node in the sequence. Unlike arrays, linked list elements are not stored in contiguous memory locations.
Data Structure
O(1) Insert
What is a Linked List?
A singly linked list is a collection of nodes where each node stores two things: the data it holds, and a pointer (or reference) to the next node in the sequence. The first node is called the head, and the last node's next pointer is null, indicating the end of the list.
Unlike arrays, linked lists do not require contiguous blocks of memory. Each node can be stored anywhere in memory, and the pointers connect them in order. This makes insertions and deletions very efficient because you only need to update pointers, rather than shifting elements as you would in an array.
Key characteristics of singly linked lists:
- Dynamic size — The list can grow or shrink at runtime without needing to pre-allocate a fixed block of memory.
- Efficient head insertion/deletion — Adding or removing a node at the head takes O(1) time because you only update the head pointer.
- Sequential access — To reach the n-th element, you must traverse from the head through n nodes. There is no random access like arrays provide.
- Extra memory per element — Each node stores a pointer in addition to its data, which adds memory overhead compared to arrays.
- No wasted capacity — Unlike dynamic arrays, there is no unused allocated space. Every allocated node holds data.
Linked lists are foundational to many advanced data structures. Stacks and queues can be implemented with linked lists. Hash tables use linked lists (chaining) to handle collisions. Graphs often use adjacency lists, which are arrays of linked lists. Understanding linked lists builds intuition for pointer manipulation that transfers to trees, graphs, and other reference-based structures.
Interactive Visualization
Experiment with the linked list below. Enter a value and/or index, then click an operation button to see how it works step by step. Use the playback controls to step through or auto-play the animation.
Singly linked list: 10 → 25 → 8 → 42 → 17. Use the operation buttons below to manipulate the list.
Code Implementation
Below is a complete singly linked list implementation with insert, delete, search, and print operations in three languages.
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert_at_head(self, data):
"""Insert a new node at the beginning. O(1)"""
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_at_index(self, data, index):
"""Insert a new node at the given index. O(n)"""
if index == 0:
self.insert_at_head(data)
return
new_node = Node(data)
current = self.head
for i in range(index - 1):
if current is None:
raise IndexError("Index out of bounds")
current = current.next
if current is None:
raise IndexError("Index out of bounds")
new_node.next = current.next
current.next = new_node
def delete_at_index(self, index):
"""Delete the node at the given index. O(n)"""
if self.head is None:
raise IndexError("List is empty")
if index == 0:
self.head = self.head.next
return
current = self.head
for i in range(index - 1):
if current.next is None:
raise IndexError("Index out of bounds")
current = current.next
if current.next is None:
raise IndexError("Index out of bounds")
current.next = current.next.next
def search(self, value):
"""Search for a value. Returns index or -1. O(n)"""
current = self.head
index = 0
while current is not None:
if current.data == value:
return index
current = current.next
index += 1
return -1
def print_list(self):
"""Print the list in a readable format."""
elements = []
current = self.head
while current is not None:
elements.append(str(current.data))
current = current.next
print(" -> ".join(elements) + " -> None")
# Example usage
ll = LinkedList()
for val in [17, 42, 8, 25, 10]:
ll.insert_at_head(val)
ll.print_list() # 10 -> 25 -> 8 -> 42 -> 17 -> None
ll.insert_at_index(99, 2)
ll.print_list() # 10 -> 25 -> 99 -> 8 -> 42 -> 17 -> None
ll.delete_at_index(3)
ll.print_list() # 10 -> 25 -> 99 -> 42 -> 17 -> None
print(ll.search(42)) # 3
print(ll.search(100)) # -1
public class LinkedList {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node head;
public LinkedList() {
this.head = null;
}
/** Insert a new node at the beginning. O(1) */
public void insertAtHead(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
/** Insert a new node at the given index. O(n) */
public void insertAtIndex(int data, int index) {
if (index == 0) {
insertAtHead(data);
return;
}
Node newNode = new Node(data);
Node current = head;
for (int i = 0; i < index - 1; i++) {
if (current == null)
throw new IndexOutOfBoundsException("Index out of bounds");
current = current.next;
}
if (current == null)
throw new IndexOutOfBoundsException("Index out of bounds");
newNode.next = current.next;
current.next = newNode;
}
/** Delete the node at the given index. O(n) */
public void deleteAtIndex(int index) {
if (head == null)
throw new IllegalStateException("List is empty");
if (index == 0) {
head = head.next;
return;
}
Node current = head;
for (int i = 0; i < index - 1; i++) {
if (current.next == null)
throw new IndexOutOfBoundsException("Index out of bounds");
current = current.next;
}
if (current.next == null)
throw new IndexOutOfBoundsException("Index out of bounds");
current.next = current.next.next;
}
/** Search for a value. Returns index or -1. O(n) */
public int search(int value) {
Node current = head;
int index = 0;
while (current != null) {
if (current.data == value)
return index;
current = current.next;
index++;
}
return -1;
}
/** Print the list in a readable format. */
public void printList() {
StringBuilder sb = new StringBuilder();
Node current = head;
while (current != null) {
sb.append(current.data);
sb.append(" -> ");
current = current.next;
}
sb.append("null");
System.out.println(sb.toString());
}
public static void main(String[] args) {
LinkedList ll = new LinkedList();
int[] values = {17, 42, 8, 25, 10};
for (int val : values) {
ll.insertAtHead(val);
}
ll.printList(); // 10 -> 25 -> 8 -> 42 -> 17 -> null
ll.insertAtIndex(99, 2);
ll.printList(); // 10 -> 25 -> 99 -> 8 -> 42 -> 17 -> null
ll.deleteAtIndex(3);
ll.printList(); // 10 -> 25 -> 99 -> 42 -> 17 -> null
System.out.println(ll.search(42)); // 3
System.out.println(ll.search(100)); // -1
}
}
#include <iostream>
#include <stdexcept>
using namespace std;
struct Node {
int data;
Node* next;
Node(int val) : data(val), next(nullptr) {}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
// Insert a new node at the beginning. O(1)
void insertAtHead(int data) {
Node* newNode = new Node(data);
newNode->next = head;
head = newNode;
}
// Insert a new node at the given index. O(n)
void insertAtIndex(int data, int index) {
if (index == 0) {
insertAtHead(data);
return;
}
Node* newNode = new Node(data);
Node* current = head;
for (int i = 0; i < index - 1; i++) {
if (current == nullptr)
throw out_of_range("Index out of bounds");
current = current->next;
}
if (current == nullptr)
throw out_of_range("Index out of bounds");
newNode->next = current->next;
current->next = newNode;
}
// Delete the node at the given index. O(n)
void deleteAtIndex(int index) {
if (head == nullptr)
throw runtime_error("List is empty");
if (index == 0) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
for (int i = 0; i < index - 1; i++) {
if (current->next == nullptr)
throw out_of_range("Index out of bounds");
current = current->next;
}
if (current->next == nullptr)
throw out_of_range("Index out of bounds");
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}
// Search for a value. Returns index or -1. O(n)
int search(int value) {
Node* current = head;
int index = 0;
while (current != nullptr) {
if (current->data == value)
return index;
current = current->next;
index++;
}
return -1;
}
// Print the list in a readable format.
void printList() {
Node* current = head;
while (current != nullptr) {
cout << current->data << " -> ";
current = current->next;
}
cout << "nullptr" << endl;
}
// Destructor to free memory
~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
}
};
int main() {
LinkedList ll;
int values[] = {17, 42, 8, 25, 10};
for (int val : values) {
ll.insertAtHead(val);
}
ll.printList(); // 10 -> 25 -> 8 -> 42 -> 17 -> nullptr
ll.insertAtIndex(99, 2);
ll.printList(); // 10 -> 25 -> 99 -> 8 -> 42 -> 17 -> nullptr
ll.deleteAtIndex(3);
ll.printList(); // 10 -> 25 -> 99 -> 42 -> 17 -> nullptr
cout << ll.search(42) << endl; // 3
cout << ll.search(100) << endl; // -1
return 0;
}
Complexity Analysis
The table below summarizes the time and space complexities for common singly linked list operations.
| Operation | Time Complexity | Notes |
|---|---|---|
| Access (by index) | O(n) | Must traverse from head to the target index |
| Search (by value) | O(n) | Linear scan; no random access |
| Insert at head | O(1) | Only the head pointer is updated |
| Insert at index | O(n) | Must traverse to the insertion point first |
| Delete (by index) | O(n) | Must find the predecessor node before relinking |
| Space | O(n) | One node allocated per element, plus one pointer per node |
Practice Problems
Strengthen your understanding of linked lists with these classic problems.
Quiz
Q1. What is the time complexity of inserting a node at the head of a singly linked list?
Inserting at the head is O(1) because you only need to create the new node, set its next pointer to the current head, and update the head pointer. No traversal is required.
Q2. What does the last node's next pointer point to in a singly linked list?
In a singly linked list, the last node's next pointer is null (or None in Python), which signals the end of the list. If it pointed to the head, it would be a circular linked list.
Q3. Which of the following is a key advantage of linked lists over arrays?
Linked lists excel at O(1) insertion and deletion at the head since only pointer updates are needed. Arrays require shifting elements for these operations. However, arrays have better cache locality and O(1) random access, which linked lists lack.
Q4. To delete a node at a given index in a singly linked list, you need to find which node first?
To delete a node in a singly linked list, you must update the predecessor's next pointer to skip over the target node. Since there is no backward pointer, you must traverse to the node just before the target so you can relink its next pointer.
Q5. How much additional memory does each node in a singly linked list require compared to just storing the data value?
Each node in a singly linked list stores one extra pointer (the next reference) in addition to the data. A doubly linked list would store two pointers (next and previous), but a singly linked list only needs one.