# 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.

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 = None``````
Python

### Step #2: Linked List Class

``````class SinglyLinkedList:
def __init__(self):
self.tail = None
self.length = 0``````
Python

### Step #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
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)

``````class SinglyLinkedList:
# Other functionality

# Pop item from the end
def pop(self):
# Return None if the list is empty
return None

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.Tail = None

# Return the node in the current variable
return current          ``````
Python

### Step #5: Traverse all Nodes

``````class SinglyLinkedList:
# Other functionality

def traverse(self):

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

# Set the next node as head

# 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

Python

### Step #7: Unshift Head

``````class SinglyLinkedList:
# Other functionality

# Create new node and set that as head
def unshift(self, data):
# Create a new node from provided data

if self.head is None:
else:

# Set the new_head as head of the list

# Increase size of the list by 1
self.length += 1

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

# 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):
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):
prev_node = None
next_node = None

while current_node:
next_node = current_node.next
current_node.next = prev_node

prev_node = current_node
current_node = next_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

def __init__(self):
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
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
return None

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.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

# Set the next node as head

# 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

# Create new node and set that as head
def unshift(self, data):
# Create a new node from provided data

if self.head is None:
else:

# Set the new_head as head of the list

# Increase size of the list by 1
self.length += 1

# 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

# 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):
prev_node = None
next_node = None

while current_node:
next_node = current_node.next
current_node.next = prev_node

prev_node = current_node
current_node = next_node

return self

# Search the list for specific data
def search(self, data):
index = 0

while current:
if current.data == data:
return index

current = current.next
index += 1

return None

def traverse(self):

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

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.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.push("Big")
big_box_list.push("Box")
big_box_list.push("Code")
big_box_list.push("Singly")
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-

## Source Code

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

## Other Code Implementations

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