Open In App

Singly Linked List in Python

Last Updated : 15 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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.

Singly-Linked-List-in-Python-(1)

What is a Singly Linked List?

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)

Output
1 ->  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)

Output
1 -> 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)  

Output
1 -> 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)

Output
1 -> 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)

Output
2 -> 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)

Output
1 -> 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)

Output
1 -> 2 -> 3 -> None

Article

Link

Detect and Remove Loop in a Linked List

Link

Detect loop or cycle in a linked list

Link

Program for Nth node from the end of a Linked List

Link

Find Middle of the Linked List

Link

Function to check if a singly linked list is palindrome

Link

Reverse a Linked List

Link

Remove duplicates from a sorted linked list

Link

Intersection point of two Linked Lists

Link

Add two numbers represented by Linked List

Link

Remove Duplicates from an Unsorted Linked List

Link



Similar Reads

Difference between Singly linked list and Doubly linked list
Introduction to Singly linked list : A singly linked list is a set of nodes where each node has two fields 'data' and 'link'. The 'data' field stores actual piece of information and 'link' field is used to point to next node. Basically the 'link' field stores the address of the next node. Introduction to Doubly linked list : A Doubly Linked List (D
2 min read
Convert Singly Linked List to XOR Linked List
Prerequisite: XOR Linked List – A Memory Efficient Doubly Linked List | Set 1XOR Linked List – A Memory Efficient Doubly Linked List | Set 2 An XOR linked list is a memory efficient doubly linked list in which the next pointer of every node stores the XOR of previous and next node's address. Given a singly linked list, the task is to convert the gi
9 min read
When is Doubly Linked List more Efficient than Singly Linked List?
Did you know there are some cases where a Doubly Linked List is more efficient than a Singly Linked List, even though it takes more memory compared to a Singly Linked List? What are those Cases? Well, we will discuss that in the following article, But first, let's talk about Singly and linked lists: What is a Singly Linked List?A singly linked list
4 min read
Convert singly linked list into circular linked list
Given a singly linked list, we have to convert it into circular linked list. For example, we have been given a singly linked list with four nodes and we want to convert this singly linked list into circular linked list. Approach: The idea is to traverse the singly linked list and check if the node is the last node or not. If the node is the last no
14 min read
Python Program For Reversing Alternate K Nodes In A Singly Linked List
Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm. Example: Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3 Output: 3->2->1->4->5->6->9->8->7->NULL. Method 1 (Process 2k node
6 min read
Python Program For Insertion Sort In A Singly Linked List
We have discussed Insertion Sort for arrays. In this article we are going to discuss Insertion Sort for linked list. Below is a simple insertion sort algorithm for a linked list. 1) Create an empty sorted (or result) list. 2) Traverse the given list, do following for every node. ......a) Insert current node in sorted way in sorted or result list. 3
5 min read
Python Program For Selecting A Random Node From A Singly Linked List
Given a singly linked list, select a random node from the linked list (the probability of picking a node should be 1/N if there are N nodes in the list). You are given a random number generator.Below is a Simple Solution: Count the number of nodes by traversing the list.Traverse the list again and select every node with probability 1/N. The selecti
4 min read
Python Program For Recursive Selection Sort For Singly Linked List - Swapping Node Links
Given a singly linked list containing n nodes. The problem is to sort the list using the recursive selection sort technique. The approach should be such that it involves swapping node links instead of swapping node data. Examples: Input: 10 -> 12 -> 8 -> 4 -> 6 Output: 4 -> 6 -> 8 -> 10 -> 12 In Selection Sort, we first find
4 min read
Random Singly Linked List Generator using Python
In this article, we will learn how to generate a singly linked list using random numbers. Prerequisite: Insertion in Linked List A Singly Linked List is a linear data structure. A linked list is a collection of nodes and in a singly linked list every node contains two things: Data Reference to the next node In this article, we will learn to generat
5 min read
Python Program To Check If A Singly Linked List Is Palindrome
Given a singly linked list of characters, write a function that returns true if the given list is a palindrome, else false. Recommended: Please solve it on "PRACTICE" first, before moving on to the solution. METHOD 1 (Use a Stack): A simple solution is to use a stack of list nodes. This mainly involves three steps.Traverse the given list from head
6 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg