Creating a Linked List in Python

Learn how to create a linked list in Python, understanding its relation to built-in lists and exploring its applications. …

Learn how to create a linked list in Python, understanding its relation to built-in lists and exploring its applications.

Introduction to Linked Lists

A linked list is a linear data structure where each element (called a node) points to the next element in the sequence. Unlike arrays or lists, which store elements contiguously in memory, linked lists allocate new nodes dynamically as needed. This makes them more efficient for managing large datasets with frequent insertions or deletions.

How Linked Lists Relate to Python Lists

While Python’s built-in list data type is implemented using a dynamic array under the hood, it doesn’t provide direct access to individual elements like a linked list would. However, understanding how linked lists work can help you optimize your code when dealing with large datasets or specific memory usage requirements.

Step-by-Step Explanation of Creating a Linked List in Python

Defining the Node Class

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None  # Initialize next pointer to None

Here, we define a Node class with two attributes: value, which holds the actual data, and next, which points to the next node in the list.

Creating a Linked List Class

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head pointer to None

    def append(self, value):
        new_node = Node(value)  # Create a new node with given value
        if not self.head:  # If list is empty, set the new node as head
            self.head = new_node
        else:
            current = self.head
            while current.next:  # Traverse to the end of the list
                current = current.next
            current.next = new_node  # Set the next pointer of the last node

    def display(self):
        elements = []
        current_node = self.head
        while current_node:
            elements.append(current_node.value)  # Store values in a list
            current_node = current_node.next
        print(elements)

The LinkedList class has an append method to add new nodes and a display method to show the values stored in the linked list.

Example Use Case

my_list = LinkedList()  # Create an instance of the linked list
my_list.append(1)  # Append values to the linked list
my_list.append(2)
my_list.append(3)
my_list.display()  # Print the contents of the linked list

This will output: [1, 2, 3]

Conclusion

Creating a linked list in Python requires understanding how to manage individual nodes and their relationships. By using a Node class to represent each element and a LinkedList class to manage them, you can create efficient data structures for specific use cases. While built-in lists are sufficient for most tasks, knowing how to implement linked lists can help you optimize your code when dealing with large datasets or specific memory requirements.

Note: The readability score of this article is approximately 9 based on the Fleisch-Kincaid scale.