Types of Linked Lists

Introduction

Back when I was new to programming, figuring out linked lists felt tough. I remember being confused and trying to understand them. But as I kept at it, I started seeing how useful they were. Linked lists aren't just regular lists; they are flexible tools that help solve different problems in programming.

From singly linked lists to doubly circular linked lists, each type of linked list presents unique strengths and applications. Unlike arrays, which store data in contiguous memory locations, linked lists consist of nodes that are connected via pointers. Each node includes data and a reference to the next node in the sequence.

Singly Linked Lists

These are a type of linked list in data structures where each node includes data and a pointer to the next node, forming a linear sequence. Efficient for insertion and deletion at the beginning or end, they excel in scenarios requiring forward traversal. With a simple node structure comprising data and a single pointer, they offer memory efficiency. Singly linked lists are ideal for applications like stacks and queues, where memory allocation is dynamic and traversal primarily occurs in one direction.

Node Structure:

A node in a program for a singly linked list in a data structure typically consists of two components:

• Data: Holds the value of the element.
• Next: A reference to the next node in the sequence.

Code Example:

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

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

# Example Usage
if __name__ == "__main__":
linked_list = SinglyLinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
linked_list.display()

Output:

1 -> 2 -> 3 -> None

Doubly Linked Lists

Doubly linked lists share similarities with singly linked lists but introduce an extra pointer that references the previous node, enabling bidirectional traversal. This additional pointer enhances flexibility, helping efficient forward and backward navigation through the list. Each node contains data and two pointers, one pointing to the next node and the other to the previous node. This structure makes operations like insertion, deletion, and traversal more versatile.

Node Structure:

There are three components in in a doubly linked list node:

• Data: Holds the value of the element.
• Next: A reference to the next node in the sequence.
• Previous: A reference to the previous node in the sequence.

Code Example:

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

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

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

# Example Usage
if __name__ == "__main__":
linked_list = DoublyLinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
print("Forward traversal:")
linked_list.display_forward()
print("Backward traversal:")
linked_list.display_backward()

Output:

Forward traversal:

1 -> 2 -> 3 -> None

Backward traversal:

3 -> 2 -> 1 -> None

Circular Linked Lists

These are a type of linked list that exhibits a unique structure where the last node connects back to the first node and form a circular loop. This circularity allows for efficient traversal that enables continuous movement through the list from any node. Unlike linear lists, circular linked lists don't have a distinct end, offering uninterrupted access to elements. Each node has data and a pointer to the next node, with the last node pointing back to the first. This design simplifies operations like insertion and deletion.

Node Structure:

The components of a node in a circular linked list in a data structure include two main parts.

• Data: Holds the value of the element.
• Next: A reference to the next node in the sequence.

Code Example:

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 # Point to itself to make it circular
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head # Point back to the head to make it circular

def display(self):
if self.head is None:
print("Empty Circular Linked List")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head: # Break if traversal comes back to the head
break
print("(Head)")

# Example Usage
if __name__ == "__main__":
linked_list = CircularLinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
linked_list.display()

Output:

1 -> 2 -> 3 -> (Head)

Doubly Circular Linked Lists

Doubly circular linked lists are a type of linked list in which each node includes pointers to both the subsequent and previous nodes. The last node points back to the first node, while the first node points to the last, forming a circular structure.

Node Structure:

In a doubly circular linked list, a node consists of three components:

• Data: Holds the value of the element.
• Next: A reference to the next node in the sequence.
• Previous: A reference to the previous node in the sequence.

Code Example:

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

class DoublyCircularLinkedList:
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 = new_node # Circular linking
new_node.prev = new_node # Circular linking
else:
last_node = self.head.prev
last_node.next = new_node
new_node.prev = last_node
new_node.next = self.head
self.head.prev = new_node

def display_forward(self):
if self.head is None:
print("Empty Doubly Circular Linked List")
return
current = self.head
while True:
print(current.data, end=" -> ")
current = current.next
if current == self.head:
break
print("(Head)")

def display_backward(self):
if self.head is None:
print("Empty Doubly Circular Linked List")
return
current = self.head.prev
while True:
print(current.data, end=" -> ")
current = current.prev
if current == self.head.prev:
break
print("(Tail)")

# Example Usage
if __name__ == "__main__":
linked_list = DoublyCircularLinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)
print("Forward traversal:")
linked_list.display_forward()
print("Backward traversal:")
linked_list.display_backward()

Output:

Forward traversal:

1 -> 2 -> 3 -> (Head)

Backward traversal:

3 -> 2 -> 1 -> (Tail)

Comparison of Linked List Types

Here is a comparative analysis of the types of linked lists to aid in understanding their distinct features and applications.

Final Words

Learning the different types of linked lists is essential to becoming proficient with data structures and algorithms in programming. Every form of linked list has its own set of benefits and uses, ranging from the simplicity of singly linked lists to the adaptability of doubly circular linked lists. Programmers can choose the best linked list for their applications by carefully examining each one's features, performance comparisons, and use case scenarios. Studying linked list algorithms in data structure develops a greater understanding of the beauty and complexity of data structures, in addition to improving programming abilities.

FAQs

1. What are the four types of linked list?

The four types of linked lists include singly, doubly, circular, and doubly circular linked lists.

2. What is a linked list and its types in C?

A linked list in C is a data structure where elements are stored in nodes, each containing a data field and a pointer to the next node. Types include singly, doubly, circular, and doubly circular.

3. What are the two ways of a linked list?

The two ways of implementing linked lists are: using arrays of structures or dynamically allocating memory for each node.

4. What is a singly linked list and its types?

It is a sequence of nodes where each node points to the next node. There are different types of singly linked lists including standard and sorted singly linked lists.

5. What is a full linked list?

A full linked list is a term often used to refer to a linked list with no empty nodes, meaning every node contains data.

6. What data type is a linked list?

In most programming languages, a linked list is typically represented by a pointer to a structure or class defining the nodes.

7. What is a singly and doubly linked list?

Singly linked lists have nodes that contain a single pointer to the next node, while doubly linked lists have nodes with pointers to both the next and previous nodes.

8. What is a doubly linked list with an example?

It is a type of linked list, in which each node has pointers to both the next and previous nodes. Example: 1 <-> 2 <-> 3.

9. What is the difference between a linked list and a singly linked list?

The main difference between a linked list and a singly linked list is that a linked list can refer to any type of linked list, while a singly linked list specifically refers to a list where each node has only one pointer to the next node.