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.
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
class Node:
def __init__(self, data):
self.data = data
self.next = NoneStep #2: Linked List Class
class SinglyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.length = 0Step #3: Push (Node to the end)
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 += 1Step #4: Pop (Last Node)
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 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
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 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 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_nodeStep #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 FalseStep #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 NoneStep #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 TrueStep #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 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 selfI
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
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()
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 ->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-
| Operation | Complexity |
|---|---|
| Insertion | O(1) |
| Removal | O(N) |
| Search | O(N) |
| Access element | O(N) |
Source Code
Use the following links to get the source code used in this article-
| Source Code of | Implementation Code |
|---|---|
| Python Implementation |  GitHub |
| Demo | GitHub |
| Test Code | GitHub |
Related Data Structures
| Command | Details |
|---|---|
| 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-
