Question

JAVA

Write a class to implement a list with the ability to insert a new item at any location within the list, remove an item, and search for an item. The list should use a linked list implementation. This implementation should make use of a dummy node at the head of the list and should have explict references head and previous. Add a method to the list that inserts elements in acsending order assuming the list is already sorted before each insert.

Answer 1

Hi, Please find the solution and rate the answer.

import java.util.Random;

public class Main {

    public static void main(String[] args) {
        List list = new List();
        Random random = new Random();
        list.insertAsc(new Node(random.nextInt(1000)));
        list.insertAsc(new Node(random.nextInt(1000)));
        list.insertAsc(new Node(random.nextInt(1000)));
        list.insertAsc(new Node(random.nextInt(1000)));
        list.insertAsc(new Node(random.nextInt(1000)));
        list.insertAsc(new Node(random.nextInt(1000)));
        list.insertAsc(new Node(random.nextInt(1000)));
        list.insertAsc(new Node(random.nextInt(1000)));
        list.insertAsc(new Node(random.nextInt(1000)));
        System.out.println("Before");
        list.printList();
        System.out.println("After");
        int x = random.nextInt(10000);
        System.out.println("Insert "+x+" at location 5");
        list.insertAt(new Node(x),5);
        list.printList();
        int x1 = random.nextInt(10000);
        System.out.println("Insert "+x1+" at location 5");
        list.insertAt(new Node(x1),5);
//        list.insertAt(new Node(random.nextInt(10000)),5);

        list.printList();
        list.insertAsc(new Node(100));
        Node search = list.search(new Node(100));
        System.out.println();
        System.out.println(search ==null?"Not Found":search+" Found");
    }
}

public class Node {
    private int x;
    public Node previous;
    public Node next;

    public Node(int x) {
        this.x = x;
    }

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    @Override
    public String toString() {
        return "Node{" +
                "x=" + x +
                '}';
    }
}

public class List {
    Node head = new Node(-100);//dummy node

    public void insertAsc(Node x) {
        Node temp = head;
        if (head.next == null) {
            head.next = x;
            x.previous = head;
            x.next = null;
            return;
        }
        while (temp.next!=null && temp.getX() < x.getX()) {
            temp = temp.next;
        }
        temp.previous.next = x;//realigning 4 pointer references
        x.next = temp;
        x.previous = temp.previous;
        temp.previous = x;
    }

    /**
     * @param x
     * @param loc if the loc is more than the no of elements it will place the element in th last
     */
    public void insertAt(Node x, int loc) {
        Node temp = head;
        int i = 0;
        while (temp.next != null) {
            temp = temp.next;
            i++;
            if (i == loc) {
                break;
            }
        }
        if (i == loc) {
            temp = temp.previous;
        }
        temp.next.previous = x;
        x.previous = temp;
        x.next = temp.next;
        temp.next = x;


    }

    public void remove(Node x) {
        Node temp = head;
        while (temp.next != null) {
            if (temp.getX() == x.getX()) {
                break;
            }
            temp = temp.next;
        }
        Node tempp = temp;
        temp.previous.next = temp.next;//self explanatory
        temp.next.previous = temp.previous;
        temp.next = null;
        temp.previous = null;

    }

    public Node search(Node x) {
        Node temp = head;
        while (temp.next != null) {
            if (temp.getX() == x.getX()) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

    public void printList() {
        Node temp = head;
        while (temp.next != null) {
            System.out.println(temp.next);
            temp = temp.next;

        }
    }

}

Sample output: