A singly linked list is a fundamental data structure in computer science and programming, it consists of nodes where each node contains a data field and a reference to the next node in the node. The last node points to null, indicating the end of the list. This linear structure supports efficient insertion and deletion operations, making it widely used in various applications. In this tutorial, we’ll explore the node structure, understand the operations on singly linked lists (traversal, searching, length determination, insertion, and deletion), and provide detailed explanations and code examples to implement these operations effectively.

What is Singly Linked List?

A singly linked list is a fundamental data structure in computer science and programming. It is a collection of nodes where each node contains a data field and a reference (link) to the next node in the sequence. The last node in the list points to null, indicating the end of the list. This linear data structure allows for efficient insertion and deletion operations, making it a popular choice for various applications.

Understanding Node Structure

In a singly linked list, each node consists of two parts: data and a pointer to the next node. The data part stores the actual information, while the pointer (or reference) part stores the address of the next node in the sequence. This structure allows nodes to be dynamically linked together, forming a chain-like sequence.

Singly Linked List

In this representation, each box represents a node, with an arrow indicating the link to the next node. The last node points to NULL, indicating the end of the list.

Node Structure of Singly Linked List

In most programming languages, a node in a singly linked list is typically defined using a class or a struct.

// Definition of a Node in a singly linked list
class Node {
public:
    // Data part of the node
    int data;

    // Pointer to the next node in the list
    Node* next;

    // Constructor to initialize the node with data
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};

// Definition of a Node in a singly linked list
public class Node {
    // Data part of the node
    int data;

    // Pointer to the next node in the list
    Node next;

    // Constructor to initialize the node with data
    public Node(int data)
    {
        this.data = data;
        this.next = null;
    }
}

# Definition of a Node in a singly linked list
class Node:
    def __init__(self, data):
       # Data part of the node
        self.data = data   
        self.next = None    

// Definition of a Node in a singly linked list
class Node {
    constructor(data) {
    // Data part of the node
        this.data = data;   
        this.next = null;   
    }
}

In this example, the Node class contains an integer data field (data) to store the information and a pointer to another Node (next) to establish the link to the next node in the list.

Operations on Singly Linked List

• Traversal
• Searching
• Length
• Insertion:
  • Insert at the beginning
  • Insert at the end
  • Insert at a specific position
• Deletion:
  • Delete from the beginning
  • Delete from the end
  • Delete a specific node

Let’s go through each of the operations mentioned above, one by one.

Traversal in Singly Linked List

Traversal involves visiting each node in the linked list and performing some operation on the data. A simple traversal function would print or process the data of each node.

Step-by-step approach:

• Initialize a pointer current to the head of the list.
• Use a while loop to iterate through the list until the current pointer reaches NULL.
• Inside the loop, print the data of the current node and move the current pointer to the next node.

Below is the function for traversal in singly Linked List:

// C++ Function to traverse and print the elements of the linked
// list
void traverseLinkedList(Node* head)
{
    // Start from the head of the linked list
    Node* current = head;

    // Traverse the linked list until reaching the end
    // (nullptr)
    while (current != NULL) {
      
        // Print the data of the current node
        cout << current->data << " ";

        // Move to the next node
        current = current->next;
    }

    cout << std::endl;
}

// Java Function to traverse and print the elements of the
// linked list
public static void traverseLinkedList(Node head)
{
    // Start from the head of the linked list
    Node current = head;

    // Traverse the linked list until reaching the end
    // (null)
    while (current != null) {

        // Print the data of the current node
        System.out.print(current.data + " ");

        // Move to the next node
        current = current.next;
    }

    System.out.println();
}

# Python Function to traverse and print the elements of the linked list
def traverse_linked_list(head):
    # Start from the head of the linked list
    current = head

    # Traverse the linked list until reaching the end (None)
    while current is not None:

        # Print the data of the current node followed by a space
        print(current.data),

        # Move to the next node
        current = current.next

    print()  # Print a new line after traversing the linked list

// Javascript Function to traverse and print the elements
// of the linked list
function traverseLinkedList(head) {

    // Start from the head of the linked list
    let current = head;

    // Traverse the linked list until reaching the
    // end (null)
    while (current !== null) {
    
        // Print the data of the current node
        console.log(current.data + " ");

        // Move to the next node
        current = current.next;
    }

    console.log();
}

1 2 3 

Searching in Singly Linked List

Searching in a Singly Linked List refers to the process of looking for a specific element or value within the elements of the linked list.

Step-by-step approach:

1. Traverse the Linked List starting from the head.
2. Check if the current node’s data matches the target value.
   • If a match is found, return true.
3. Otherwise, Move to the next node and repeat steps 2.
4. If the end of the list is reached without finding a match, return false.

Below is the function for searching in singly linked list:

// C++ function to search for a value in the Linked List
bool searchLinkedList(Node* head, int target)
{

    // Traverse the Linked List
    while (head != nullptr) {

        // Check if the current node's data matches the
        // target value
        if (head->data == target) {

            return true; // Value found
        }

        // Move to the next node
        head = head->next;
    }

    return false; // Value not found
}

// Java function to search for a value in the Linked List
public boolean searchLinkedList(Node head, int target)
{
    // Traverse the Linked List
    while (head != null) {

        // Check if the current node's data matches the
        // target value
        if (head.data == target) {

            // Value found
            return true;
        }

        // Move to the next node
        head = head.next;
    }

    // Value not found
    return false;
}

# Python function to search for a value in the Linked List
def search_linked_list(head, target):

    # Traverse the Linked List
    while head is not None:

        # Check if the current node's data matches the target value
        if head.data == target:

            return True  # Value found
        # Move to the next node
        head = head.next

    return False  # Value not found

// Javascript function to search for a value in the Linked List
function searchLinkedList(head, target) {

    // Traverse the Linked List
    while (head !== null) {
    
        // Check if the current node's data matches the target value
        if (head.data === target) {
            return true;  // Value found
        }
        
        // Move to the next node
        head = head.next;
    }
    
    return false;  // Value not found
}

Finding Length in Singly Linked List

Finding Length in Singly Linked List refers to the process of determining the total number of nodes in a singly linked list.

Step-by-step approach:

• Initialize a counter length to 0.
• Start from the head of the list, assign it to current.
• Traverse the list:
  • Increment length for each node.
  • Move to the next node (current = current->next).
• Return the final value of length.

Below is the function for finding length in Singly Linked List:

// C++ function to find the length of the linked list
int findLength(Node* head)
{
    // Initialize a counter for the length
    int length = 0;

    // Start from the head of the list
    Node* current = head;

    // Traverse the list and increment the length for each
    // node
    while (current != nullptr) {
        length++;
        current = current->next;
    }

    // Return the final length of the linked list
    return length;
}

// Java function to find the length of the linked list
public int findLength(Node head) {
  
    // Initialize a counter for the length
    int length = 0;

    // Start from the head of the list
    Node current = head;

    // Traverse the list and increment the length for each
    // node
    while (current != null) {
        length++;
        current = current.next;
    }

    // Return the final length of the linked list
    return length;
}

# Python function to find the length of the linked list
def find_length(head):
  
    # Initialize a counter for the length
    length = 0

    # Start from the head of the list
    current = head

    # Traverse the list and increment the length for each
    # node
    while current is not None:
        length += 1
        current = current.next

    # Return the final length of the linked list
    return length

// Javascript function to find the length of the linked list
function findLength(head) {

    // Initialize a counter for the length
    let length = 0;

    // Start from the head of the list
    let current = head;

    // Traverse the list and increment the length for each
    // node
    while (current !== null) {
        length++;
        current = current.next;
    }

    // Return the final length of the linked list
    return length;
}

Insertion in Singly Linked List

Insertion is a fundamental operation in linked lists that involves adding a new node to the list. There are several scenarios for insertion:

a. Insertion at the Beginning of Singly Linked List:

Insertion at the Beginning of Singly Linked List

Step-by-step approach:

• Create a new node with the given value.
• Set the next pointer of the new node to the current head.
• Move the head to point to the new node.
• Return the new head of the linked list.

Below is the function for insertion at the beginning of singly linked list:

// C++ function to insert a new node at the beginning of the
// linked list
Node* insertAtBeginning(Node* head, int value)
{
    // Create a new node with the given value
    Node* newNode = new Node(value);

    // Set the next pointer of the new node to the current
    // head
    newNode->next = head;

    // Move the head to point to the new node
    head = newNode;

    // Return the new head of the linked list
    return head;
}

// Java function to insert a new node at the beginning of the
// linked list
public Node insertAtBeginning(Node head, int value) {
    // Create a new node with the given value
    Node newNode = new Node(value);

    // Set the next pointer of the new node to the current
    // head
    newNode.next = head;

    // Move the head to point to the new node
    head = newNode;

    // Return the new head of the linked list
    return head;
}

# Python function to insert a new node at the beginning of the
# linked list
def insert_at_beginning(head, value):
  
    # Create a new node with the given value
    new_node = Node(value)

    # Set the next pointer of the new node to the current
    # head
    new_node.next = head

    # Move the head to point to the new node
    head = new_node

    # Return the new head of the linked list
    return head

// Javascript function to insert a new node at the beginning of the
// linked list
function insertAtBeginning(head, value) {

    // Create a new node with the given value
    let newNode = new Node(value);

    // Set the next pointer of the new node to the current
    // head
    newNode.next = head;

    // Move the head to point to the new node
    head = newNode;

    // Return the new head of the linked list
    return head;
}

b. Insertion at the End of Singly Linked List:

To insert a node at the end of the list, traverse the list until the last node is reached, and then link the new node to the current last node.-

Insertion at the End of Singly Linked List

Step-by-step approach:

• Create a new node with the given value.
• Check if the list is empty:
  • If it is, make the new node the head and return.
• Traverse the list until the last node is reached.
• Link the new node to the current last node by setting the last node’s next pointer to the new node.

Below is the function for insertion at the end of singly linked list:

// C++ Function to insert a node at the end of the linked
// list
void insertAtEnd(Node** head, int value)
{
    // Create a new node with the given value
    Node* newNode = new Node(value);

    // If the list is empty, make the new node the head
    if (*head == nullptr) {
        *head = newNode;
        return;
    }

    // Traverse the list until the last node is reached
    Node* current = *head;
    while (current->next != nullptr) {
        current = current->next;
    }

    // Link the new node to the current last node
    current->next = newNode;
}

// Java function to insert a node at the end of the linked
// list
public void insertAtEnd(Node[] head, int value) {
  
    // Create a new node with the given value
    Node newNode = new Node(value);

    // If the list is empty, make the new node the head
    if (head[0] == null) {
        head[0] = newNode;
        return;
    }

    // Traverse the list until the last node is reached
    Node current = head[0];
    while (current.next != null) {
        current = current.next;
    }

    // Link the new node to the current last node
    current.next = newNode;
}

# Python function to insert a node at the end of the linked
# list
def insert_at_end(head, value):
  
    # Create a new node with the given value
    new_node = Node(value)

    # If the list is empty, make the new node the head
    if head is None:
        return new_node

    # Traverse the list until the last node is reached
    current = head
    while current.next is not None:
        current = current.next

    # Link the new node to the current last node
    current.next = new_node

    return head

// Javascript function to insert a node at the end of the linked
// list
function insertAtEnd(head, value) {

    // Create a new node with the given value
    let newNode = new Node(value);

    // If the list is empty, make the new node the head
    if (head === null) {
        return newNode;
    }

    // Traverse the list until the last node is reached
    let current = head;
    while (current.next !== null) {
        current = current.next;
    }

    // Link the new node to the current last node
    current.next = newNode;

    return head;
}

c. Insertion at a Specific Position of the Singly Linked List:

To insert a node at a specific position, traverse the list to the desired position, link the new node to the next node, and update the links accordingly.

Insertion at a Specific Position of the Singly Linked List

Step-by-step approach:

• Check if the given position is valid.
  • If invalid, print “Invalid position!” and exit.
• Loop until pos reaches 0:
  • If pos is 0:
    • Create a new node with the given data.
    • Set the new node’s next pointer to the current node.
    • Update the current node to the new node.
  • Else, move to the next node by updating the double pointer.
• Increment the size of the linked list.

Below is the function for insertion at a specific position of the singly linked list:

// C++ function to insert a Node at specified position
void insertPos(Node** current, int pos, int data)
{
    // This condition to check whether the
    // position given is valid or not.
    if (pos < 1 || pos > size + 1)
        cout << "Invalid position!" << endl;
    else {

        // Keep looping until the pos is zero
        while (pos--) {

            if (pos == 0) {

                // adding Node at required position
                Node* temp = getNode(data);

                // Making the new Node to point to
                // the old Node at the same position
                temp->next = *current;

                // Changing the pointer of the Node previous
                // to the old Node to point to the new Node
                *current = temp;
            }
            else
                // Assign double pointer variable to point
                // to the pointer pointing to the address of
                // next Node
                current = &(*current)->next;
        }
        size++;
    }
}

// Java function to insert a Node at specified position
public void insertPos(Node current, int pos, int data)
{

    // This condition to check whether the
    // position given is valid or not.
    if (pos < 1 || pos > size + 1) {
        System.out.println("Invalid position!");
    }
    else {

        // Keep looping until the pos is zero
        while (--pos > 0) {
            if (pos == 0) {

                // adding Node at required position
                Node temp = new Node(data);

                // Making the new Node to point to
                // the old Node at the same position
                temp.next = current;

                // Changing the pointer of the Node previous
                // to the old Node to point to the new Node
                current = temp;
            }
            else {

                // Assign current to point to the
                // pointer pointing to the address of
                // next Node
                current = current.next;
            }
        }
        size++;
    }
}

# Python function to insert a Node at specified position
def insert_pos(current, pos, data):
  
    # This condition to check whether the
    # position given is valid or not.
    if pos < 1 or pos > size + 1:
        print("Invalid position!")
    else:
      
        # Keep looping until the pos is zero
        while pos > 1:
            if pos == 1:

                # adding Node at required position
                temp = Node(data)

                # Making the new Node to point to
                # the old Node at the same position
                temp.next = current

                # Changing the pointer of the Node previous
                # to the old Node to point to the new Node
                current = temp
            else:

                # Assign cur
                # pointer pointing to the address of
                # next Node
                current = current.next
            pos -= 1
        size += 1
    return current

// Javascript function to insert a Node at specified position
function insertPos(current, pos, data) {

    // This condition to check whether the
    // position given is valid or not.
    if (pos < 1 || pos > size + 1) {
        console.log("Invalid position!");
    } else {
    
        // Keep looping until the pos is zero
        while (--pos > 0) {
            if (pos === 0) {
            
                // adding Node at required position
                let temp = new Node(data);

                // Making the new Node to point to
                // the old Node at the same position
                temp.next = current;

                // Changing the pointer of the Node previous
                // to the old Node to point to the new Node
                current = temp;
            } else {
            
                // Assign current to point to the
                // pointer pointing to the address of
                // next Node
                current = current.next;
            }
        }
        size++;
    }
    return current;
}

Deletion in Singly Linked List

Deletion involves removing a node from the linked list. Similar to insertion, there are different scenarios for deletion:

a. Deletion at the Beginning of Singly Linked List:

To delete the first node, update the head to point to the second node in the list.

Deletion at the Beginning of Singly Linked List

Steps-by-step approach:

• Check if the head is NULL.
  • If it is, return NULL (the list is empty).
• Store the current head node in a temporary variable temp.
• Move the head pointer to the next node.
• Delete the temporary node.
• Return the new head of the linked list.

Below is the function for deletion at the beginning of singly linked list:

// C++ Function to remove the first node of the linked
// list
Node* removeFirstNode(struct Node* head)
{
    if (head == NULL)
        return NULL;

    // Move the head pointer to the next node
    Node* temp = head;
    head = head->next;

    delete temp;

    return head;
}

// Java Function to remove the first node
// of the linked list
static Node removeFirstNode(Node head)
{
    if (head == null)
        return null;

    // Move the head pointer to the next node
    Node temp = head;
    head = head.next;

    return head;
}

# Python Function to remove the first node
# of the linked list
def removeFirstNode(head):
    if not head:
        return None
    temp = head

    # Move the head pointer to the next node
    head = head.next
    temp = None
    return head

// Javascript Function to remove the first node
// of the linked list /
function removeFirstNode(head) {
  if (head == null) return null;

  // Move the head pointer to the next node
  temp = head;
  head = head.next;

  return head;
}

b. Deletion at the End of Singly Linked List:

To delete the last node, traverse the list until the second-to-last node and update its next field to None.

Deletion at the End of Singly Linked List

Step-by-step approach:

• Check if the head is NULL.
  • If it is, return NULL (the list is empty).
• Check if the head’s next is NULL (only one node in the list).
  • If true, delete the head and return NULL.
• Traverse the list to find the second last node (second_last).
• Delete the last node (the node after second_last).
• Set the next pointer of the second last node to NULL.
• Return the head of the linked list.

Below is the function for deletion at the end of singly linked list:

// C++ Function to remove the last node of the linked list
Node* removeLastNode(struct Node* head)
{
    if (head == NULL)
        return NULL;
 
    if (head->next == NULL) {
        delete head;
        return NULL;
    }
 
    // Find the second last node
    Node* second_last = head;
    while (second_last->next->next != NULL)
        second_last = second_last->next;
 
    // Delete last node
    delete (second_last->next);
 
    // Change next of second last
    second_last->next = NULL;
 
    return head;
}

// Java Function to remove the last node of the linked list
Node removeLastNode(Node head)
{
    // If the list is empty, return null
    if (head == null)
        return null;

    // If the list has only one node, delete it and return
    // null
    if (head.next == null) {
        head = null;
        return null;
    }

    // Find the second last node
    Node second_last = head;
    while (second_last.next.next != null)
        second_last = second_last.next;

    // Remove the last node
    second_last.next = null;

    // Return the modified list
    return head;
}

# Python Function to remove the last node of the linked list
def removeLastNode(head):
    # If the list is empty, return None
    if head is None:
        return None

    # If the list has only one node, delete it and return None
    if head.next is None:
        head = None
        return None

    # Find the second last node
    second_last = head
    while second_last.next.next is not None:
        second_last = second_last.next

    # Remove the last node
    second_last.next = None

    # Return the modified list
    return head

// Javascript Function to remove the last node of the linked list
function removeLastNode(head) {
    // If the list is empty, return null
    if (head === null)
        return null;

    // If the list has only one node, delete it
    // and return null
    if (head.next === null) {
        head = null;
        return null;
    }

    // Find the second last node
    let second_last = head;
    while (second_last.next.next !== null)
        second_last = second_last.next;

    // Remove the last node
    second_last.next = null;
    
    // Return the modified list
    return head;
}

c. Deletion at a Specific Position of Singly Linked List:

To delete a node at a specific position, traverse the list to the desired position, update the links to bypass the node to be deleted.

Deletion at a Specific Position of Singly Linked List

Step-by-step approach:

• Check if the list is empty or the position is invalid, return if so.
• If the head needs to be deleted, update the head and delete the node.
• Traverse to the node before the position to be deleted.
• If the position is out of range, return.
• Store the node to be deleted.
• Update the links to bypass the node.
• Delete the stored node.

Below is the function for deletion at a specific position of singly linked list:

// C++ function to delete a node at a specific position
void deleteAtPosition(Node** head, int position)
{
    // If the list is empty or the position is invalid
    if (*head == nullptr || position < 1) {
        return;
    }

    // If the head needs to be deleted
    if (position == 1) {
        Node* temp = *head;
        *head = (*head)->next;
        delete temp;
        return;
    }

    // Traverse to the node before the position to be
    // deleted
    Node* current = *head;
    for (int i = 1; i < position - 1 && current != NULL;
         i++) {
        current = current->next;
    }

    // If the position is out of range
    if (current == NULL || current->next == NULL) {
        return;
    }

    // Store the node to be deleted
    Node* temp = current->next;

    // Update the links to bypass the node to be deleted
    current->next = current->next->next;

    // Delete the node
    delete temp;
}

// Java function to delete a node at a specific position
public void deleteAtPosition(Node head, int position)
{
    // If the list is empty or the position is invalid
    if (head == null || position < 1) {
        return;
    }

    // If the head needs to be deleted
    if (position == 1) {
        Node temp = head;
        head = head.next;
        temp = null;
        return;
    }

    // Traverse to the node before the position to be
    // deleted
    Node current = head;
    for (int i = 1; i < position - 1 && current != null;
         i++) {
        current = current.next;
    }

    // If the position is out of range
    if (current == null || current.next == null) {
        return;
    }

    // Store the node to be deleted
    Node temp = current.next;

    // Update the links to bypass the node to be deleted
    current.next = current.next.next;

    // Delete the node
    temp = null;
}

# Python function to delete a node at a specific position
def delete_at_position(head, position):
    # If the list is empty or the position is invalid
    if head is None or position < 1:
        return head

    # If the head needs to be deleted
    if position == 1:
        temp = head
        head = head.next
        temp = None
        return head

    # Traverse to the node before the position to be deleted
    current = head
    for i in range(1, position - 1):
        if current is not None:
            current = current.next

    # If the position is out of range
    if current is None or current.next is None:
        return head

    # Store the node to be deleted
    temp = current.next

    # Update the links to bypass the node to be deleted
    current.next = current.next.next

    # Delete the node
    temp = None
    return head

// Javascript function to delete a node at a specific position
function deleteAtPosition(head, position) {
    // If the list is empty or the position is invalid
    if (head === null || position < 1) {
        return head;
    }

    // If the head needs to be deleted
    if (position === 1) {
        let temp = head;
        head = head.next;
        temp = null;
        return head;
    }

    // Traverse to the node before the position to be deleted
    let current = head;
    for (let i = 1; i < position - 1 && current !== null; i++) {
        current = current.next;
    }

    // If the position is out of range
    if (current === null || current.next === null) {
        return head;
    }

    // Store the node to be deleted
    let temp = current.next;

    // Update the links to bypass the node to be deleted
    current.next = current.next.next;

    // Delete the node
    temp = null;
    return head;
}