Linked lists are a crucial data structure in computer science, providing a dynamic way to store and manage data. They offer significant advantages over arrays, especially for certain types of operations. This detailed guide will explain the types of linked lists, common operations, and their advantages over arrays, with examples in both Java and Python.
What is a Linked List?
A linked list is a linear data structure where each element, called a node, contains a data part and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, allowing for more flexible data management.
Key Characteristics of Linked Lists
- Dynamic Size: The size of a linked list can grow or shrink dynamically.
- Non-Contiguous Storage: Nodes are stored in non-contiguous memory locations.
- Ease of Insertion/Deletion: Inserting and deleting nodes is efficient, especially compared to arrays.
Types of Linked Lists
- Singly Linked List: Each node points to the next node.
- Doubly Linked List: Each node points to both the next and previous nodes.
- Circular Linked List: The last node points back to the first node, forming a circle.
Singly Linked List
A singly linked list contains nodes that point to the next node in the sequence.
Singly Linked List Executable Code Examples Using Java & Python
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class SinglyLinkedList {
Node head;
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " -> ");
temp = temp.next;
}
System.out.println("null");
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.display();
}
}
// Output:
// 1 -> 2 -> 3 -> nullclass Node:
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
def display(self):
temp = self.head
while temp:
print(temp.data, end=" -> ")
temp = temp.next
print("null")
# Example usage
list = SinglyLinkedList()
list.insert(1)
list.insert(2)
list.insert(3)
list.display()
# Output:
# 1 -> 2 -> 3 -> null
Doubly Linked List
A doubly linked list contains nodes that point to both the next and previous nodes, allowing traversal in both directions.
Doubly Linked List Executable Code Examples Using Java & Python
class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
public class DoublyLinkedList {
Node head;
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
} else {
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
newNode.prev = temp;
}
}
public void display() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " <-> ");
temp = temp.next;
}
System.out.println("null");
}
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.display();
}
}
// Output:
// 1 <-> 2 <-> 3 <-> nullclass Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
temp = self.head
while temp.next:
temp = temp.next
temp.next = new_node
new_node.prev = temp
def display(self):
temp = self.head
while temp:
print(temp.data, end=" <-> ")
temp = temp.next
print("null")
# Example usage
list = DoublyLinkedList()
list.insert(1)
list.insert(2)
list.insert(3)
list.display()
# Output:
# 1 <-> 2 <-> 3 <-> null
Circular Linked List
A circular linked list is similar to a singly linked list, but the last node points back to the first node, forming a circle.
Circular Linked List Executable Code Examples Using Java & Python
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class CircularLinkedList {
Node head;
public void insert(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
head.next = head;
} else {
Node temp = head;
while (temp.next != head) {
temp = temp.next;
}
temp.next = newNode;
newNode.next = head;
}
}
public void display() {
if (head == null) return;
Node temp = head;
do {
System.out.print(temp.data + " -> ");
temp = temp.next;
} while (temp != head);
System.out.println("head");
}
public static void main(String[] args) {
CircularLinkedList list = new CircularLinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.display();
}
}
// Output:
// 1 -> 2 -> 3 -> head
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def insert(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
new_node.next = self.head
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node
new_node.next = self.head
def display(self):
if self.head is None:
return
temp = self.head
while True:
print(temp.data, end=" -> ")
temp = temp.next
if temp == self.head:
break
print("head")
# Example usage
list = CircularLinkedList()
list.insert(1)
list.insert(2)
list.insert(3)
list.display()
# Output:
# 1 -> 2 -> 3 -> head
Common Operations on Linked Lists
Insertion
Adding a new node to the linked list.
Java Example
// Insertion code is included in the previous examplesPython Example
# Insertion code is included in the previous examplesDeletion
Removing a node from the linked list.
Deletion Examples:
public class SinglyLinkedList {
Node head;
// Other methods...
public void delete(int key) {
Node temp = head, prev = null;
// If head node itself holds the key
if (temp != null && temp.data == key) {
head = temp.next; // Changed head
return;
}
// Search for the key to be deleted
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
// If key was not present in the list
if (temp == null) return;
// Unlink the node from linked list
prev.next = temp.next;
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
list.insert(1);
list.insert(2);
list.insert(3);
list.delete(2);
list.display();
}
}
// Output:
// 1 -> 3 -> nullclass SinglyLinkedList:
def __init__(self):
self.head = None
# Other methods...
def delete(self, key):
temp = self.head
# If head node itself holds the key
if temp is not None:
if temp.data == key:
self.head = temp.next
temp = None
return
# Search for the key to be deleted
prev = None
while temp is not None:
if temp.data == key:
break
prev = temp
temp = temp.next
# If key was not present in the list
if temp == None:
return
# Unlink the node from linked list
prev.next = temp.next
temp = None
# Example usage
list = SinglyLinkedList()
list.insert(1)
list.insert(2)
list.insert(3)
list.delete(2)
list.display()
# Output:
# 1 -> 3 -> nullAdvantages of Linked Lists Over Arrays
- Dynamic Size: Linked lists can grow and shrink dynamically, whereas arrays have a fixed size.
- Efficient Insertions/Deletions: Adding or removing elements in a linked list is efficient, especially at the beginning or middle.
- No Wasted Space: Linked lists do not require pre-allocated memory, preventing wasted space.
Comparison Table
| Feature | Linked List | Array |
|---|---|---|
| Size | Dynamic | Fixed |
| Memory Allocation | Non-contiguous | Contiguous |
| Insertions/Deletions | Efficient (O(1) at beginning) | Inefficient (O(n) worst case) |
| Access Time | Sequential (O(n)) | Random (O(1)) |
| Memory Utilization | No wasted space | May have wasted space |
Conclusion
Linked lists are a versatile and powerful data structure, offering significant advantages over arrays in certain scenarios. Understanding the different types of linked lists, common operations, and their benefits will enhance your ability to manage dynamic data structures effectively, especially in testing environments.
Article Contributors
Subscribe to QABash Weekly 💥
Dominate – Stay Ahead of 99% Testers!
