Singly LinkedList in Java

In Java, a single linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference to the next node in the list. The first node in the list is called the head, and the last node is called the tail.

Here’s an example implementation of a single linked list in Java:

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        LinkedList<Integer> list = new LinkedList<Integer>();
        
        while (true) {
            System.out.println("Choose an operation:");
            System.out.println("1. Add an element to the end of the list");
            System.out.println("2. Remove an element from the list");
            System.out.println("3. Get the size of the list");
            System.out.println("4. Check if the list contains an element");
            System.out.println("5. Print the elements of the list");
            System.out.println("6. Exit");
            int choice = scanner.nextInt();
            
            switch (choice) {
                case 1:
                    System.out.print("Enter an integer to add: ");
                    int num = scanner.nextInt();
                    list.add(num);
                    System.out.println(num + " added to the end of the list.");
                    break;
                case 2:
                    if (list.isEmpty()) {
                        System.out.println("List is empty.");
                    } else {
                        System.out.print("Enter an integer to remove: ");
                        num = scanner.nextInt();
                        boolean removed = list.remove(Integer.valueOf(num));
                        if (removed) {
                            System.out.println(num + " removed from the list.");
                        } else {
                            System.out.println(num + " not found in the list.");
                        }
                    }
                    break;
                case 3:
                    System.out.println("Size of the list: " + list.size());
                    break;
                case 4:
                    System.out.print("Enter an integer to check: ");
                    num = scanner.nextInt();
                    boolean contains = list.contains(Integer.valueOf(num));
                    if (contains) {
                        System.out.println(num + " found in the list.");
                    } else {
                        System.out.println(num + " not found in the list.");
                    }
                    break;
                case 5:
                    if (list.isEmpty()) {
                        System.out.println("List is empty.");
                    } else {
                        System.out.print("Elements of the list: ");
                        for (Integer i : list) {
                            System.out.print(i + " ");
                        }
                        System.out.println();
                    }
                    break;
                case 6:
                    System.out.println("Exiting program...");
                    scanner.close();
                    System.exit(0);
                    break;
                default:
                    System.out.println("Invalid choice. Try again.");
                    break;
            }
        }
    }
}

Advantages:

1. Dynamic size: A singly linked list can grow or shrink as needed, allowing for dynamic allocation of memory.
2. Efficient insertion and deletion: Insertion and deletion operations can be performed in constant time (O(1)) if the position of the element to be inserted or deleted is known.
3. Low memory overhead: Singly linked lists have a low memory overhead compared to other data structures like arrays, which may require extra memory to allocate unused space.
4. Flexibility: Singly linked lists can be used to implement other abstract data types like stacks, queues, and hash tables.

Disadvantages:

1. Sequential access only: Singly linked lists can only be traversed in one direction, which means that random access to elements is not possible. This can make searching for an element slower than in an array or a doubly linked list.
2. No constant-time access to elements: Unlike arrays, which allow for constant-time access to elements by index, singly linked lists require traversal of the list from the head to the desired element. This can result in slower access times for large lists.
3. Extra memory required for each node: Each node in a singly linked list requires extra memory to store the reference to the next node. This can add up to a significant amount of memory overhead for large lists.
4. Inefficient memory usage: Singly linked lists can waste memory if elements are frequently inserted or deleted in the middle of the list, as this requires the creation or deletion of multiple nodes. This can lead to inefficient memory usage and increased memory fragmentation over time.