Data Structure: Singly Linked List in Python

Singly linked list is a linear collection of elements(nodes), connecting to the next element(node). We can always go to the next element(node) from any node, but can not go backward.

singly linked list overview
singly linked list overview

NOTE

In this article, we are discussing in detail, the implementation of Singly Linked List in Python.

Check the link below to check the details of Linked List and Singly Linked List-

Implementation

Here is the detailed implementation of Singly Linked List in Python, step-by-step –

Step #1: Node Class

Singly Linked List individual node
Singly Linked List individual node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
Python

Step #2: Linked List Class

Singly Linked List initial stage
Singly Linked List initial stage
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0
Python

Step #3: Push (Node to the end)

Singly Linked List Push
Singly Linked List Push
class SinglyLinkedList:
    # Other functionality
        
    # Push item to the end
    def push(self, data):
        # Create a new node
        node = Node(data)
        
        # If there is no head, that means the list is empty
        # Then make this new node as head
        if not self.head:
            self.head = node
        else:
            # Set the new node as the next of the current tail
            self.tail.next = node
            
        # Set the new node as tail
        self.tail = node
        
        # Increase length by 1
        self.length += 1
Python

Step #4: Pop (Last Node)

Singly Linked List Pop
Singly Linked List Pop
class SinglyLinkedList:
    # Other functionality
        
    # Pop item from the end
    def pop(self):
        # Return None if the list is empty
        if not self.head:
            return None
        
        current = self.head
        new_tail = current
        
        # Traverse through the list 
        # and get the second last item as new_tail
        while current.next:
            new_tail = current
            current = current.next
            
        # Set the new tail
        self.tail = new_tail
        
        # Set next of the new tail as None
        self.tail.next = None
        
        # Decrease the length by 1
        self.length -= 1
        
        # If there is no item left
        # then set the head and tail both as None
        if self.length == 0:
            self.head = None
            self.Tail = None
            
        # Return the node in the current variable
        return current          
Python

Step #5: Traverse all Nodes

class SinglyLinkedList:
    # Other functionality
        
    def traverse(self):
        current = self.head
        
        while current:
            print(current.data, end=" -> ")
            
            # Move to the next node
            current = current.next
            
Python

Step #6: Shift Head

class SinglyLinkedList:
    # Other functionality
        
    # Shift the head
    # and maek the second item as the head
    # Return the first item as result of shift
    def shift(self):
        # If the current head is None,
        # then return None
        if self.head is None:
            return None
        
        old_head = self.head
        
        # Set the next node as head
        self.head = old_head.next
        
        # Decrease the length by 1
        self.length -= 1
        
        if self.length == 0:
            self.tail = None
            
        # Set the next of old_head to None
        # and return the old_head
        old_head.next = None
        
        return old_head           
Python

Step #7: Unshift Head

class SinglyLinkedList:
    # Other functionality
        
    # Unshift head
    # Create new node and set that as head
    def unshift(self, data):
        # Create a new node from provided data
        new_head = Node(data)
        
        if self.head is None:
            self.tail = new_head
        else:
            new_head.next = self.head
            
        # Set the new_head as head of the list
        self.head = new_head
        
        # Increase size of the list by 1
        self.length += 1
        
        return new_head         
Python

Step #8: Get Node by Index

class SinglyLinkedList:
    # Other functionality
        
    # Get node by index(sequence numbers)
    # 0 based index (index starts from 0)
    def get(self, index):
        # Check if provided inex is valid
        # Return None if index is invalid
        if index < 0 or index >= self.length:
            return None
        
        selected_node = self.head
        
        # Start from head and go till the provided index
        for _ in range(index):
            selected_node = selected_node.next
            
        return selected_node
Python

Step #9: Set data at Node by Index

class SinglyLinkedList:
    # Other functionality
        
    # Set data of a specific node at specific index
    # 0 based index(index starts from 0)
    def set(self, index, data):
        node_at_index = self.get(index)
        
        # If item exists at index then return that
        if node_at_index is not None:
            node_at_index.data = data
            
            return True
        
        return False
Python

Step #10: Search by data

class SinglyLinkedList:
    # Other functionality
        
    # Search the list for specific data
    def search(self, data):
        current = self.head
        index = 0
        
        while current:
            if current.data == data:
                return index
            
            current = current.next
            index += 1
            
        return None
Python

Step #11: Insert Data at Specific Index

class SinglyLinkedList:
    # Other functionality
        
    # Insert new node at a specific index
    # 0 based index(index starts at 0)
    def insert(self, index, data):
        # Return false if index is out of range
        if index < 0 or index > self.length:
            return False
        
        # If index is the next element after tail
        # then just push item to the lsit
        if index == self.length:
            self.push(data)
            
            return True
        
        # If index is zero then unshift
        if index == 0:
            self.unshift(data)
            
            return True
        
        # Create new node and add it to the defined index
        new_node = Node(data)
        
        # Get the node after which this new node will be inserted
        prev_node = self.get(index - 1)
        
        # Add the new_node after the prev_node
        new_node.next = prev_node.next
        prev_node.next = new_node
        
        # Increase length by one
        self.length += 1
        
        return True
Python

Step #12: Remove Item from Specific Index

class SinglyLinkedList:
    # Other functionality
        
    # Reemove item at specific index
    def remove(self, index):
        # Return false if index is out of range
        if index < 0 or index >= self.length:
            return None
        
        if index == 0:
            return self.shift()
        
        if index == self.length - 1:
            return self.pop()
        
        prev_node = self.get(index - 1)
        node_to_remove = prev_node.next
        prev_node.next = prev_node.next.next
        
        # Decrease length by 1
        self.length -= 1
        
        return node_to_remove 
Python

Step #13: Reverse a Singly Linked List

class SinglyLinkedList:
    # Other functionality
        
    # Reverse a linked list
    def reverse(self):
        current_node = self.head
        prev_node = None
        next_node = None
        
        self.tail = self.head
        
        while current_node:
            next_node = current_node.next
            current_node.next = prev_node

            prev_node = current_node
            current_node = next_node

        self.head = prev_node
        
        return self
Python

I

Full Implementation Code

Here is the full implementation of Singly Linked List, with all the functionality.

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

class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0
        
    # Push item to the end
    def push(self, data):
        # Create a new node
        node = Node(data)
        
        # If there is no head, that means the list is empty
        # Then make this new node as head
        if not self.head:
            self.head = node
        else:
            # Set the new node as the next of the current tail
            self.tail.next = node
            
        # Set the new node as tail
        self.tail = node
        
        # Increase length by 1
        self.length += 1
        
    # Pop item from the end
    def pop(self):
        # Return None if the list is empty
        if not self.head:
            return None
        
        current = self.head
        new_tail = current
        
        # Traverse through the list 
        # and get the second last item as new_tail
        while current.next:
            new_tail = current
            current = current.next
            
        # Set the new tail
        self.tail = new_tail
        
        # Set next of the new tail as None
        self.tail.next = None
        
        # Decrease the length by 1
        self.length -= 1
        
        # If there is no item left
        # then set the head and tail both as None
        if self.length == 0:
            self.head = None
            self.Tail = None
            
        # Return the node in the current variable
        return current
    
    # Shift the head
    # and maek the second item as the head
    # Return the first item as result of shift
    def shift(self):
        # If the current head is None,
        # then return None
        if self.head is None:
            return None
        
        old_head = self.head
        
        # Set the next node as head
        self.head = old_head.next
        
        # Decrease the length by 1
        self.length -= 1
        
        if self.length == 0:
            self.tail = None
            
        # Set the next of old_head to None
        # and return the old_head
        old_head.next = None
        
        return old_head
            
    # Unshift head
    # Create new node and set that as head
    def unshift(self, data):
        # Create a new node from provided data
        new_head = Node(data)
        
        if self.head is None:
            self.tail = new_head
        else:
            new_head.next = self.head
            
        # Set the new_head as head of the list
        self.head = new_head
        
        # Increase size of the list by 1
        self.length += 1
        
        return new_head
        
    # Get node by index(sequence numbers)
    # 0 based index (index starts from 0)
    def get(self, index):
        # Check if provided inex is valid
        # Return None if index is invalid
        if index < 0 or index >= self.length:
            return None
        
        selected_node = self.head
        
        # Start from head and go till the provided index
        for _ in range(index):
            selected_node = selected_node.next
            
        return selected_node
    
    # Set data of a specific node at specific index
    # 0 based index(index starts from 0)
    def set(self, index, data):
        node_at_index = self.get(index)
        
        # If item exists at index then return that
        if node_at_index is not None:
            node_at_index.data = data
            
            return True
        
        return False
    
    # Insert new node at a specific index
    # 0 based index(index starts at 0)
    def insert(self, index, data):
        # Return false if index is out of range
        if index < 0 or index > self.length:
            return False
        
        # If index is the next element after tail
        # then just push item to the lsit
        if index == self.length:
            self.push(data)
            
            return True
        
        # If index is zero then unshift
        if index == 0:
            self.unshift(data)
            
            return True
        
        # Create new node and add it to the defined index
        new_node = Node(data)
        
        # Get the node after which this new node will be inserted
        prev_node = self.get(index - 1)
        
        # Add the new_node after the prev_node
        new_node.next = prev_node.next
        prev_node.next = new_node
        
        # Increase length by one
        self.length += 1
        
        return True
          
    # Reemove item at specific index
    def remove(self, index):
        # Return false if index is out of range
        if index < 0 or index >= self.length:
            return None
        
        if index == 0:
            return self.shift()
        
        if index == self.length - 1:
            return self.pop()
        
        prev_node = self.get(index - 1)
        node_to_remove = prev_node.next
        prev_node.next = prev_node.next.next
        
        # Decrease length by 1
        self.length -= 1
        
        return node_to_remove 
        
    # Reverse a linked list
    def reverse(self):
        current_node = self.head
        prev_node = None
        next_node = None
        
        self.tail = self.head
        
        while current_node:
            next_node = current_node.next
            current_node.next = prev_node

            prev_node = current_node
            current_node = next_node

        self.head = prev_node
        
        return self
    
    # Search the list for specific data
    def search(self, data):
        current = self.head
        index = 0
        
        while current:
            if current.data == data:
                return index
            
            current = current.next
            index += 1
            
        return None
        
    
    def traverse(self):
        current = self.head
        
        while current:
            print(current.data, end=" -> ")
            
            # Move to the next node
            current = current.next
            
Python

Demo

Here is the demo code for using the implemented functionality of Singly Linked List-

from singly_linked_list import SinglyLinkedList


big_box_list = SinglyLinkedList()

print("----------- Singly Linked List Push example -----------\n")

big_box_list.push("Big")
big_box_list.push("Box")
big_box_list.push("Code")

big_box_list.traverse()

print("\n\n----------- Singly Linked List Pop example -----------\n")

popped_item = big_box_list.pop()
print("Poppped item: ", popped_item.data)

popped_item = big_box_list.pop()
print("Poppped item: ", popped_item.data)

popped_item = big_box_list.pop()
print("Poppped item: ", popped_item.data)

print("Poppped item: ", big_box_list.pop())

# Push some items again
big_box_list.push("Big")
big_box_list.push("Box")
big_box_list.push("Code")

print("\n\n----------- Singly Linked List Shift example -----------\n")

print("Shift head from list: ", big_box_list.shift())

print("Shift head from list: ", big_box_list.shift())

print("\n\n----------- Singly Linked List Unshift example -----------\n")

print("Unshift - 'Box' | Result: ", big_box_list.unshift("Box"))
print("Unshift - 'Box' | Result: ", big_box_list.unshift("Big"))

print("\n\n----------- Singly Linked List Get example -----------\n")

print("Get - at index: 0 | result:", big_box_list.get(0))
print("Get - at index: 2 | result:", big_box_list.get(2))
print("Get - at index: 99 | result:", big_box_list.get(99))

print("\n\n----------- Singly Linked List Set example -----------\n")

print("Set - 'New Val' at index: 0 | result: ", big_box_list.set(0, "New Val"))
print("Set - 'Second' at index: 2 | result: ", big_box_list.set(2, "Second"))
print(
    "Set - 'Out bound' at index: 99 | result: ", big_box_list.set(99, "Out bound")
)

print("\n\n----------- Singly Linked List Insert example -----------\n")

print(
    "\nInsert - 'New Val 1' at index: 0 | result: ",
    big_box_list.insert(0, "New Val 1"),
)
print(
    "\nInsert - 'New Val' at index: 2 | result: ",
    big_box_list.insert(2, "New Val 2"),
)
print(
    "\nInsert - 'Out bound' at index: 99 | result: ",
    big_box_list.insert(99, "Out bound"),
)

print("\n\n----------- Singly Linked List Remove example -----------\n")

# Reinitialize the list
big_box_list = SinglyLinkedList()
big_box_list.push("Big")
big_box_list.push("Box")
big_box_list.push("Code")

print("Remove - form index: 2 | result:", big_box_list.remove(2))

print("Remove - from index: 0 | result:", big_box_list.remove(0))

print("Remove - form index: 99 | result:", big_box_list.remove(99))

print("List value: ")
big_box_list.traverse()

print("\n\n----------- Singly Linked List Reverse example -----------\n")

# Reinitialize the list
big_box_list = SinglyLinkedList()
big_box_list.push("Big")
big_box_list.push("Box")
big_box_list.push("Code")
big_box_list.push("Singly")
big_box_list.push("Linked")
big_box_list.push("List")

print("List value: ")
big_box_list.traverse()

big_box_list.reverse()

print("\nList value after reverse: ")
big_box_list.traverse()
Python

Output:

Output of the demo code will look like below-

----------- Singly Linked List Push example -----------

Big -> Box -> Code ->

----------- Singly Linked List Pop example -----------

Poppped item:  Code
Poppped item:  Box
Poppped item:  Big
Poppped item:  None


----------- Singly Linked List Shift example -----------

Shift head from list:  Big
Shift head from list:  Box


----------- Singly Linked List Unshift example -----------

Unshift - 'Box' | Result:  Box
Unshift - 'Box' | Result:  Big


----------- Singly Linked List Get example -----------

Get - at index: 0 | result: Big
Get - at index: 2 | result: Code
Get - at index: 99 | result: None


----------- Singly Linked List Set example -----------

Set - 'New Val' at index: 0 | result:  True
Set - 'Second' at index: 2 | result:  True
Set - 'Out bound' at index: 99 | result:  False


----------- Singly Linked List Insert example -----------


Insert - 'New Val 1' at index: 0 | result:  True

Insert - 'New Val' at index: 2 | result:  True

Insert - 'Out bound' at index: 99 | result:  False


----------- Singly Linked List Remove example -----------

Remove - form index: 2 | result: Code
Remove - from index: 0 | result: Big
Remove - form index: 99 | result: None
List value:
Box ->

----------- Singly Linked List Reverse example -----------

List value:
Big -> Box -> Code -> Singly -> Linked -> List ->
List value after reverse:
List -> Linked -> Singly -> Code -> Box -> Big ->
Plaintext

Tests

Let’s test the functionality using automated testing. Use the following code for testing.

Output:

Output of the test-

Time Complexity

The time complexity of operation on a Singly Linked List is as below-

OperationComplexity
InsertionO(1)
RemovalO(N)
SearchO(N)
Access elementO(N)

Source Code

Use the following links to get the source code used in this article-

Related Data Structures

CommandDetails
Doubly Linked List Doubly Linked List Detail

Other Code Implementations

Use the following links to check the Singly Link List implementation in other programming languages-

Leave a Comment


The reCAPTCHA verification period has expired. Please reload the page.