Singly Linked Lists
Introduction to linked lists, node structure, and basic operations. Learn why linked lists exist and when to use them over arrays.
Unlike arrays, where elements sit next to each other in memory, linked lists connect elements through pointers. Each element knows where the next one lives, but they can be scattered anywhere in memory. This flexibility comes with trade-offs.
What is a Linked List?
A linked list is a linear data structure where elements (called nodes) are connected via pointers. Each node contains:
- Data: The actual value stored
- Next pointer: Reference to the next node
Singly Linked List:
head
↓
+------+---+ +------+---+ +------+---+ +------+------+
| data | ●-+--->| data | ●-+--->| data | ●-+--->| data | null |
+------+---+ +------+---+ +------+---+ +------+------+
10 20 30 40
Each node points to the next. The last node points to null.
Node Structure
struct Node<T> {
data: T,
next: Option<Box<Node<T>>>,
}
Linked List Class
pub struct LinkedList<T> {
head: Option<Box<Node<T>>>,
size: usize,
}
impl<T> LinkedList<T> {
pub fn new() -> Self {
Self {
head: None,
size: 0,
}
}
}
Core Operations
Traversal
To access elements, we must traverse from the head:
impl<T: std::fmt::Display> LinkedList<T> {
pub fn traverse(&self) {
let mut current = &self.head;
while let Some(node) = current {
print!("{} ", node.data);
current = &node.next;
}
println!();
}
}
Traversing: 10 → 20 → 30 → 40
Step 1: current = head (10)
Step 2: current = current.next (20)
Step 3: current = current.next (30)
Step 4: current = current.next (40)
Step 5: current = current.next (None) → stop
Insert at Head - O(1)
The most efficient insertion is at the beginning:
impl<T> LinkedList<T> {
pub fn insert_at_head(&mut self, data: T) {
let new_node = Box::new(Node {
data,
next: self.head.take(),
});
self.head = Some(new_node);
self.size += 1;
}
}
Before: head → [10] → [20] → [30]
Insert 5 at head:
Step 1: Create new node with data 5
new_node → [5]
Step 2: new_node.next = head
new_node → [5] → [10] → [20] → [30]
Step 3: head = new_node
head → [5] → [10] → [20] → [30]
Insert at Tail - O(n)
We must traverse to find the last node:
impl<T> LinkedList<T> {
pub fn insert_at_tail(&mut self, data: T) {
let new_node = Box::new(Node {
data,
next: None,
});
if self.head.is_none() {
self.head = Some(new_node);
self.size += 1;
return;
}
let mut current = self.head.as_mut().unwrap();
while current.next.is_some() {
current = current.next.as_mut().unwrap();
}
current.next = Some(new_node);
self.size += 1;
}
}
Optimization: Keep a Tail Pointer
Maintaining a reference to the last node reduces tail insertion from O(n) to O(1). This trades a small amount of memory for significant time savings.
Insert at Index - O(n)
impl<T> LinkedList<T> {
pub fn insert_at_index(&mut self, index: usize, data: T) -> Result<(), &'static str> {
if index > self.size {
return Err("Index out of bounds");
}
if index == 0 {
self.insert_at_head(data);
return Ok(());
}
let mut current = self.head.as_mut().unwrap();
for _ in 0..index - 1 {
current = current.next.as_mut().unwrap();
}
let new_node = Box::new(Node {
data,
next: current.next.take(),
});
current.next = Some(new_node);
self.size += 1;
Ok(())
}
}
Insert 25 at index 2:
Before: [10] → [20] → [30] → [40]
↑
index 1 (stop here)
Step 1: Traverse to node at index 1 (value 20)
Step 2: new_node.next = current.next (30)
Step 3: current.next = new_node
After: [10] → [20] → [25] → [30] → [40]
Delete at Head - O(1)
impl<T> LinkedList<T> {
pub fn delete_at_head(&mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
self.size -= 1;
node.data
})
}
}
Delete at Tail - O(n)
impl<T> LinkedList<T> {
pub fn delete_at_tail(&mut self) -> Option<T> {
if self.head.is_none() {
return None;
}
if self.head.as_ref().unwrap().next.is_none() {
self.size -= 1;
return self.head.take().map(|node| node.data);
}
let mut current = self.head.as_mut().unwrap();
while current.next.as_ref().unwrap().next.is_some() {
current = current.next.as_mut().unwrap();
}
self.size -= 1;
current.next.take().map(|node| node.data)
}
}
Delete by Value - O(n)
impl<T: PartialEq> LinkedList<T> {
pub fn delete_value(&mut self, value: T) -> bool {
if self.head.is_none() {
return false;
}
// Check if head contains the value
if self.head.as_ref().unwrap().data == value {
self.head = self.head.take().unwrap().next;
self.size -= 1;
return true;
}
let mut current = self.head.as_mut().unwrap();
while current.next.is_some() {
if current.next.as_ref().unwrap().data == value {
current.next = current.next.take().unwrap().next;
self.size -= 1;
return true;
}
if current.next.is_some() {
current = current.next.as_mut().unwrap();
} else {
break;
}
}
false
}
}
Search - O(n)
impl<T: PartialEq> LinkedList<T> {
pub fn search(&self, value: T) -> Option<usize> {
let mut current = &self.head;
let mut index = 0;
while let Some(node) = current {
if node.data == value {
return Some(index);
}
current = &node.next;
index += 1;
}
None
}
}
Get Element at Index
impl<T: Clone> LinkedList<T> {
pub fn get(&self, index: usize) -> Option<T> {
if index >= self.size {
return None;
}
let mut current = self.head.as_ref();
for _ in 0..index {
current = current.unwrap().next.as_ref();
}
current.map(|node| node.data.clone())
}
}
Display
impl<T: std::fmt::Display> std::fmt::Display for LinkedList<T> {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
let mut values = Vec::new();
let mut current = &self.head;
while let Some(node) = current {
values.push(format!("{}", node.data));
current = &node.next;
}
write!(f, "{}", values.join(" → "))
}
}
Time Complexity
| Operation | Time Complexity | |-----------|-----------------| | Access by index | O(n) | | Insert at head | O(1) | | Insert at tail | O(n)* | | Insert at index | O(n) | | Delete at head | O(1) | | Delete at tail | O(n) | | Delete by value | O(n) | | Search | O(n) |
*O(1) if tail pointer is maintained
Arrays vs Linked Lists
| Aspect | Array | Linked List | |--------|-------|-------------| | Access | O(1) | O(n) | | Insert at start | O(n) | O(1) | | Insert at end | O(1)* | O(n) | | Memory | Contiguous | Scattered | | Extra space | None | Pointer per node | | Cache performance | Excellent | Poor |
*Amortized for dynamic arrays
When to Use Linked Lists
Use linked lists when:
- Frequent insertions/deletions at the beginning
- Size is unknown and changes frequently
- No need for random access
- Implementing stacks, queues, or other data structures
Use arrays when:
- Random access is needed
- Cache performance matters
- Memory overhead is a concern
- Size is relatively stable
Common Patterns
Reverse a Linked List
impl<T> LinkedList<T> {
pub fn reverse(&mut self) {
let mut prev: Option<Box<Node<T>>> = None;
let mut current = self.head.take();
while let Some(mut node) = current {
let next = node.next.take();
node.next = prev;
prev = Some(node);
current = next;
}
self.head = prev;
}
}
Reversing: 10 → 20 → 30 → null
Step 1: prev=null, curr=10
10.next = null
prev=10, curr=20
Step 2: prev=10, curr=20
20.next = 10
prev=20, curr=30
Step 3: prev=20, curr=30
30.next = 20
prev=30, curr=null
Result: 30 → 20 → 10 → null
Find Middle Element
impl<T: Clone> LinkedList<T> {
pub fn find_middle(&self) -> Option<T> {
let mut slow = &self.head;
let mut fast = &self.head;
while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
slow = &slow.as_ref().unwrap().next;
fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
}
slow.as_ref().map(|node| node.data.clone())
}
}
Memory Management
In languages without garbage collection (C, C++), you must manually free deleted nodes to avoid memory leaks. Rust's ownership system handles this automatically through its Box type and Drop trait.
Key Takeaways
- Linked lists store elements with pointers, not contiguous memory
- O(1) insertion/deletion at head, but O(n) access by index
- Each node requires extra memory for the pointer
- Great for stacks, queues, and when order changes frequently
- Poor cache locality compared to arrays
- Maintain a tail pointer for O(1) tail insertion
Linked lists trade random access speed for flexible insertion and deletion. Understanding when this trade-off makes sense is key to choosing the right data structure.