What is a linked list in Python?

Question

Jayant Kumar · Accepted Answer

Table of Contents
Introduction
A linked list is a fundamental data structure used to store a collection of elements. Unlike arrays or lists, which store elements in contiguous memory locations, a linked list stores elements in nodes where each node points to the next (and possibly previous) node. This structure allows for efficient insertion and deletion operations.
What is a Linked List?
A linked list consists of a sequence of nodes, where each node contains:

Data: The value or information stored in the node.
Pointer/Reference: A reference to the next node in the sequence (and possibly to the previous node, depending on the type of linked list).

Types of Linked Lists

Singly Linked List

Each node has a reference to the next node.
The list is traversed from the head node to the end (null reference).

Doubly Linked List

Each node has references to both the next and previous nodes.
Allows traversal in both directions, from head to tail and vice versa.

Circular Linked List

The last node points back to the first node, creating a circular structure.
Can be singly or doubly linked.

Implementation Examples in Python
1. Singly Linked List
A singly linked list is implemented by defining a Node class and a LinkedList class that manages the nodes.
Example:
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

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

# Example usage
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)

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

2. Doubly Linked List
A doubly linked list is similar to a singly linked list but each node also has a reference to the previous node.
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 append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node
        new_node.prev = last_node

def display(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" &#x3C;-> ")
            current_node = current_node.next
        print("None")

# Example usage
dll = DoublyLinkedList()
dll.append(1)
dll.append(2)
dll.append(3)

dll.display()  # Output: 1 &#x3C;-> 2 &#x3C;-> 3 &#x3C;-> None

3. Circular Linked List
In a circular linked list, the last node points back to the first node, forming a circle.
Example:
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

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

def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
            return
        last_node = self.head
        while last_node.next != self.head:
            last_node = last_node.next
        last_node.next = new_node
        new_node.next = self.head

def display(self):
        if not self.head:
            print("Empty list")
            return
        current_node = self.head
        while True:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
            if current_node == self.head:
                break
        print("(back to head)")

# Example usage
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)

cll.display()  # Output: 1 -> 2 -> 3 -> (back to head)

Advantages of Linked Lists

Dynamic Size: Can grow or shrink in size dynamically, unlike arrays.
Efficient Insertions/Deletions: Insertions and deletions are more efficient compared to arrays, especially when inserting/removing elements from the middle.

Use Cases

Dynamic Memory Allocation: When the number of elements is not known in advance.
Implementing Other Data Structures: Used as building blocks for more complex data structures such as stacks, queues, and hash tables.

Conclusion
A linked list is a versatile data structure in Python that offers dynamic sizing and efficient insertions and deletions. Depending on the needs of your application, you can implement singly, doubly, or circular linked lists to manage your data effectively. Understanding the types and their implementations helps in choosing the right data structure for various programming tasks.

What is a linked list in Python?

Similar Questions