The linked list is a non-contiguous data structure. It is a collection of nodes arranged in a linear sequence. Nodes are connected using a Node pointer.
Types of Linked List
There are three types of linked lists:
- Singly linked list
- Doubly linked list
- Circular linked list
a. Singly circular linked list
b. Doubly circular linked list
Singly Linked List
In the Singly linked list, each Node has its value and a pointer holding the address of the next node in the list. Using the next pointer we can traverse the Linked List. The last Node of the linked list doesn’t point to any memory location, it contains None.
Doubly Linked List
In the Doubly linked list, each Node has its value and two pointers holding the address of the next node in the list and the address of the previous node in the list. Using the next and previous pointers we can traverse the Linked List. The next point pointer of the last node of the linked list and the previous Node of the head Node doesn’t point to any memory location, it contains None.
Circular Linked List
In Circular Linked List there are no None pointers. Each Node’s next/prev pointers contain the address of the next or previous Nodes.
Circular Linked List can be singly list or doubly list. For the Singly list, the last node’s next pointer contains the address of the head node, for the doubly linked list, the head node’s previous pointer contains the address of the node, and the last node’s next pointer contains the address of the head node. Ideally, there is no head node in the circular linked list. Any node can be assigned as the head node.
Circular Doubly Linked List
What is a Node in linked List
Each node contains a value and pointers to another node in the linked list.
Nodes are randomly stored in random memory locations, it does not need contiguous memory locations.
For a singly linked list, a node contains a single pointer, pointing to the next node.
For a doubly linked list, a node contains two pointers, pointing to the next node and the previous node.
In python, we can use class to define a node.
from typing import Any
class NodeSingly:
"""Node definition for a linked list.
Args:
value: Node value.
"""
def __init__(self, value: Any):
self.value = value
self.next = None
class NodeDoubly:
"""Node definition for a linked list.
Args:
value: Node value.
"""
def __init__(self, value: Any):
self.value = value
self.next = None
self.prev = None
Pros of Linked List
The linked list provides constant time insertion and deletion from the front of the list. Memory can be allocated on a need basis, with no fixed memory allocation required, unlike an array.
Cons of Linked List
A linked list is not memory efficient as it needs to store additional information regarding the next/prev node. A random node can not be accessed at constant time, linear time is required to access any node. Only a doubly linked list supports reverse traverse.
Linked List Operations
Common operations in linked lists are
- Traversal
- Traverse the linked list, access each node in the list, and returns the values of the list.
- Insertion
- Insertion a node in the linked list. A node can be inserted at the front of the list or the end of the list or any random index in the list.
- Insertion on the front is constant time operation. Insertion at any random index or at the end of the list of linear time complexity.
- Deletion
- Delete a node in the linked list. A node can be deleted from anywhere in the list, from the front, at any random index, or the end.
- Deletion on the front is constant time. Deletion at any random index or the end is linear time complex.
- Search
- Search for a value in the linked list. Since random access Is not possible in the linked list, unlike the array, to search for any value we have to traverse the list.
- Update
- Update the value of any node in the list. The update operation is also linear time complex, as we need to traverse the list.
Traverse
Access the values of the linked list nodes. A single for loop can be used to traverse the singly or doubly linked list as follows. The same approach also works for a circular linked list.
def traverse(self) -> List[Any]:
"""Traverse the linked list.
Returns:
A list containing the node values.
"""
values =[]
current = self.head
while current:
values.append(current.value)
current = current.next
print(values)
return values
Insertion
A node can be inserted at the head of the list, at the tail of the list, or a given index of the list.
Inserting at the head node is of constant complexity. To insert at the head node the next pointer of the new node is assigned to the head node and the head pointer is reassigned to the new node as shown in the below diagram. The new node is now the head node of the list.
The insertion at the tail of the list is of linear complexity. To insert at the tail of the list, we need to traverse the list to get the last node and assigned the next pointer of the last node to the new node. Here the newly added node becomes the last node of the list.
Insertion at a given index of the list is of linear complexity. To insert at a given index, we need to traverse the list to find the node whose index precedes the target index at which insertion is required. The next pointer of the new node is assigned to that node’s next pointer and the next pointer of that node is reassigned to the new node as shown in the following diagram.
For the doubly linked list also the process is similar for the above cases, except that we need to handle one additional pointer to update the previous pointer.
Implementation of adding a node at a given index, when the index is 0, is the same as adding a node at the head node, when the index is equal to the length of the list, it is equivalent to adding a node at the tail of the list.
def add_at_index(self, index: int, value: Any) -> None:
"""Add a node at a given index.
Args:
index: Index at which the node should be added.
value: Value of the node.
"""
if not self.head and index > 0:
return
current_id = 0
current =self.head
# Add at the beginning of the head
if index == 0:
self.head = Node(value)
self.head.next = current
return
# given index can be the tail also
while current_id < index-1:
if current.next:
current = current.next
current_id += 1
else:
return
newnode = Node(value)
newnode.next = current.next
current.next = newnode
Deletion
A node can be deleted from a linked list, it can be the head node, the tail node, or a node at a given index.
To delete the head node, the head pointer is assigned to the next node, it is of constant complexity.
To delete the tail node, we need to traverse the list to get the node just before the tail node. The next pointer of the node just before the tail is assigned to None to delete the tail node. This is a linear time-complex operation.
To delete a node at any given index, we also need to traverse the list to get the node just before the node to delete. The next pointer of that node is assigned to the deleted node’s next pointer. This is a linear time-complex operation.
For the doubly linked list also the process is similar for the above cases, except that we need to handle one additional pointer to update the previous pointer.
Implementation of node deletion at a given index. when the index is 0, it is the same as deleting the head node, when the index is equal to the length of the list, it is equivalent to deleting the tail of the list.
def delete_at_index(self, index: int) -> None:
"""Delete a node at a given index.
Args:
index: Index of the node to delete.
"""
if not self.head:
raise ValueError("Empty list.")
# delete from the front of the list.
if index == 0:
self.head = self.head.next
return
current_id = 0
current = self.head
# delete at index other than the list front.
while current_id < index -1:
if not current.next:
return
current = current.next
current_id += 1
if current.next:
current.next = current.next.next
Search
To search for a value in the linked list, we can traverse the list until we find the desired value.
def search(self, value: Any) -> int:
"""Search if a value exists in the list.
Args:
value: Value to search.
Returns:
Index of the node containing the value if exists, else -1.
"""
current = self.head
index = 0
while current:
if current.value == value:
return index
current = current.next
index += 1
return -1
We can also traverse the list to get the value of a node at a given index
def get(self, index:int) -> Any:
"""Get the value of a node at a given index.
Args:
index: Index if the node in the linked list.
Returns:
Value of the node if it exists else -1.
"""
current_id = 0
current = self.head
while current_id < index:
if current.next:
current = current.next
current_id += 1
else:
return -1
if current:
return current.value
return -1
Update
Update the value of the node at a given index. For this also we need to traverse the linked list, due to which the operation is of linear complexity.
def update_at_index(self, index: int, value: Any) -> None:
"""Update a node at a given index.
Args:
index: Index at which the node should be updated.
value: Value of the node.
"""
if not self.head and index >= 0:
return
current_id = 0
current =self.head
if index == 0:
self.head.value = value
return
while current_id < index:
if current.next:
current = current.next
current_id += 1
else:
return
current.value = value
Implementation
Here we implement a singly and doubly linked list using python.
Singly linked list implementation
Scroll the below code block to see the full implementation.
from typing import Any, List
class Node:
"""Node definition for a linked list.
Args:
value: Node value.
"""
def __init__(self, value: Any):
self.value = value
self.next = None
class LinkedList:
"""Linked list.
Args:
value: Optional value for the head node.
"""
def __init__(self, value: Any=None):
"""Initialize list attributes."""
self.head = None
if value:
self.head = Node(value)
def get(self, index:int) -> Any:
"""Get the value of a node at a given index.
Args:
index: Index if the node in the linked list.
Returns:
Value of the node if it exists else -1.
"""
current_id = 0
current = self.head
while current_id < index:
if current.next:
current = current.next
current_id += 1
else:
return -1
if current:
return current.value
return -1
def add_at_head(self, value: Any) -> None:
"""Add a node at the front of the linked list.
Args:
value: Value of the node to add.
"""
if self.head:
newnode = Node(value)
newnode.next = self.head
self.head = newnode
else:
self.head = Node(value)
def add_at_tail(self, value: Any) -> None:
"""Add a node at the tail of the list.
Args:
value: Value of the node to add.
"""
if self.head:
current = self.head
while current.next:
current = current.next
current.next = Node(value)
else:
self.head = Node(value)
def add_at_index(self, index: int, value: Any) -> None:
"""Add a node at a given index.
Args:
index: Index at which the node should be added.
value: Value of the node.
"""
if not self.head and index > 0:
return
current_id = 0
current =self.head
if index == 0:
self.head = Node(value)
self.head.next = current
return
while current_id < index-1:
if current.next:
current = current.next
current_id += 1
else:
return
newnode = Node(value)
newnode.next = current.next
current.next = newnode
def delete_at_index(self, index: int) -> None:
"""Delete a node at a given index.
Args:
index: Index of the node to delete.
"""
if not self.head:
raise ValueError("Empty list.")
# delete from the front of the list.
if index == 0:
self.head = self.head.next
return
current_id = 0
current = self.head
# delete at index other than the list front.
while current_id < index -1:
if not current.next:
return
current = current.next
current_id += 1
if current.next:
current.next = current.next.next
def remove(self, value: Any) -> None:
"""Remove a node containing the given value.
Args:
value: Value of the node to remove.
"""
if not self.head:
raise ValueError("Empty list.")
current = self.head
if value == current.value:
if current.next:
self.head = current.next
else:
self.head=None
else:
while current.next:
if value == current.next.value:
current.next = current.next.next
break
current = current.next
def update_at_index(self, index: int, value: Any) -> None:
"""Update a node at a given index.
Args:
index: Index at which the node should be updated.
value: Value of the node.
"""
if not self.head and index >= 0:
return
current_id = 0
current =self.head
if index == 0:
self.head.value = value
return
while current_id < index:
if current.next:
current = current.next
current_id += 1
else:
return
current.value = value
def search(self, value: Any) -> int:
"""Search if a value exists in the list.
Args:
value: Value to search.
Returns:
Index of the node containing the value if exists, else -1.
"""
current = self.head
index = 0
while current:
if current.value == value:
return index
current = current.next
index += 1
return -1
def traverse(self) -> List[Any]:
"""Traverse the linked list.
Returns:
A list containing the node values.
"""
values =[]
current = self.head
while current:
values.append(current.value)
current = current.next
print(values)
return values
ll = LinkedList(1)
ll.add_at_index(1, 2)
ll.add_at_index(2, 3)
ll.add_at_index(3, 4)
ll.add_at_index(3, 5)
ll.add_at_index(3, 6)
ll.traverse()
ll.delete_at_index(1)
ll.traverse()
ll.delete_at_index(1)
ll.traverse()
ll.update_at_index(1, 10)
ll.traverse()
print(ll.search(10))
ll.remove(5)
ll.traverse()
ll.remove(1)
ll.traverse()
Doubly Linked List Implementation
Scroll the below code block to see the full implementation.
from typing import Any
class Node:
"""Node definition for a linked list.
Args:
value: Node value.
"""
def __init__(self, value: Any):
self.value = value
self.next = None
self.prev = None
class MyLinkedList:
"""Linked list.
Args:
value: Optional value for the head node.
"""
def __init__(self, value: Any=None):
"""Initialize list attributes."""
self.head = None
if value:
self.head = Node(value)
def get(self, index:int) -> Any:
"""Get the value of a node at a given index.
Args:
index: Index if the node in the linked list.
Returns:
Value of the node if it exists else -1.
"""
current_id = 0
current = self.head
while current_id < index:
if current.next:
current = current.next
current_id += 1
else:
return -1
if current:
return current.value
return -1
def add_at_head(self, value: Any) -> None:
"""Add a node at the front of the linked list.
Args:
value: Value of the node to add.
"""
if self.head:
newnode = Node(value)
newnode.next = self.head
self.head = newnode
else:
self.head = Node(value)
def add_at_tail(self, value: Any) -> None:
"""Add a node at the tail of the list.
Args:
value: Value of the node to add.
"""
if self.head:
current = self.head
while current.next:
current = current.next
newnode = Node(value)
newnode.prev = current
current.next = newnode
else:
self.head = Node(value)
def add_at_ndex(self, index: int, value: Any) -> None:
"""Add a node at a given index.
Args:
index: Index at which the node should be added.
value: Value of the node.
"""
if not self.head and index > 0:
return
current_id = 0
current =self.head
if index == 0:
self.head = Node(value)
self.head.next = current
return
while current_id < index-1:
if current.next:
current = current.next
current_id += 1
else:
return
newnode = Node(value)
newnode.next = current.next
newnode.prev = current
current.next = newnode
def delete_at_index(self, index: int) -> None:
"""Delete a node at a given index.
Args:
index: Index of the node to delete.
"""
if not self.head:
raise ValueError("Empty list.")
if index == 0:
self.head = self.head.next
if self.head:
self.head.prev = None
return
current_id = 0
current = self.head
while current_id < index -1:
if not current.next:
return
current = current.next
current_id += 1
if current.next:
current.next = current.next.next
if current.next:
current.next.prev = current
def update_at_index(self, index: int, value: Any) -> None:
"""Update a node at a given index.
Args:
index: Index at which the node should be updated.
value: Value of the node.
"""
if not self.head and index >= 0:
return
current_id = 0
current =self.head
if index == 0:
self.head.value = value
return
while current_id < index:
if current.next:
current = current.next
current_id += 1
else:
return
current.value = value
def search(self, value: Any) -> int:
"""Search if a value exists in the list.
Args:
value: Value to search.
Returns:
Index of the node containing the value if exists, else -1.
"""
current = self.head
index = 0
while current:
if current.value == value:
return index
current = current.next
index += 1
return -1
Loop/Cycle in a linked list
When the next pointer of a node connects to a previous node of a linked list, that particular scenario is referred to as a cycle in the linked list.
When the last node’s next pointer connects to the head node, that situation is referred to as a circular linked list.
To detect a loop in a linked list, we can traverse the list and use a set data structure. A set is a data structure that contains unique values.
def has_loop(head: Node) -> bool:
"""Check for loop.
Args:
head: Head node of the list.
Returns:
True if the loop exists, else False.
"""
nodes = set()
if not head:
return False
nodes.add(head)
while head.next:
head = head.next
if head in nodes:
return True
nodes.add(head)
return False