Types of Linked List - Singly linked, doubly linked and circular (Data Structures & Algorithms)

Why This Matters

Linked lists are fundamental data structures in computer science that provide dynamic memory allocation and allow for efficient manipulation of data elements. In this tutorial, we will delve into three types of linked lists: singly linked, doubly linked, and circular linked lists, each with its unique advantages and applications. We'll explore these concepts using Python examples and learn how to implement and use them effectively.

Why This Matters

Understanding linked lists is crucial for grasping dynamic memory allocation, data structures, and algorithms. They are essential in various real-world scenarios such as implementing efficient data structures for stacks, queues, and dynamic arrays. Furthermore, they help in debugging common programming errors related to memory management.

Prerequisites

Before diving into the types of linked lists, it is essential to have a good understanding of the following concepts:

• Basic Python syntax and control structures (if-else, for, while)
• Data structures like arrays and lists
• Memory management in Python (dynamic memory allocation)
• Familiarity with recursion can be helpful but is not strictly required.

Core Concept

Singly Linked List

A singly linked list is a linear data structure where each node contains a data element and a reference to the next node. The last node in the list has a None or null pointer indicating the end of the list. Here's an example of a singly linked list:

class 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 not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node

def print_list(self):
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")

Doubly Linked List

A doubly linked list is an extension of a singly linked list, where each node contains two pointers—one pointing to the next node and another pointing to the previous node. This allows for efficient traversal in both directions. Here's an example of a doubly linked list:

class 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 not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current

def append(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.prev = current
new_node.next = None

def print_list(self, reverse=False):
if reverse:
current = self.head
while current and current.prev:
print(current.data, end=" <- ")
current = current.prev
print(current.data, end=" <- None")
else:
current = self.head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")

Circular Linked List

A circular linked list is a type of linked list where the last node's next pointer points back to the first node, forming a cycle. This structure allows for efficient traversal from any node to any other node in the list. Here's an example of a circular linked list:

class Node:
def __init__(self, data):
self.data = data
self.next = None

class CircularLinkedList:
def __init__(self):
self.head = None
self.tail = None

def insert(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.tail = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
new_node.next = self.head

def print_list(self):
if not self.head:
print("Empty list")
else:
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break

Worked Example

Let's create a singly linked list, doubly linked list, and circular linked list using the provided classes and insert some data:

Singly Linked List

sll = SinglyLinkedList()

sll.insert(1)

sll.insert(2)

sll.insert(3)

sll.print_list() # Output: 1 -> 2 -> 3 -> None

Doubly Linked List

dll = DoublyLinkedList()

dll.insert(4)

dll.append(5)

dll.insert(6)

dll.print_list() # Output: 6 <- 5 <- 4 <- None

dll.print_list(reverse=True) # Output: None <- 4 <- 5 <- 6

Circular Linked List

cll = CircularLinkedList()

cll.insert(7)

cll.insert(8)

cll.print_list() # Output: 7 -> 8 -> 7

Common Mistakes

1. Forgetting to initialize the head or tail node in a linked list
2. Not setting the next or previous pointers correctly when inserting nodes
3. Creating an infinite loop while traversing the linked list due to incorrect pointer handling
4. Failing to handle edge cases such as empty lists or duplicate data entries
5. Using inappropriate data structures for specific problems (e.g., using a singly linked list where a doubly linked list would be more efficient)
6. Neglecting to free memory when working with circular linked lists to avoid memory leaks

Practice Questions

1. Implement a function to find the length of a singly linked list.
2. Write a function to reverse a singly linked list recursively and iteratively.
3. Create a doubly linked list and implement functions for inserting, deleting, and searching nodes.
4. Implement a circular queue using a circular linked list with a fixed size.
5. Solve the following problem: Given a singly linked list, determine if it contains a cycle.
6. Implement a function to merge two sorted singly linked lists into one sorted singly linked list.
7. Write a function to find the middle node of a singly linked list.
8. Implement a function to remove duplicates from a singly linked list.
9. Solve the following problem: Given a circular linked list, return the node that precedes the given node in the list. If the given node is the first node, return None.
10. Write a function to reverse every k-th node in a singly linked list (e.g., reversing every third node for a list with nodes 1->2->3->4->5->6 results in 1->3->2->6->5->4).

FAQ

1. What is the time complexity of inserting an element in a singly linked list? - O(1) for average and worst-case scenarios since we are adding elements at the end or in the middle of the list.
2. Why use doubly linked lists over singly linked lists? - Doubly linked lists allow efficient traversal in both directions, which can be useful in certain applications such as implementing a queue data structure. They also make deleting nodes easier since we have access to the previous node.
3. What are some advantages and disadvantages of using circular linked lists? - Advantages include efficient traversal from any node to any other node in the list, but they can also lead to memory leaks if not implemented correctly. Disadvantages include the complexity of operations like insertion and deletion compared to singly or doubly linked lists.
4. Can we implement a stack or queue using a circular linked list? - Yes, both stacks and queues can be efficiently implemented using circular linked lists.
5. What is the time complexity of searching for an element in a singly linked list? - The average time complexity is O(n), where n is the number of nodes in the list. However, if the element is not present in the list, the worst-case scenario has a time complexity of O(n).
6. What is the space complexity of a circular linked list compared to a singly or doubly linked list? - The space complexity of a circular linked list is slightly higher due to the need for an extra pointer (next) in each node to form the cycle. However, this difference is usually negligible in practice.