Linked Lists
Linked lists are linear data structures where elements are stored in nodes, each containing data and a reference to the next node. This module covers the fundamentals of linked lists, their types, operations, and common patterns.
Introduction to Linked Lists
A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each element (node) contains a reference to the next node in the sequence.
Key Characteristics
- Dynamic size (can grow or shrink during execution)
- Efficient insertions and deletions (no shifting required)
- Sequential access (no random access)
- Extra memory for storing references
Types of Linked Lists
1. Singly Linked List
Each node contains data and a reference to the next node. Traversal is only possible in one direction.
Node1(data) -> Node2(data) -> Node3(data) -> ... -> NodeN(data) -> null2. Doubly Linked List
Each node contains data, a reference to the next node, and a reference to the previous node. Traversal is possible in both directions.
null <- Node1(data) <-> Node2(data) <-> Node3(data) <-> ... <-> NodeN(data) -> null3. Circular Linked List
The last node points back to the first node, forming a circle. Can be singly or doubly linked.
Node1(data) -> Node2(data) -> Node3(data) -> ... -> NodeN(data) -┐
^ |
└-----------------------------------------------------------┘Common Operations
| Operation | Time Complexity | Description |
|---|---|---|
| Access | O(n) | Accessing an element requires traversing from the head |
| Search | O(n) | Finding an element requires traversal |
| Insert at beginning | O(1) | Constant time to insert at the head |
| Insert at end | O(n) or O(1)* | O(n) if we only have head reference, O(1) if we maintain a tail reference |
| Delete | O(n) | Need to find the node and update references |
Linked List Implementation
Java Implementation
// Singly Linked List implementation in Java
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class SinglyLinkedList {
Node head;
// Insert at the beginning
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
// Insert at the end
public void insertAtEnd(int data) {
Node newNode = new Node(data);
// If the list is empty, make the new node the head
if (head == null) {
head = newNode;
return;
}
// Traverse to the last node
Node current = head;
while (current.next != null) {
current = current.next;
}
// Add the new node at the end
current.next = newNode;
}
// Insert after a given node
public void insertAfter(Node prevNode, int data) {
if (prevNode == null) {
System.out.println("Previous node cannot be null");
return;
}
Node newNode = new Node(data);
newNode.next = prevNode.next;
prevNode.next = newNode;
}
// Delete a node with given key
public void deleteNode(int key) {
// Store head node
Node temp = head, prev = null;
// If head node itself holds the key to be deleted
if (temp != null && temp.data == key) {
head = temp.next; // Changed head
return;
}
// Search for the key to be deleted, keep track of previous node
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
// If key was not present in linked list
if (temp == null) return;
// Unlink the node from linked list
prev.next = temp.next;
}
// Print the linked list
public void printList() {
Node current = head;
while (current != null) {
System.out.print(current.data + " -> ");
current = current.next;
}
System.out.println("null");
}
}
// Usage example
public class LinkedListExample {
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.insertAtBeginning(0);
list.printList(); // Output: 0 -> 1 -> 2 -> 3 -> null
list.deleteNode(2);
list.printList(); // Output: 0 -> 1 -> 3 -> null
}
}Python Implementation
# Singly Linked List implementation in Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
# Insert at the beginning
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
# Insert at the end
def insert_at_end(self, data):
new_node = Node(data)
# If the list is empty, make the new node the head
if self.head is None:
self.head = new_node
return
# Traverse to the last node
current = self.head
while current.next:
current = current.next
# Add the new node at the end
current.next = new_node
# Insert after a given node
def insert_after(self, prev_node, data):
if prev_node is None:
print("Previous node cannot be None")
return
new_node = Node(data)
new_node.next = prev_node.next
prev_node.next = new_node
# Delete a node with given key
def delete_node(self, key):
# Store head node
temp = self.head
# If head node itself holds the key to be deleted
if temp and temp.data == key:
self.head = temp.next
return
# Search for the key to be deleted, keep track of previous node
prev = None
while temp and temp.data != key:
prev = temp
temp = temp.next
# If key was not present in linked list
if temp is None:
return
# Unlink the node from linked list
prev.next = temp.next
# Print the linked list
def print_list(self):
current = self.head
while current:
print(f"{current.data} -> ", end="")
current = current.next
print("None")
# Usage example
if __name__ == "__main__":
linked_list = SinglyLinkedList()
linked_list.insert_at_end(1)
linked_list.insert_at_end(2)
linked_list.insert_at_end(3)
linked_list.insert_at_beginning(0)
linked_list.print_list() # Output: 0 -> 1 -> 2 -> 3 -> None
linked_list.delete_node(2)
linked_list.print_list() # Output: 0 -> 1 -> 3 -> NoneDoubly Linked List Implementation
Java Implementation
// Doubly Linked List implementation in Java
class Node {
int data;
Node next;
Node prev;
public Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyLinkedList {
Node head;
Node tail;
// Insert at the beginning
public void insertAtBeginning(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
return;
}
newNode.next = head;
head.prev = newNode;
head = newNode;
}
// Insert at the end
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (head == null) {
head = tail = newNode;
return;
}
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
// Insert after a given node
public void insertAfter(Node prevNode, int data) {
if (prevNode == null) {
System.out.println("Previous node cannot be null");
return;
}
Node newNode = new Node(data);
newNode.next = prevNode.next;
newNode.prev = prevNode;
if (prevNode.next != null) {
prevNode.next.prev = newNode;
} else {
tail = newNode;
}
prevNode.next = newNode;
}
// Delete a node with given key
public void deleteNode(int key) {
Node temp = head;
// If head node itself holds the key
if (temp != null && temp.data == key) {
head = temp.next;
if (head != null) {
head.prev = null;
} else {
tail = null;
}
return;
}
// Search for the key to be deleted
while (temp != null && temp.data != key) {
temp = temp.next;
}
// If key was not present in linked list
if (temp == null) return;
// If the node to be deleted is the last node
if (temp == tail) {
tail = temp.prev;
tail.next = null;
return;
}
// Unlink the node from linked list
temp.prev.next = temp.next;
if (temp.next != null) {
temp.next.prev = temp.prev;
}
}
// Print the linked list forward
public void printForward() {
Node current = head;
System.out.print("null <- ");
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.next;
}
System.out.println("null");
}
// Print the linked list backward
public void printBackward() {
Node current = tail;
System.out.print("null <- ");
while (current != null) {
System.out.print(current.data + " <-> ");
current = current.prev;
}
System.out.println("null");
}
}Python Implementation
# Doubly Linked List implementation in Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
# Insert at the beginning
def insert_at_beginning(self, data):
new_node = Node(data)
if self.head is None:
self.head = self.tail = new_node
return
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
# Insert at the end
def insert_at_end(self, data):
new_node = Node(data)
if self.head is None:
self.head = self.tail = new_node
return
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
# Insert after a given node
def insert_after(self, prev_node, data):
if prev_node is None:
print("Previous node cannot be None")
return
new_node = Node(data)
new_node.next = prev_node.next
new_node.prev = prev_node
if prev_node.next:
prev_node.next.prev = new_node
else:
self.tail = new_node
prev_node.next = new_node
# Delete a node with given key
def delete_node(self, key):
temp = self.head
# If head node itself holds the key
if temp and temp.data == key:
self.head = temp.next
if self.head:
self.head.prev = None
else:
self.tail = None
return
# Search for the key to be deleted
while temp and temp.data != key:
temp = temp.next
# If key was not present in linked list
if temp is None:
return
# If the node to be deleted is the last node
if temp == self.tail:
self.tail = temp.prev
self.tail.next = None
return
# Unlink the node from linked list
temp.prev.next = temp.next
if temp.next:
temp.next.prev = temp.prev
# Print the linked list forward
def print_forward(self):
current = self.head
print("null <- ", end="")
while current:
print(f"{current.data} <-> ", end="")
current = current.next
print("null")
# Print the linked list backward
def print_backward(self):
current = self.tail
print("null <- ", end="")
while current:
print(f"{current.data} <-> ", end="")
current = current.prev
print("null")Common Linked List Patterns
1. Fast and Slow Pointers (Floyd's Cycle-Finding Algorithm)
Using two pointers that move at different speeds to solve problems like detecting cycles, finding the middle element, etc.
// Java implementation to detect a cycle in a linked list
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
// Move slow pointer by one and fast pointer by two
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
// If slow and fast pointers meet, there is a cycle
if (slow == fast) {
return true;
}
}
return false;
}2. Reversing a Linked List
A fundamental operation that is often used in more complex linked list problems.
# Python implementation to reverse a linked list
def reverse_list(head):
prev = None
current = head
while current:
next_temp = current.next # Store next node
current.next = prev # Reverse the link
prev = current # Move prev to current
current = next_temp # Move current to next
return prev # New head of the reversed list3. Merge Two Sorted Lists
A common operation in sorting algorithms like merge sort and in many interview questions.
// Java implementation to merge two sorted linked lists
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// Create a dummy head to simplify the code
ListNode dummy = new ListNode(0);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
// Attach the remaining nodes
if (l1 != null) {
current.next = l1;
} else {
current.next = l2;
}
return dummy.next;
}Practice Problems
Apply your knowledge of linked lists by solving these carefully selected problems:
1. Reverse Linked List
Reverse a singly linked list.
EasyLinked ListRecursion
2. Detect Cycle in a Linked List
Determine if a linked list has a cycle in it.
EasyLinked ListTwo Pointers
3. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new sorted list.
EasyLinked ListSorting
4. Remove Nth Node From End of List
Remove the nth node from the end of a linked list and return its head.
MediumLinked ListTwo Pointers