Implementation of Singly Linked List in Python Programming Language

A singly linked list is a fundamental data structure in computer science that consists of a sequence of elements, called nodes. Each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists don’t store elements in contiguous memory locations, making them more flexible for dynamic data management.

Below is how a singly linked list looks like:

A
A
B
B
C
C
Head Node
Head Node
Tail Node
Tail Node
D
DText is not SVG - cannot display

This article explores the structure and python implementation of singly linked lists, including key operations like insertion, deletion, searching, and traversal. It also covers time and space complexity analysis. We’ll start by declaring the base classes for the singly linked list, and then implement all the basic operations.

Prerequisites: Basics of Linked List Data Structure

Implementing the Singly Linked List Class

To implement a singly linked list in Python, we need to create two classes: SinglyLinkedNode and SinglyLinkedList.

SinglyLinkedNode Class

The SinglyLinkedNode class represents the structure of all individual nodes present in the Singly Linked list:

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

The purpose of each field in the structure is as follows:

  • data: Stores the actual value of the node.
  • next: A reference to the next node in the list. Its value is initially set to None, indicating that there are no nodes after this node.

SinglyLinkedList Class

The SinglyLinkedList class manages the entire list:

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

The purpose of each field in the structure is as follows:

  • head: Points to the first node in the list. Its value is initially set to None, indicating an empty list.
  • size: Keeps track of the number of nodes in the list.

This base implementation of linked list class provides a foundation for adding more complex operations like insertion, deletion, and traversal, which we’ll explore in the following sections.

Implementing Basic Operations for Singly Linked List

insert_at_beginning

This operation adds a new node at the start of the list and makes the newly added node the new head of the singly linked list.

Algorithm:

  1. Create a new node with the given data.
  2. Set the new node’s next pointer to the current head.
  3. Update the head to point to the new node.
  4. Increment the size of the list.
  • Time Complexity: O(1) (constant time, as it only involves updating a few pointers)
  • Space Complexity: O(1) (only creates one new node, regardless of list size)
def insert_at_beginning(self, data):
  new_node = SinglyLinkedNode(data)
  new_node.next = self.head
  self.head = new_node
  self.size += 1

insert_at_end

This operation appends a new node to the end of the singly linked list.

Algorithm:

  1. Create a new node with the given data.
  2. If the list is empty, make the new node the head.
  3. Otherwise, traverse to the last node and set its next pointer to the new node.
  4. Increment the size of the list.
  • Time Complexity: O(n), where n is the number of nodes in the list (need to traverse the entire list to reach the end)
  • Space Complexity: O(1) (only creates one new node, regardless of list size)
def insert_at_end(self, data):
  new_node = SinglyLinkedNode(data)
  if not self.head:
    self.head = new_node
  else:
    current = self.head
    while current.next:
      current = current.next
    current.next = new_node
  self.size += 1

If you need to optimize the time complexity of this operation, maintaining a tail pointer is an option. By keeping track of the last node in the list and caching it, you can reduce the time complexity from O(n) to O(1). This approach allows for constant-time insertion at the end of the list, regardless of its size, making it particularly efficient for large lists or frequent end insertions.

delete_node

This operation removes a specific node from the singly linked list.

Algorithm:

  1. Check if the list is empty. If so, return without doing anything.
  2. Check if the head node contains the data to be deleted:
    • If yes, update the head to point to the next node.
    • Decrement the size of the list.
    • Return from the function.
  3. Traverse the list to find the node to delete and its previous node:
    • Start from the head and move to the next node.
    • Continue until we find a node with the matching data or reach the end of the list.
  4. If a node with matching data is found:
    • Update the previous node’s next pointer to skip the node to be deleted.
    • Decrement the size of the list.
  • Time Complexity: O(n), where n is the number of nodes in the list (may need to traverse the entire list to find the node)
  • Space Complexity: O(1) (only uses a few temporary variables, regardless of list size)
def delete_node(self, data):
  if not self.head:
    return

  if self.head.data == data:
    self.head = self.head.next
    self.size -= 1
    return

  current = self.head
  while current.next and current.next.data != data:
    current = current.next

  if current.next:
    current.next = current.next.next
    self.size -= 1

Note that it is possible to have multiple nodes with the same value. In such cases, the above implementation deletes only the first node with the matching value. You can also implement a similar method that takes in the actual linked list node as an input and deletes it from the list.

search_node

This operation searches for a node with a given value.

Algorithm:

  1. Traverse the list from the head.
  2. Compare each node’s data with the search value.
  3. Return the node if found, or None if not found.
  • Time Complexity: O(n), where n is the number of nodes in the list (may need to traverse the entire list to find the node)
  • Space Complexity: O(1) (only uses a single temporary variable, regardless of list size)
def search_node(self, data):
  current = self.head
  while current:
    if current.data == data:
      return current
    current = current.next
  return None

Note that the above implementation returns only the first matching node. You can extend the implementation as shown below to return all the nodes matching the given data:

def search_all_nodes(self, data):
  result = []
  current = self.head
  while current:
    if current.data == data:
      result.append(current)
    current = current.next
  return result

This implementation allows you to find all occurrences of a specific value in the linked list, which can be useful in scenarios where duplicate values are allowed and you need to process all instances of a particular value.

get_size

This operation returns the total number of nodes in the list.

Algorithm:

  1. Return the size attribute of the list.
  • Time Complexity: O(1) (constant time, as it simply returns a pre-computed value)
  • Space Complexity: O(1) (no additional space used)
def get_size(self):
  return self.size

This operation displays all elements in the list sequentially.

Algorithm:

  1. Traverse the list from the head.
  2. Print each node’s data.
  • Time Complexity: O(n), where n is the number of nodes in the list (needs to visit every node once)
  • Space Complexity: O(1) (only uses a single temporary variable, regardless of list size)
def print_list(self):
  current = self.head
  while current:
    print(current.data, end=" -> ")
    current = current.next
  print("None")

Overall Implementation with Example Usage

Here’s a complete implementation of the singly linked list class along with example usage:


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

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

  def insert_at_beginning(self, data):
    new_node = SinglyLinkedNode(data)
    new_node.next = self.head
    self.head = new_node
    self.size += 1

  def insert_at_end(self, data):
    new_node = SinglyLinkedNode(data)
    if not self.head:
      self.head = new_node
    else:
      current = self.head
      while current.next:
        current = current.next
      current.next = new_node
    self.size += 1

  def delete_node(self, data):
    if not self.head:
      return

    if self.head.data == data:
      self.head = self.head.next
      self.size -= 1
      return

    current = self.head
    while current.next and current.next.data != data:
      current = current.next

    if current.next:
      current.next = current.next.next
      self.size -= 1

  def search_node(self, data):
    current = self.head
    while current:
      if current.data == data:
        return current
      current = current.next
    return None

  def get_size(self):
    return self.size

  def print_list(self):
    current = self.head
    while current:
      print(current.data, end=" -> ")
      current = current.next
    print("None")

# Example usage
if __name__ == "__main__":
  # Create a new singly linked list
  my_list = SinglyLinkedList()

  # Insert elements at the beginning
  my_list.insert_at_beginning(3)
  my_list.insert_at_beginning(2)
  my_list.insert_at_beginning(1)

  print("After inserting 1, 2, 3 at the beginning:")
  my_list.print_list()  # Output: 1 -> 2 -> 3 -> None

  # Insert elements at the end
  my_list.insert_at_end(4)
  my_list.insert_at_end(5)

  print("After inserting 4 and 5 at the end:")
  my_list.print_list()  # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None

  # Delete a node
  my_list.delete_node(3)

  print("After deleting node with value 3:")
  my_list.print_list()  # Output: 1 -> 2 -> 4 -> 5 -> None

  # Search for a node
  found_node = my_list.search_node(4)
  print(f"Searched for 4, found: {found_node.data if found_node else 'Not found'}")

  # Get the size of the list
  print(f"Size of the list: {my_list.get_size()}")

This implementation demonstrates the creation of a singly linked list and various operations such as insertion at the beginning and end, deletion, searching, and printing the list. The example usage shows how to create a list, add elements, delete a node, search for a value, and get the size of the list.

When you run this code, you’ll see the list’s state after each operation, allowing you to visualize how the singly linked list changes with different operations.