12.3 Linked Lists in Python

NicePython

— 3 min read

A linked list is a collection of elements, called nodes, where each node contains a reference (or pointer) to the next node in the sequence. Linked lists are dynamic and can grow or shrink in size easily because nodes are not stored in contiguous memory locations.

There are two main types of linked lists:

  • Singly Linked List: Each node points to the next node.
  • Doubly Linked List: Each node points to both the next and the previous node.

12.3.1 Singly Linked List

In a singly linked list, each node contains two parts:

  1. Data: The value stored in the node.
  2. Next: A reference (or pointer) to the next node in the list.

Example: Implementing a Singly Linked List

class Node:
    def __init__(self, data):
        self.data = data  # Store the data (value)
        self.next = None  # Store a reference to the next node (default is None)

class SinglyLinkedList:
    def __init__(self):
        self.head = None  # The list starts empty

    # Insert a new node at the beginning of the list
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    # Insert a new node at the end of the list
    def insert_at_end(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

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

# Example usage
sll = SinglyLinkedList()
sll.insert_at_beginning(3)
sll.insert_at_beginning(2)
sll.insert_at_end(4)
sll.insert_at_end(5)
sll.print_list()  # Output: 2 -> 3 -> 4 -> 5 -> None

In this example:

  • The Node class defines the structure of each node, with data holding the node's value and next pointing to the next node.
  • The SinglyLinkedList class allows us to manipulate the list by inserting new nodes at the beginning or end and printing the list.

Advantages of Singly Linked Lists:

  • Dynamic size: Can grow or shrink easily.
  • Efficient insertions/removals: Particularly at the beginning.

Disadvantages of Singly Linked Lists:

  • No backward traversal: You can only traverse from the head to the tail.
  • Random access is inefficient: Finding an element by index requires traversing the list.

12.3.2 Doubly Linked List

In a doubly linked list, each node contains three parts:

  1. Data: The value stored in the node.
  2. Next: A reference to the next node.
  3. Prev: A reference to the previous node.

This allows traversal in both directions.

Example: Implementing a Doubly Linked List

class Node:
    def __init__(self, data):
        self.data = data  # Value of the node
        self.next = None  # Pointer to the next node
        self.prev = None  # Pointer to the previous node

class DoublyLinkedList:
    def __init__(self):
        self.head = None  # List starts empty

    # Insert a node at the beginning
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        if self.head is not None:
            self.head.prev = new_node
        self.head = new_node

    # Insert a node at the end
    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node
        new_node.prev = current

    # Print the list from head to tail
    def print_list(self):
        current = self.head
        while current:
            print(current.data, end=" <-> ")
            current = current.next
        print("None")

# Example usage
dll = DoublyLinkedList()
dll.insert_at_beginning(2)
dll.insert_at_end(3)
dll.insert_at_end(4)
dll.print_list()  # Output: 2 <-> 3 <-> 4 <-> None

In this example:

  • prev in each node allows traversal in both directions, forward (using next) and backward (using prev).
  • The DoublyLinkedList class provides methods to insert nodes and print the list in a readable way.

Advantages of Doubly Linked Lists:

  • Traversal in both directions.
  • Easier deletion of nodes, especially when the node is in the middle.

Disadvantages of Doubly Linked Lists:

  • More memory usage: Each node requires an extra pointer (prev).
  • Slightly more complex implementation than singly linked lists.

12.3.3 Summary

  • Linked Lists: Dynamic data structures with nodes pointing to the next (and possibly previous) nodes. Suitable for dynamic memory allocation and efficient insertions/deletions.
    • Singly Linked List: Each node points to the next node.
    • Doubly Linked List: Each node points to both the next and previous nodes.

By understanding and implementing linked lists, you can efficiently solve problems involving dynamic data storage, hierarchical relationships, and sorted data management.

Read more