8.1. Singly Linked Lists

Singly linked lists are a type of data structure that is made up of nodes that are created using self-referential structures. Each node contains a value and a reference to the next node in the sequence. The first node is called the head and the last node is called the tail. The tail node points to a null reference. Singly linked lists are used to implement other data structures such as stacks, queues, and graphs.

Singly linked lists are useful because they allow for constant time insertion and deletion of elements at the beginning of the list. However, they do not allow for constant time access to elements in the middle of the list. To access an element in the middle of the list, you must traverse the list from the head node to the desired node.

In this notebook, we will implement a singly linked list in Python and demonstrate how to perform common operations on the list such as insertion, deletion, and traversal.

Fig. 8.3 A singly linked list is a data structure that is made up of nodes that are created using self-referential structures. Each node contains a value and a reference to the next node in the sequence.

8.1.1. Nodes

A Node is a recursive data structure that contains an instance attribute ‘next’ which refers to another object of type Node that is next in the sequence.

Instance attributes of Node that are NOT ‘next’ node_ are often referred to as the data or cargo, or payload of the node.

For example, a node with data “Monday” has a reference to the node with data “Tuesday”, which has a reference to the node with data “Wednesday”, and so on.

Fig. 8.4 A node in a linked list contains a reference to the next node in the sequence.

The code below shows a simple implementation of a Node class:

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

8.1.2. SinglyLinkedList Class

Next, we define a singly linked list class that contains a reference to the head node of the list. The singly linked list class provides methods for inserting, deleting, and traversing the list.

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

8.1.3. Traversal

To traverse the list, we start at the head node and follow the next references until we reach the end of the list (i.e., the tail node).

def traverse(self):
    
    # Start at the head node
    current = self.head
    
    # Traverse the list until the current node is None
    while current is not None:
        print(current.value)

        # Move to the next node
        current = current.next

Fig. 8.5 Traversal: Keep setting the current node to the next node until the current node is None.

8.1.4. Insertion

There are three common cases for inserting a new node into a singly linked list:

1. Prepend: Insert a new node at the beginning of the list.

2. Append: Insert a new node at the end of the list.

3. Insert: Insert a new node at a specific index in the list.

To insert a new node at the beginning of the list, we create a new node with the desired value and set its next reference to the current head of the list. Then, we update the head of the list to point to the new node.

Fig. 8.6 Prepend: Inserting a node at the front of a singly linked list.

To insert a new node at the end of the list, we create a new node with the desired value and set its next reference to the current head of the list. Then, we update the head of the list to point to the new node.

Fig. 8.7 Append: Inserting a node at the tail of a singly linked list.

def append(self, value):
    
    # Create a new node with the given value
    new_node = Node(value)

    
    # If the list is empty, set the new node as the head
    if self.head is None:
        self.head = new_node
        return

    
    # Otherwise, traverse the list to find the last node
    last = self.head
    while last.next:
        last = last.next
    

    # Set the next reference of the last node to the new node
    last.next = new_node

To insert a new node at a specific index in the list, we need to find the node that precedes the index where we want to insert the new node. We then update the next reference of the preceding node to point to the new node, and update the next reference of the new node to point to the node that was previously at the index.

Fig. 8.8 Insert: Inserting a node at a specific index in a singly linked list.

8.1.5. Deletion

Similar to insertion, there are three common cases for deleting a node from a singly linked list:

1. Delete head: Delete the first node in the list.

2. Delete tail: Delete the last node in the list.

3. Delete specific value: Delete a node with a specific value from the list.

To delete the head of the list, we simply update the head reference to point to the next node in the list.

Fig. 8.9 Delete head: Deleting the first node in a singly linked list.

To delete the tail of the list, we need to find the node that precedes the tail node. We then update the next reference of the preceding node to point to null.

Fig. 8.10 Delete tail: Deleting the last node in a singly linked list.

To delete a node with a specific value from the list, we need to find the node that precedes the node to be deleted. We then update the next reference of the preceding node to skip over the node to be deleted.

Fig. 8.11 Delete specific value: Deleting a node with a specific value from a singly linked list.

To delete a node from the list, we need to find the node that precedes the node to be deleted. We then update the next reference of the preceding node to skip over the node to be deleted.

def delete(self, value):

    # If the list is empty, return
    if self.head is None:
        return

    # If the head node has the value to be deleted, update the head to point to the next node
    current = self.head
    if current.value == value:
        self.head = current.next
        
    else:
        # Traverse the list to find the node with the value to be deleted
        while current.next is not None:
            if current.next.value == value:

                # Update the next reference of the current node to skip over the node to be deleted
                current.next = current.next.next
                break

            current = current.next

8.1.6. Analysis

The time complexity of inserting or deleting a node from a singly linked list is O(n) in the worst case, where n is the number of nodes in the list. This is because we may need to traverse the entire list to find the node to be inserted or deleted.

The space complexity of a singly linked list is O(n), where n is the number of nodes in the list. This is because we need to store a reference to each node in the list.

# Reverse a linked list

def reverse_linked_list(linked_list):
    prev = None
    current = linked_list.head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    linked_list.head = prev
    return linked_list