Linked Lists in Python

What is a Linked List?

Linked lists are fundamental data structures in computer science, offering dynamic storage for data elements. Unlike arrays, which store elements sequentially in memory, linked lists use nodes to store data and pointers to link to the next node in the sequence. This flexibility makes them efficient for dynamic data management. In this article, we'll explore linked lists in Python, covering their implementation, basic operations like insertion and deletion, and how to reverse a linked list.

Implementing a Linked List in Python

To begin, let's define a Node class for our linked list:

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

Here, each Node contains some data (self.data) and a pointer (self.next) to the next node in the list. If self.next is None, it indicates the end of the list.

Next, we create a LinkedList class to manage our nodes:

class LinkedList:
    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 print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" -> ")
            current_node = current_node.next
        print("None")

    def length(self):
        current = self.head
        length = 0
        while current:
            length += 1
            current = current.next
        return length

    def reverse(self):
        prev = None
        current = self.head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        self.head = prev

    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

Using the Linked List

Let's see how we can use this implementation:

Append Operation

# Creating a linked list
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.append(4)

# Printing the linked list
print("Linked List:")
llist.print_list()

# Length of the linked list
print(f"Length of the linked list: {llist.length()}")

Delete Operation

# Deleting a node
llist.delete_node(3)
print("Linked List after deleting node with data=3:")
llist.print_list()

Reverse Operation

# Reversing the linked list
print("Reversed Linked List:")
llist.reverse()
llist.print_list()

Conclusion

We've explored the basics of linked lists in Python, from defining the structure using classes to implementing common operations like insertion, deletion, and reversal. Linked lists are powerful tools for managing dynamic data efficiently, offering flexibility and ease of modification compared to static arrays. Experiment with the code provided to deepen your understanding and explore further applications in your projects.

Linked lists form the building blocks of many advanced data structures and algorithms, making them essential knowledge for any programmer. Mastering their concepts and implementations will enhance your ability to tackle complex programming challenges effectively.