Linked List Java Program

A linked list is a linear data structure. It is built with a collection of nodes, where each node points to the next one.

Linked Lists are useful because they allow us to modify the size of the list at run-time.

Each node requires some space in the memory, which it requests from the heap memory.

The new keyword is used to request memory from heap.

In the following Java program, all the functionalities that are commonly required in a linked list are available.

That includes Insertion, Deletion, Searching, Traversal, and Reversal procedures.

The program is simple because the mnemonic variable names are used.

import java.io.*;
class Node{
    int data;
    Node next;
    public Node(){
        data = 0;
        next = null;
    }
    public Node(int d, Node n){
        data = d;
        next = n;
    }
}
class LinkedList{
    Node start;
    public LinkedList(){
        start = null;
    }
    public void insert(int d){
        Node n = new Node(d, null);
        boolean status = false;
        if(start == null)
            start = n;
        else if(d <= start.data){
            n.next = start;
            start = n;
        }
        else{
            Node first = start;
            Node second = start.next;
            while(second != null){
                if(d >= first.data && d <= second.data){
                    first.next = n;
                    n.next = second;
                    status = true;
                    break;
                }
                else{
                    first = second;
                    second = second.next;
                }
            }
            if(!status)
                first.next = n;
        }
    }
    public boolean delete(int d){
        boolean status = false;
        if(start == null)
            return false;
        else if(start.data == d){
            start = start.next;
            status = true;
        }
        else{
            Node first = start;
            Node second = start.next;
            while(second != null){
                if(second.data == d){
                    Node n = second.next;
                    first.next = n;
                    status = true;
                    break;
                }
                else{
                    first = second;
                    second = second.next;
                }
            }
        }
        return status;
    }
    public void search(int d){
        Node n = start;
        int pos = 1;
        while(n != null){
            if(n.data == d){
                System.out.println(d + " found at position " + pos);
                break;
            }
            else{
                n = n.next;
                pos++;
            }
        }
        if(n == null)
            System.out.println(d + " not found.");
    }
    public void reverse(){
        Node first = start;
        Node last = null;
        int size = 0;
        Node n = start;
        while(n != null){
            size++;
            n = n.next;
        }
        int mid = size / 2;
        for(int i = 1; i <= mid; i++){ 
            Node f = start; 
            Node s = start; 
            while(s != last){ 
                f = s; 
                s = s.next; 
            } 
            last = f; 
            int temp = first.data; 
            first.data = last.data; 
            last.data = temp; 
            first = first.next; 
        } 
    } 
    public void display(){ 
        Node n = start; 
        while(n != null){ 
            System.out.print(n.data + "-->;");
            n = n.next;
        }
        System.out.println("null");
    }
}
class LinkedListProgram{
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        LinkedList list = new LinkedList();
        while(true){
            System.out.println("1. Insert");
            System.out.println("2. Delete");
            System.out.println("3. Search");
            System.out.println("4. Reverse");
            System.out.println("5. Display");
            System.out.print("Enter your choice: ");
            int choice = Integer.parseInt(br.readLine());
            switch(choice){
                case 1:
                System.out.print("Data to insert: ");
                int d = Integer.parseInt(br.readLine());
                list.insert(d);
                break;
                case 2:
                System.out.print("Data to delete: ");
                d = Integer.parseInt(br.readLine());
                if(list.delete(d))
                    System.out.println(d + " deleted.");
                else
                    System.out.println(d + " not found.");
                break;
                case 3:
                System.out.print("Data to search: ");
                d = Integer.parseInt(br.readLine());
                list.search(d);
                break;
                case 4:
                list.reverse();
                System.out.println("List reversed.");
                break;
                case 5:
                list.display();
                break;
                default:
                System.out.println("Bye");
                System.exit(0);
            }
        }
    }
}

Leave a Reply

%d bloggers like this: