Working With Linked Lists in Python

Linked Lists in Python

Have you ever wondered how data is stored and accessed in programming? Linked lists are a commonly used data structure in computer science used to store and manage data collections. In this blog, we will explore the concept of linked lists in Python, including what they are, how they work, and how to use them in your code.

Linked lists are a type of data structure that allows you to store and manipulate collections of data. Unlike arrays, which store data in contiguous blocks of memory, linked lists store data in nodes that point to each other. This makes linked lists more flexible and efficient for certain operations.

Definition of Linked Lists

A linked list is a data structure consisting of a group of nodes that together represent a sequence. Each node contains data and a pointer to the next node in the sequence. The linked list is a dynamic data structure, which means that it can grow or shrink in size during runtime. In Python, linked lists can be implemented using the built-in list data structure or by defining a custom Node class.

Advantages of Linked Lists

• Linked lists can be easily modified by adding or removing elements, unlike arrays, which require shifting elements.
• Linked lists can be used to implement other data structures, such as queues, stacks, and trees.
• Linked lists use less memory than arrays since they only allocate memory when a new element is added.

Disadvantages of Linked Lists

Linked lists require more memory than arrays since each element needs to store a reference to the next element.
Traversing a linked list can be slower than accessing an element in an array since the elements are not stored in contiguous memory.

Here are some key concepts to keep in mind when working with linked lists in Python:

• Nodes: A node is a basic unit of a linked list, containing both a value and a pointer to the next node in the list.
• Head: The head of a linked list is the first node in the list.
• Tail: The tail of a linked list is the last node in the list, and its next pointer points to null.
• Pointer: A pointer is a reference to another node in the list. In Python, pointers are implemented as variables that hold memory addresses.
• Singly Linked Lists: In a singly linked list, each node contains a single pointer to the next node in the list.
• Doubly Linked Lists: In a doubly linked list, each node contains two pointers – one to the next node in the list, and one to the previous node in the list.Creating a Linked List in Python:

Here is an example of how to create a linked list in Python:

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

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

    def add_node(self, value):
        new_node = Node(value)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = new_node

This code defines a Node class and a LinkedList class. The Node class contains a value and a next pointer, while the LinkedList class contains a head pointer. The add_node method adds a new node to the end of the list by iterating through the list until it finds the last node and setting its next pointer to the new node.

Traversing a Linked List:

To traverse a linked list, you simply start at the head of the list and follow the next pointers until you reach the end of the list.

Here is an example of how to traverse a linked list in Python:

class LinkedList:
    # ... same as before

    def traverse(self):
        current = self.head
        while current is not None:
            print(current.value)
            current = current.next

This code defines a traverse method that starts at the head of the list and iterates through each node in the list, printing its value.

Inserting and Deleting Nodes:

To insert a node into a linked list, you need to update the pointers of the surrounding nodes to point to the new node. To delete a node, you need to update the pointers of the surrounding nodes to bypass the node to be deleted.

Here is an example of how to insert and delete nodes in a linked list in Python:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    def print_list(self):
        current_node = self.head
        while current_node:
            print(current_node.data, end=" ")
            current_node = current_node.next
        print()
    
    def insert_at_beginning(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node
        
    def insert_at_end(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        current_node = self.head
        while current_node.next:
            current_node = current_node.next
        current_node.next = new_node
    
    def insert_after_node(self, prev_node, data):
        if not prev_node:
            print("Previous node is not in the list")
            return
        new_node = Node(data)
        new_node.next = prev_node.next
        prev_node.next = new_node
    
    def delete_node(self, key):
        current_node = self.head
        if current_node and current_node.data == key:
            self.head = current_node.next
            current_node = None
            return
        prev_node = None
        while current_node and current_node.data != key:
            prev_node = current_node
            current_node = current_node.next
        if current_node is None:
            return
        prev_node.next = current_node.next
        current_node = None

# Example usage
linked_list = LinkedList()
linked_list.insert_at_beginning(5)
linked_list.insert_at_end(6)
linked_list.insert_after_node(linked_list.head, 7)
linked_list.print_list()  # Output: 5 7 6
linked_list.delete_node(7)
linked_list.print_list()  # Output: 5 6

Output:

5 7 6
5 6

In this code, we define a Node class to represent a single node in a linked list. Each node has a data attribute to hold its value and a next attribute to reference the next node in the list.

We also define a LinkedList class to represent the linked list itself. The LinkedList class has a head attribute to hold the first node in the list.

We define several methods to manipulate the list:

• print_list: prints all the nodes in the list
• insert_at_beginning: inserts a new node at the beginning of the list
• insert_at_end: inserts a new node at the end of the list
• insert_after_node: inserts a new node after a given node in the list
• delete_node: deletes the first occurrence of a node with a given value from the list

In the example usage code at the bottom, we create a new linked list and insert some nodes. We then print the list, delete a node, and print the list again to demonstrate the functionality of the LinkedList class.

Time Complexity of Linked List Operations:

Understanding the time complexity of linked list operations is crucial for evaluating their performance. The time complexity of common operations in linked lists can be summarized as follows:

• Accessing an element at a specific index: O(n)
• Inserting a node at the beginning: O(1)
• Inserting a node at the end: O(n)
• Inserting a node at a specific index: O(n)
• Deleting a node at the beginning: O(1)
• Deleting a node at the end: O(n)
• Deleting a node at a specific index: O(n)
• Searching for an element: O(n)

Diagrams and Visualizations:

Visual representations and diagrams can greatly aid in understanding the structure and operations of linked lists. The following diagram illustrates a singly linked list with four nodes:

This diagram shows how each node contains data and a reference to the next node. The last node in the list points to None, indicating the end of the list.

Conclusion

Linked lists are a powerful data structure that can be used to store and manipulate collections of data in Python. By using the built-in list data structure or defining a custom Node class, it is easy to create and manipulate linked lists in Python. While linked lists have some advantages over arrays, they also have some disadvantages, and the choice of which data structure to use depends on the specific needs of the application.