Implement a Linked List in Python

Linked lists are fundamental data structures in computer science, offering a flexible alternative to arrays. Unlike arrays, which store elements contiguously in memory, linked lists store elements in nodes, each pointing to the next node in the sequence. This allows for efficient insertion and deletion of elements, even in the middle of the list. This post will guide you through implementing a singly linked list in Python.

Understanding the Node

The building block of a linked list is the Node. Each node contains two key components:

• Data: The value stored in the node.
• Next: A pointer (reference) to the next node in the sequence. The last node’s next pointer is typically None.

Here’s how you can represent a node in Python:

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

Building the Linked List

Now, let’s create the linked list class itself. This class will manage the nodes and provide methods for common linked list operations.

class LinkedList:
    def __init__(self):
        self.head = None  # The head points to the first node

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

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete_node(self, key):
        current = self.head
        if current and current.data == key:
            self.head = current.next
            current = None
            return

        prev = None
        while current and current.data != key:
            prev = current
            current = current.next

        if current is None:
            return

        prev.next = current.next
        current = None


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

This LinkedList class includes methods for:

• append(data): Adds a new node to the end of the list.
• prepend(data): Adds a new node to the beginning of the list.
• delete_node(key): Deletes a node with the specified key (data).
• print_list(): Prints the list’s contents.

Usage Example

Let’s see the LinkedList class in action:

linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.prepend(0)
linked_list.print_list()  # Output: 0 -> 1 -> 2 -> 3 -> None
linked_list.delete_node(2)
linked_list.print_list()  # Output: 0 -> 1 -> 3 -> None

This demonstrates the basic functionality of adding, deleting, and traversing a linked list. You can extend this class to include more complex operations like searching, inserting at a specific index, and reversing the list. Remember to handle edge cases, such as an empty list, for code. Further exploration could involve implementing doubly linked lists or circular linked lists, which offer additional functionalities.