Mastering Linked Lists: Understanding, Implementing, and Manipulating in Python

Introduction to Linked Lists

Welcome to our intriguing session for today! We're diving into an essential topic in computer science and data structures: Linked Lists . These structures comprise a sequence of nodes . Each node holds some data and a reference (a link) to the next node, thus forming a chain-like structure. The concept of linked lists is leveraged in many real-world scenarios. For instance, in a music playlist where songs can be dynamically added, deleted, or reordered, linked lists serve as an excellent solution thanks to their efficient operations.

Understanding Linked Lists

A linked list is a collection of nodes, each acting as a container for its data and a pointer (link) to the next node in the list. This link greatly facilitates sequential traversal through the list. Here is a simple visualization of a node: class Node {Data Pointer to Next Node} class Node {Data Pointer to Next Node} A node consists of two parts: Data, which contains the stored value (that could be any type such as number, string, etc.), and Pointer to Next Node, which holds the link to the next node in the sequence. When a node is initially created, next is set to None because there is no subsequent node to point to. Think of it like a treasure hunt game, where each clue leads to the next one, and the chain continues until we reach the final destination.

Linked Lists vs Arrays

O(1)

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Deletion

Calling delete(value) searches the list for a node with the given value. If the node is found, it is removed from the list, and the links are fixed to keep the list connected.

Python

# Defining the delete method
def delete(self, value):
    temp = self.head

# Defining the delete method
def delete(self, value):
    temp = self.head

The delete() method begins by setting a temp reference to the head of the linked list. This temp reference will be used to traverse the list.

Python

    if (temp is not None):
         if temp.value == value:
            self.head = temp.next
            temp = None
            return

    if (temp is not None):
         if temp.value == value:
            self.head = temp.next
            temp = None
            return

The first if statement checks if the head of the list is not None or, in other words, if the list is not empty. Then, inside the if block, it checks if the head node is the node to be deleted (i.e., its value matches the value parameter). If it is, the head is updated to be the next node in the list (potentially None if the head was the only node in the list), and then the old head node is deleted by setting temp to None.

Python

    while (temp is not None):
        if temp.value == value:
            break
        prev = temp
        temp = temp.next

    while (temp is not None):
        if temp.value == value:
            break
        prev = temp
        temp = temp.next

If the head node is not the one to be deleted, the list is traversed in search of the node. The prev reference is updated as the current node before temp moves on to the next one. If at any point during the traversal, a node with a value matching the value parameter is found, the loop breaks, leaving temp pointing to the node to delete and prev pointing to its predecessor.

Python

    if temp == None:
        return
    prev.next = temp.next
    temp = None

    if temp == None:
        return
    prev.next = temp.next
    temp = None

After traversal, if temp is None, this means the node to delete was not found, and the function returns. Otherwise, the predecessor's next reference (which currently points to the to-be-deleted node) is updated to point to the successor of the node to be deleted, thus excluding it from the list. The node is then deleted by setting temp to None.

The delete() method doesn't return any value. It either successfully deletes a node or quietly returns if the requested node is not found in the list.

Introduction to Linked Lists

Understanding Linked Lists

Linked Lists vs Arrays

Join the 1M+ learners on CodeSignal

Implementing a Linked List in Python

Complexity Analysis

Diving Deep into Linked List Manipulation

Insertion

Deletion

Traversal

Conclusion

Ready to Practice?