Singly Linked List

A singly linked list is a linear data structure consisting of a series of nodes, each containing two parts: a data part and a pointer to the next node. The characteristic of a singly linked list is that each node points only to the next node, and the pointer of the last node points to null, indicating the end of the list.

Basic Operations of Singly Linked List

1. Creating a Linked List

To create a linked list, you need a head node, which does not store data but only stores a pointer to the first node.

2. Adding Nodes

Nodes can be added at the head, tail, or in the middle of the linked list.

3. Deleting Nodes

Nodes can be deleted from the head, tail, or middle of the linked list.

4. Searching Nodes

Nodes can be searched based on their values.

5. Traversing the Linked List

Starting from the head node, each node is accessed in sequence.

Advantages and Disadvantages of Singly Linked List

Advantages

The length of the linked list can dynamically increase, unlike arrays that require pre-allocated memory space.
The time complexity for inserting and deleting nodes is O(1), as it does not require moving other elements, making it efficient.

Disadvantages

The random access efficiency of the linked list is low, with a time complexity of O(n), as each access requires starting from the head.
The linked list requires additional memory space to store pointers, which takes up more memory.

Implementation of Singly Linked List

SinglyLinkedListDemo.java

        class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + (next != null) +
                '}';
    }
}

class LinkedList {
    Node head;

    LinkedList() {
        this.head = null;
    }

    void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    void delete(int data) {
        if (head == null) {
            return;
        }

        if (head.data == data) {
            head = head.next;
            return;
        }

        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    void print() {
        Node current = head;
        while (current.next != null) {
            System.out.print(current + " -> ");
            current = current.next;
        }
        System.out.println(current);
    }

}

public class SinglyLinkedListDemo {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);
        list.print();
        list.delete(3);
        list.print();
    }
}

Output:

bash

        Node{data=1, next=true} -> Node{data=2, next=true} -> Node{data=3, next=true} -> Node{data=4, next=true} -> Node{data=5, next=false}
Node{data=1, next=true} -> Node{data=2, next=true} -> Node{data=4, next=true} -> Node{data=5, next=false}