Singly Linked List (SLL)

Follow me

 Singly Linked List (SLL)

Agenda: 

1. What is a Node?
2. Defining a Node
3. Singly Linked List
4. Operations on Singly Linked List

1. What is a Node?

    a. Node Structure: A node in a linked list typically consists of two components:

• Data
• Next

    b. Data: It holds the actual value or data associated with the node.
    c. Next Pointer: It stores the memory address (reference) of the next node in the sequence.
    d. Head and Tail: The linked list is accessed through the head node, which points to the first node in the list. The last node in the list points to NULL indicating the end of the list. This node is known as the tail node.

2. Defining a Node.

 

        class Node:

                def __init__(self, item=None, next=None)

                        self.item=item

                        self.next=next

Note: 

• Head and Start both are same.
• Tail and End both are same.

3.Singly Linked List

    i) SLL is a linear data structure.

    ii) It can grow and shrink.

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in 
only one direction from head to the last node (tail).

Each element in a linked list is called a node. A single node contains data and a pointer to the next node which helps in maintaining the structure of the list.

The first node is called the head; it points to the first node of the list and helps us access every other element in the list. The last node, also sometimes called the tail, points to NULL which helps us in determining when the list ends.

4. Operations on Singly Linked List        

• Traversal - To access each element of the linked list.
• Insertion - To add/insert a new node to the list.
• Deletion - To remove an existing node from the list.
• Search - To find a node in the list.
• Sort - To sort the nodes.

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:

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

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

# 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

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

# 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

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

# 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

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

# 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

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

# 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

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

# 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

Searching of Singly Linked List in Python:

Searching is performed in order to find the location of a particular element in the list. Searching any element in the list needs traversing through the list and make the comparison of every element of the list with the specified element. If the element is matched with any of the list element then the location of the element is returned from the function.

Below is the implementation of the above idea:

class Node: # Singly linked node def __init__(self, data=None): self.data = data self.next = None

class singly_linked_list:

def __init__(self): # Createe an empty list self.tail = None self.head = None self.count = 0 def append_item(self, data): #Append items on the list node = Node(data) if self.head: self.head.next = node self.head = node else: self.tail = node self.head = node self.count += 1 def iterate_item(self): # Iterate the list. current_item = self.tail while current_item: val = current_item.data current_item = current_item.next yield val def search_item(self, val): # Search the list for node in self.iterate_item(): if val == node: return True return False items = singly_linked_list() items.append_item('PHP') items.append_item('Python') items.append_item('C#') items.append_item('C++') items.append_item('Java') if items.search_item('SQL'): print("True") else: print("False") if items.search_item('C++'): print("True") else: print("False")

Output:

        False

        True

OR Another Type

i. Node creation

A program class to create a node should be defined as a first step in the python program and the data objects can be created as when required.

Code:

# Linked list Concepts  - Demo Program    
class Node:
                def __init__(self, item=None, next=None)
                        self.item=item
                        self.next=next

ii. Linked List Creation

Another program class to create linked list with initial values should be defined in the program as next step. This class would contain steps for subsequent operations like Inserting, Delete, Traverse (Navigation).

Code:

class LinkedListdemo:
    def __init__(self, start=None):       #Linked list creation
        self.start = start     #Link to first node

iii. Initial Data Loading (Insert at The End)

Ideally the initial loading can happen from the end of the empty data set. While inserting a new data, If the dataset is empty make the new node as the first and last node and exit. If data is present in the dataset then navigate to end, make the current last node as last but one node. New node will be the last.

Code:

 def insert_at_last(self, data):      
        new_node = Node(data)                     # move data
        if self.start is None:                    # empty set
            self.start_node = new_node             
            return
        n = self.start
        while n.next is not None:
            n= n.next                              
        n.next = new_node;                         #new node is the last
                                                                  #old last is last but one

iv. Navigating through data set

While navigating check whether the list is empty or not. Use the start node link to reach first node and use the link present in the first node to reach second and move on till the end

Code:

            def navigate_list(self):             if self.start_node is None: # if there is no first node             print("List has no element") #it is empty list             return             else:             print ("DATA LINK to NEXT") # Header             print ("\n") # blank line             print (" ", self.start) # Link to first node             n = self.start # start from first             while n is not None:                 print(n.item , n.next) # Print Data and next link                 n = n.next # loop iteration

v. Appending Nodes to Dataset

With all definitions are over, create a working object for linked list creation module and invoke it for inserting new nodes at the end.

Code:

new_linked_listdemo = LinkedListdemo()                   # new object
new_linked_listdemo.insert_at_last("January")         # inserting nodes at end
new_linked_listdemo.insert_at_last("February")
new_linked_listdemo.insert_at_last("March")
new_linked_listdemo.insert_at_last("April")
new_linked_listdemo.insert_at_last("May")
new_linked_listdemo.insert_at_last("June")
new_linked_listdemo.insert_at_last("July")
new_linked_listdemo.insert_at_last("August")
new_linked_listdemo.insert_at_last("September")
new_linked_listdemo.insert_at_last("October")
new_linked_listdemo.insert_at_last("November")
new_linked_listdemo.insert_at_last("December")

vi. List Dataset

Using the same linked list creation object class, scan through the dataset and view it.

Code:

new_linked_listdemo.navigate_list()  # traversing the list

Output:

vii. Insert in The Beginning

Make the new node as the starting node and the existing starting node as the second node. Code:

def insert_at_beginning(iab, data):      
            new_node = Node(data)                 # move data
            new_node.next = self.start_node         # Current first as second
            self.start_node= new_node              # new as latest first
new_linked_listdemo.insert_at_beginning("Pre-January")
new_linked_listdemo.navigate_list()                   # traverssing the list

Output:

viii. Insert Next to An Existing Item

Reach the existing item, make it as previous node for the new node. Make the new node as previous node to the next node.

Code:

def insert_nextto_item(self, x, data):
        n = self.start_node
        while n is not None:
            if n.item == x:                       # match the item 
                break
            n = n.next
        if n is None:                                  # no match
            print("item not in the list")
        else:
            new_node = Node(data)               
            new_node.next = n.next                # Swap new node address and previous
            n.next = new_node                      # node link

ix. Inserting Node After an Existing Node

new_linked_listdemo.insert_nextto_item("March","Post-march")
new_linked_listdemo.navigate_list()                   # traverssing the list

Output:

x. Deletion of Nodes

First Node – Make the second node as the starting node Last Node  – Reach the last but one node and blank out the next link Any Middle node identified by content – Reach that node and change the link of the previous node to point to next node with reference to node to be deleted.

Code:

def delete_at_beginning(self):
        if self.start_node is None:              # Empty list
            print("Empty List")
            return 
        self.start_node = self.start_node.next     # make second node as initial

def delete_at_last(self):
        if self.start_node is None:
            print("Empty list")
            return

        n = self.start_node
        while n.next.next is not None:         # Search last but one node
            n = n.next
        n.next = None                         # blank out the link 
        
def delete_element_by_content(self, x):
    
    
    n = self.start_node
    while n.next is not None:
        if n.next.item == x:         # match found                   
            break
        n = n.next

    if n.next is None:
        print("no such item")
    else:
        n.next = n.next.next         # change previous node link with next

xi. Test the Delete Function

Code:

new_linked_listdemo.delete_at_beginning()
new_linked_listdemo.delete_at_last()
new_linked_listdemo.delete_element_by_content("August")
new_linked_listdemo.navigate_list()    # traverssing the list

Output: