Working with Linked Lists in Python

Overview of Linked Lists

Linked lists are a fundamental data structure in computer science and an important concept to understand for any programmer. A linked list is a collection of nodes, where each node contains a data element and a reference (or link) to the next node in the list. Unlike arrays, linked lists do not require contiguous memory allocation, which makes them more flexible and efficient for certain operations.

There are different types of linked lists, such as singly linked lists, doubly linked lists, and circular linked lists. In this article, we will focus on singly linked lists, where each node only has a reference to the next node in the list.

Related Article: How to Use the main() Functions In Python

Creating a Node in a Linked List

To create a linked list, we first need to understand how to create a node. A node is a basic building block of a linked list and contains two main components: the data element and the reference to the next node.

In Python, we can define a Node class to represent a node in a linked list. Here's an example:

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

In this example, the __init__ method initializes the data element and sets the next reference to None. The data parameter represents the value of the data element stored in the node.

Inserting Elements into a Linked List

Once we have a node class, we can start building a linked list by inserting elements into it. There are several ways to insert elements into a linked list, but the most common methods are inserting at the beginning, at the end, or at a specific position in the list.

To insert an element at the beginning of a linked list, we need to create a new node with the desired data and update the next reference of the new node to point to the current head of the list. Here's an example:

def insert_at_beginning(head, data):    new_node = Node(data)    new_node.next = head    head = new_node    return head

In this example, the insert_at_beginning function takes the current head of the list and the data of the new node as parameters. It creates a new node with the given data, updates the next reference of the new node to point to the current head, and finally updates the head of the list to be the new node.

To insert an element at the end of a linked list, we need to traverse the list until we reach the last node, and then create a new node with the desired data and update the next reference of the last node to point to the new node. Here's an example:

def insert_at_end(head, data):    new_node = Node(data)    if head is None:        head = new_node    else:        current = head        while current.next is not None:            current = current.next        current.next = new_node    return head

In this example, the insert_at_end function takes the current head of the list and the data of the new node as parameters. It checks if the list is empty (i.e., the head is None), and if so, sets the head to be the new node. Otherwise, it traverses the list until it reaches the last node, and then updates the next reference of the last node to point to the new node.

To insert an element at a specific position in a linked list, we need to traverse the list until we reach the position before the desired position, and then create a new node with the desired data and update the next reference of the new node to point to the node at the desired position. Here's an example:

def insert_at_position(head, data, position):    if position == 0:        new_node = Node(data)        new_node.next = head        head = new_node    else:        current = head        for _ in range(position - 1):            current = current.next            if current is None:                raise IndexError("Position out of range")        new_node = Node(data)        new_node.next = current.next        current.next = new_node    return head

In this example, the insert_at_position function takes the current head of the list, the data of the new node, and the position as parameters. If the position is 0, it inserts the new node at the beginning of the list. Otherwise, it traverses the list until it reaches the position before the desired position, and then inserts the new node at the desired position.

Deleting a Node from a Linked List

Deleting a node from a linked list involves updating the next reference of the previous node to skip the node to be deleted. There are several ways to delete a node from a linked list, but the most common methods are deleting the first occurrence of a specific value, deleting a node at a specific position, and deleting the entire list.

To delete the first occurrence of a specific value from a linked list, we need to traverse the list until we find the node with the desired value, update the next reference of the previous node to skip the node to be deleted, and finally delete the node. Here's an example:

def delete_by_value(head, value):    if head is None:        return head    if head.data == value:        head = head.next        return head    current = head    while current.next is not None:        if current.next.data == value:            current.next = current.next.next            return head        current = current.next    return head

In this example, the delete_by_value function takes the current head of the list and the value to be deleted as parameters. It checks if the list is empty (i.e., the head is None), and if so, returns the head unchanged. Otherwise, it traverses the list until it finds the node with the desired value, updates the next reference of the previous node to skip the node to be deleted, and returns the head.

To delete a node at a specific position in a linked list, we need to traverse the list until we reach the position before the desired position, update the next reference of the previous node to skip the node to be deleted, and finally delete the node. Here's an example:

def delete_by_position(head, position):    if head is None:        return head    if position == 0:        head = head.next        return head    current = head    for _ in range(position - 1):        current = current.next        if current is None or current.next is None:            raise IndexError("Position out of range")    current.next = current.next.next    return head

In this example, the delete_by_position function takes the current head of the list and the position to be deleted as parameters. It checks if the list is empty (i.e., the head is None), and if so, returns the head unchanged. If the position is 0, it updates the head to skip the first node and returns the head. Otherwise, it traverses the list until it reaches the position before the desired position, updates the next reference of the previous node to skip the node to be deleted, and returns the head.

To delete the entire list, we simply set the head to None, which effectively disconnects all the nodes from each other and frees up the memory occupied by the list.

Related Article: How to do Incrementing in Python

Traversing a Linked List

Traversing a linked list involves visiting each node in the list and performing some operation on it. The most common operation is printing the data element of each node.

To traverse a linked list, we start from the head and repeatedly follow the next references until we reach the end of the list (i.e., the next reference of the current node is None). Here's an example:

def traverse_list(head):    current = head    while current is not None:        print(current.data)        current = current.next

In this example, the traverse_list function takes the head of the list as a parameter. It initializes a current variable to the head, and then repeatedly prints the data element of the current node and updates the current variable to the next node until the current node is None.

Working with Singly Linked Lists

Singly linked lists are a type of linked list where each node only has a reference to the next node in the list. This simplicity makes singly linked lists easier to implement and understand compared to other types of linked lists.

Singly linked lists have several advantages and disadvantages. One advantage is that inserting or deleting a node at the beginning of the list can be done in constant time, as it only involves updating the next reference of the new or previous node. However, inserting or deleting a node at the end of the list or at a specific position requires traversing the list, which takes linear time.

Another advantage of singly linked lists is that they can handle dynamic memory allocation more efficiently than arrays. Since each node only requires memory for its data element and the next reference, memory can be allocated and deallocated on demand, which reduces memory wastage.

On the other hand, one disadvantage of singly linked lists is that accessing nodes by index is not efficient, as it requires traversing the list from the beginning until the desired position. Additionally, singly linked lists require more memory compared to arrays, as each node needs to store a reference to the next node.

Additional Resources