Singly Linked List in Java

Algorithm for Singly Linked List Operations

Understanding how singly linked lists work involves learning about the algorithms that manage their operations. We’ll cover three primary operations: insertion, deletion, and traversal.

1. Insertion

1. To insert a new node into a singly linked list, you first need to create a new node. You can insert a node at the beginning, at the end, or between two existing nodes.
    
2. Beginning: Point the new node’s next to the current head of the list, and then update the head to this new node.
    
3. End: Traverse the list to find the last node (one whose next is null), and set its next to the new node.
    
4. Middle: Find the node after which you want to insert the new node, set the new node’s next to this node’s next, and then update this node’s next to the new node.

2. Deletion

1. To remove a node, you need to modify the next pointer of the node preceding the node to be deleted.
    
2. Specific Node: Traverse the list to find the node before the one you want to delete, set its next to point to the node after the node to be deleted.

3. Traversal

Traversing a singly linked list means going through each node until you reach the end (a node pointing to null). During traversal, you can perform operations like searching for a value or printing each node’s data.

Example Code in Java

Let’s implement a simple singly linked list in Java that includes methods to insert a node at the beginning and to print the list:

• Java

Java

class Node {

    int data;

    Node next;

    public Node(int data) {

        this.data = data;

        this.next = null;

    }

}

class SinglyLinkedList {

    Node head;

   public SinglyLinkedList() {

        this.head = null;

    }

    public void insertAtBeginning(int data) {

        Node newNode = new Node(data);

        newNode.next = head;

        head = newNode;

    }

    public void printList() {

        Node current = head;

        while (current != null) {

            System.out.println(current.data);

            current = current.next;

        }

    }

}

public class Main {

    public static void main(String[] args) {

        SinglyLinkedList list = new SinglyLinkedList();

        list.insertAtBeginning(10);

        list.insertAtBeginning(20);

        list.insertAtBeginning(30);

        list.printList();

    }

}

You can also try this code with Online Java Compiler

Run Code

Output

30
20
10

In this code, we create a Node class to represent each element in the list, and a SinglyLinkedList class that manages the nodes. The insertAtBeginning method demonstrates how a new node is added to the front of the list, and printList shows how to traverse the list to print each node’s data.

Program: Implementing a Singly Linked List in Java

Now that we understand the theory and the basic operations of singly linked lists, let's dive into a more comprehensive program that includes insertion at the end, deletion of a specific node, and a method to display the list. This example will help solidify your understanding by providing a practical application of the concepts we've discussed.

Java Program for a Singly Linked List

• Java

Java

class Node {
    int data;
    Node next;
    // Constructor to create a new node
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    Node head; // head of the list

    // Method to insert a node at the end of the list
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
        }
    }
    // Method to delete a node when the data of the node is known
    public void deleteNode(int key) {
        Node temp = head, prev = null;
        
        // If the head node itself holds the key to be deleted
        if (temp != null && temp.data == key) {
            head = temp.next; // Changed head
            return;
        }

        // Search for the key to be deleted, keep track of the previous node
        while (temp != null && temp.data != key) {
            prev = temp;
            temp = temp.next;
        }

        // If key was not present in linked list
        if (temp == null) return;

        // Unlink the node from linked list
        prev.next = temp.next;
    }

    // Method to print the linked list
    public void printList() {
        Node tNode = head;
        while (tNode != null) {
            System.out.print(tNode.data + " ");
            tNode = tNode.next;
        }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        // Inserting nodes into the singly linked list
        list.insertAtEnd(1);
        list.insertAtEnd(2);
        list.insertAtEnd(4);
        list.insertAtEnd(8);
        // Print the linked list
        System.out.println("Created Linked list is:");
        list.printList();
        
        // Deleting a node from the linked list
        list.deleteNode(4); // Delete node with data 4
        System.out.println("Linked List after Deletion of 4:");
        list.printList();
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Created Linked list is:
1 2 4 8 
Linked List after Deletion of 4:
1 2 8 

In this program:

1. We define a Node class that will represent each element in our singly linked list.
    
2. The SinglyLinkedList class contains methods to insert nodes at the end of the list, delete specific nodes by value, and print all nodes in the list.
    
3. In the main method, we demonstrate how to use these methods to manipulate our singly linked list.

Frequently Asked Questions

What is the primary advantage of using a singly linked list over an array?

The main advantage is flexibility. Singly linked lists allow dynamic memory allocation, meaning memory for elements can be allocated when needed. This is unlike arrays, which require a fixed amount of memory to be allocated initially. This makes linked lists particularly useful for applications where the number of elements can change over time.

Can you access elements by index in a singly linked list as in an array?

No, singly linked lists do not support random access to elements based on indices like arrays do. To access an element, you must traverse the list from the head to the desired position, which takes linear time.

How do you find the size of a singly linked list?

To determine the size, you need to traverse the list from the head node to the end, counting each node until you reach the last one. The count at the end will give you the size of the list.

Conclusion

In this article, we have learned about singly linked lists and their implementation in Java. We started with a basic understanding of what a singly linked list is and its operations such as insertion, deletion, and traversal, and provided a comprehensive Java program to demonstrate these operations in action. With the help of examples we learned how to implement these concepts properly.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.