DSA : Types of Linked List

What is a Linked List?

A linked list is a fundamental data structure in computer science that consists of a sequence of elements, called nodes, where each node contains two main components: the data and a reference (or link) to the next node in the sequence.

Unlike arrays, linked lists do not store their elements in contiguous memory locations, which allows for dynamic memory allocation and efficient insertion and deletion of elements.

Types of Linked Lists

Singly Linked List

It is the most basic type of linked list, with each node containing some data and a pointer to the following node of the same data type.

Each node points to the next node in the sequence. The last node points to null. The nodes in a singly linked list are not stored in contiguous memory locations, allowing for dynamic memory allocation, efficient insertions and deletions.

In a singly linked list, each node contains a single link pointing to the following node in the sequence:

Head -> [ Data | Next ] -> [ Data | Next ] -> ... -> [ Data | Next ] -> None

Below is an example of a singly linked list in Python:

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

Building a Simple Linked List

To show how a linked list works, let’s create a simple singly linked list with a few nodes:

# Define the node
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

# Initialize the nodes
node1 = Node('A')
node2 = Node('B')
node3 = Node('C')

# Link the nodes
node1.next = node2
node2.next = node3

# Now, node1 is the head of the linked list
head = node1

Traversing the Linked List

To traverse a linked list, you start from the head and follow the links:

current_node = head
while current_node is not None:
    print(current_node.data)
    current_node = current_node.next

This code will output:

A
B
C

Time Complexity: O(N)
Auxiliary Space: O(N)

Doubly Linked List

In the doubly linked list, each node has two links: one pointing to the next node and one to the previous node:

Head -> [ Prev | Data | Next ] <-> [ Prev | Data | Next ] <-> ... <-> [ Prev | Data | Next ] -> None

Here’s how a doubly linked list node might be defined:

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

Circular Linked List

In a circular linked list, the last node points back to the first node, creating a circular structure:

Head -> [ Data | Next ] -> [ Data | Next ] -> ... -> [ Data | Next ] -> Head

An example of a node in a circular linked list:

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

Conclusion

The structure of a linked list, with its nodes containing data and links, provides a flexible and dynamic way to manage collections of data. Whether singly, doubly, or circular, linked lists offer efficient memory usage and facilitate easy insertion and deletion of elements. Understanding these fundamental structures is key to mastering more complex data structures and algorithms.