Categories
Class 12

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);
            }
        }
    }
}

Question 1: A linked list is formed from the objects of the class Node. The class structure of the Node is given below:

class Node {
    int num;
    Node next;
}

Write an algorithm or a method to count the nodes that contain only odd integers from an existing linked list and returns the count. The method declaration is as follows: int countOdd(Node startPtr)

int countOdd(int startPtr){
    if(startPtr == null)
        return 0;
    else if(startPtr.num % 2 == 1)
        return 1 + countOdd(startPtr.next);
    else
        return coundOdd(startPtr.next);
}

Question 2: A linked list is formed from the objects of the class:

class Node{
    int num;
    Node next;
}

Write an algorithm or a method to insert a node at the beginning of an existing linked list. The method declaration is as follows: void insertNode(Nodes starPtr, int n)

void insertNode(Node startPtr, int n){
    Node d = new Node(n);
    if(startPtr == null)
        startPtr = d;
    else{
        d.next = startPtr;
        startPtr = d;
    }
}

Question 3: A linked list is formed from the objects of the class:

class Node{
    int data;
    Node next;
}

Write an algorithm or a method to concatenate two linked lists.

public void concatenate(Node list){
    if(start == null){
        start = list;
        return;
    }
    Node s = start;
    while(s.next != null)
        s = s.next;
    s.next = list;
}

Question 4: Write a method search() to search for an item in a linked list. Also print its position in the list if it is found, otherwise display a proper message.

public void search(int d){
    if(start == null){
        System.out.println(d + " not found.");
        return;
    }
    Node s = start;
    int pos = 1;
    while(s != null){
        if(d == s.data){
            System.out.println(d + " found at position " + pos);
            return;
        }
        s = s.next;
        pos++;
   }
   System.out.println(d + " not found.");
}

9 replies on “Linked List Java Program”

Linked Lists are made up of nodes. Each node stores the individual data of the linked list.

Sir,How to create applets in BlueJ 4.2.2?
Sir,What is the best website for video lectures in Python?

I have never used BlueJ for creating applets. I have used text editors like Sublime Text Editor.

Linked List program can be executed in BlueJ just like any other program. Visit this post to get access to the source code. Name the file with the class that contains the main() method.

Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle.
Define a class Cqueue with the following details:
Class name : Cqueue Data member/instance variables:
ele[ ] : array to hold the integer elements cap : stores the maximum capacity of the array
front : to point the index of the front
rear : to point the index of the rear. Member functions/methods: Cqueue(int max) : constructor to initialize the data member cap = max, front = rear = 0 and create the integer array
void insert(int v) : to add integers from the front index if possible else display the message(“full from rear”)
int delete( ) : to remove and return elements from rear, if any, else returns -999
void display() : to display elements of circular queue
Specify the class Cqueue giving the details of void insert(int) and int delete( ). Assume that the other functions have been defined. The main( ) function and algorithm need NOT be written.

public void insert(int v){
if((rear + 1) % cap != front){
rear = (rear + 1) % cap;
ele[rear] = v;
}
else
System.out.println(“Full from rear!”);
}
public int delete(){
if(front != rear){
int v = ele[front];
front = (front + 1) % cap;
return ele[front];
}
else
return -999;
}

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.