Singly Linked List in Python
Last Updated :
15 Apr, 2024
A Singly Linked List is a type of data structure that is made up of nodes that are created using self-referential structures. Each node contains a data element and a reference (link) to the next node in the sequence. This allows for a dynamic and efficient management of data elements.
.webp)
A singly linked list is a linear data structure in which the elements are not stored in contiguous memory locations and each element is connected only to its next element using a pointer. We can traverse the entire linked list using the next pointer of each node.
Representation of Singly linked list in Python:
Here is the representation of the singly linked list in python:
Python
class Node:
def __init__(self, data=None):
# Data stored in the node
self.data = data
# Reference to the next node in the singly linked list
self.next = None
Traversal of Singly Linked List in Python:
To traverse a singly linked list in Python, you simply need to iterate through each node starting from the head node and print the data of each node until you reach the end of the list (i.e. when the next pointer of a node is None).
Below is the implementation of the above idea:
Python3
# Python Program for traversal of Singly Linked list
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_at_beginning(head, data):
new_node = Node(data)
new_node.next = head
return new_node
def traverse(head):
current = head
while current:
# Print the current node's data followed by an arrow and space
print(str(current.data) + " -> ", end=" ")
current = current.next
# At the end of the list, print None to indicate no further nodes
print("None")
# Singly linked list created and its head stored in a variable named "head"
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
# To traverse and print the nodes:
traverse(head)
Output1 -> 2 -> 3 -> 4 -> None
Insertion of Singly Linked List in Python:
Given a Linked List, the task is to insert a new node in this given Linked List at the following positions:
- At the front of the linked list
- After a given node.
- At the end of the linked list.
1. Insertion at the Beginning of the linked list:
To insert a node at the beginning of a singly linked list in Python, you need to follow these steps:
- Create a new node with the given data.
- Set the “next” pointer of the new node to point to the current head of the list.
- Update the head of the list to point to the new node.
Below is the implementation of the above idea:
Python3
# Python Program for the insertion of node at the beginning
class Node:
def __init__(self, data):
# Initialize a new Node with data and next pointer
self.data = data
self.next = None
def insert_at_beginning(head, data):
# Insert a new node at the beginning of the linked list
new_node = Node(data)
new_node.next = head
return new_node
def traverse(head):
# Traverse the linked list and print its elements
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
traverse(head)
Output1 -> 2 -> 3 -> 4 -> None
2. Insertion after a given node:
To insert a node after a given node in a singly linked list in Python, you need to follow these steps:
- Create a new node with the given data.
- Set the “next” pointer of the new node to point to the next node of the given node.
- Update the “next” pointer of the given node to point to the new node.
Below is the implementation of the above idea:
Python3
# Python Program for Insertion after a given node
class Node:
def __init__(self, data):
# Initialize a new node with data and next pointer
self.data = data
self.next = None
def insert_at_beginning(head, data):
# Insert a new node at the beginning of the linked list
new_node = Node(data)
new_node.next = head
return new_node
def insert_after_node(node, data):
# Insert a new node with given data after the specified node
if node is None:
print("Error: The given node is None")
return
new_node = Node(data)
new_node.next = node.next
node.next = new_node
def traverse(head):
# Traverse the linked list and print its elements
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 1)
# Insert 2 after the node with data 1
insert_after_node(head, 2)
# Traverse and print the nodes after insertion
traverse(head)
Output1 -> 2 -> 3 -> 4 -> None
3. Insertion at the end of the linked list:
To insert a node at the end of a singly linked list in Python, you need to follow these steps:
- Create a new node with the given data.
- Traverse the list to find the last node.
- Set the “next” pointer of the last node to point to the new node.
Below is the implementation of the above idea:
Python3
# Python Program for the insertion at the end of the Singly Linked List
class Node:
def __init__(self, data):
# Initialize a new node with data and next pointer
self.data = data
self.next = None
def insert_at_beginning(head, data):
# Insert a new node at the beginning of the linked list
new_node = Node(data)
new_node.next = head
return new_node
def insert_at_end(head, data):
# Insert a new node with given data at the end of the linked list
new_node = Node(data)
if head is None:
return new_node
current = head
while current.next:
current = current.next
current.next = new_node
return head
def traverse(head):
# Traverse the linked list and print its elements
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Driver Code
head = None
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
# Insert 4 at the end
insert_at_end(head, 4)
# Traverse and print the nodes after insertion
traverse(head)
Output1 -> 2 -> 3 -> 4 -> None
Deletion of Singly Linked List in Python:
You can delete an element in a list from:
- Beginning
- After a given node
- End
1. Deletion from the beginning:
To delete a node from the beginning of a singly linked list in Python, you need to follow these steps:
- If the list is empty (head is None), there is nothing to delete.
- Update the head of the list to point to the next node (if any).
Below is the implementation of the above idea:
Python3
# Python Program for the deletion of a node at the beginning
class Node:
def __init__(self, data):
# Initialize a new node with data and next pointer
self.data = data
self.next = None
def insert_at_beginning(head, data):
# Insert a new node at the beginning of the linked list
new_node = Node(data)
new_node.next = head
return new_node
def delete_at_beginning(head):
# Delete the node at the beginning of the linked list
if head is None:
print("Error: Singly linked list is empty")
return None
new_head = head.next
del head
return new_head
def traverse(head):
# Traverse the linked list and print its elements
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
# Delete the node at the beginning (node with data 1)
head = delete_at_beginning(head)
# Traverse and print the nodes after deletion
traverse(head)
Output2 -> 3 -> 4 -> None
2. Deletion after a given node:
To delete a node after a given node in a singly linked list in Python, you need to follow these steps:
- Check if the given node is None or if the next node of the given node is None (i.e., no node exists after the given node).
- If either condition is true, print an error message or return since there’s nothing to delete.
- Otherwise, update the “next” pointer of the given node to skip the next node.
- Optionally, free the memory allocated to the deleted node.
Below is the implementation of the above idea:
Python3
# Python Program of deletion form a given node
class Node:
def __init__(self, data):
# Initialize a new node with data and next pointer
self.data = data
self.next = None
def insert_at_beginning(head, data):
# Insert a new node at the beginning of the linked list
new_node = Node(data)
new_node.next = head
return new_node
def delete_after_node(node):
# Delete the node after the given node
if node is None or node.next is None:
print("Error: The given node is None or the next node is None")
return
next_node = node.next
node.next = next_node.next
del next_node
def traverse(head):
# Traverse the linked list and print its elements
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
# Delete the node after the node with data 3
delete_after_node(head.next)
# Traverse and print the nodes after deletion
traverse(head)
Output1 -> 2 -> 4 -> None
3. Deletion at the end:
To delete a node at the end of a singly linked list in Python, you need to follow these steps:
- Check if the list is empty (head is None) or if the list has only one node (i.e., head.next is None). If either condition is true, there is nothing to delete.
- Traverse the list to find the second-to-last node.
- Set the “next” pointer of the second-to-last node to None to remove the last node.
- Optionally, free the memory allocated to the deleted node.
Below is the implementation of the above idea:
Python3
# Python Program for deletion at the End of Singly Linked List
class Node:
def __init__(self, data):
# Initialize a new node with data and next pointer
self.data = data
self.next = None
def insert_at_beginning(head, data):
# Insert a new node at the beginning of the linked list
new_node = Node(data)
new_node.next = head
return new_node
def delete_at_end(head):
# Delete the last node of the linked list
if head is None or head.next is None:
print("Error: Singly linked list is empty or has only one node")
return None
current = head
while current.next.next:
current = current.next
del_node = current.next
current.next = None
del del_node
return head
def traverse(head):
# Traverse the linked list and print its elements
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# Driver Code
head = None
head = insert_at_beginning(head, 4)
head = insert_at_beginning(head, 3)
head = insert_at_beginning(head, 2)
head = insert_at_beginning(head, 1)
# Delete the last node (node with data 4)
head = delete_at_end(head)
# Traverse and print the nodes after deletion
traverse(head)
Output1 -> 2 -> 3 -> None
Please Login to comment...