Question

DATA STRUCTURES JAVA

In the doubly linked list develop the following operators:

1. Clone without duplicates. Clone a linked list by removing the duplicates.

public LinkedList cloneWithoutDuplicates( )

2. At each occurrence of element x in the list, if y is the element before x and z is the one after x, substitute y with x and z with y.

public void substitute(AnyType x, Comparator<AnyType> cmp)

3. Exchange elements in index1 and index2 with the following condition: if the element in index1 is larger than the one in index2 then swap, otherwise swap the elements in index1+1 and index2+1.

public void checkAndSwap(index1, index2)

4. Copy elements from index1 to index2, and paste them before index3 preserving the order. public void copyAndPaste(index1, index2, index3)

Answer 1

import java.util.Comparator;

public class DoublyLinkedList {
    Node head;

    class Node {
        int data;
        Node prev;
        Node next;

        Node(int d) {
            data = d;
        }
    }

    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        newNode.prev = null;
        if (head != null)
            head.prev = newNode;
        head = newNode;
    }

    public Node insertAfter(Node prev_Node, int new_data) {
        if (prev_Node == null) {
            System.out.println("The given previous node cannot be null");
            return null;
        }
        Node new_node = new Node(new_data);
        new_node.next = prev_Node.next;
        prev_Node.next = new_node;
        new_node.prev = prev_Node;
        if (new_node.next != null)
            new_node.next.prev = new_node;
        return new_node;
    }


    int[] search(int x) {
        Node temp = head;  // Initialize current
        int count = 0;
        int[] arr = null;
        while (temp != null) {
            if (temp.data == x) {
                count++;
            }
            temp = temp.next;
        }
        arr = new int[count];
        count = 0;
        int i = 0;
        while (temp != null) {
            if (temp.data == x) {
                arr[count] = i;
                count++;
            }
            temp = temp.next;
            i++;
        }
        return arr;
    }

    boolean searchvalue(int x) {
        Node temp = head;  // Initialize current
        while (temp != null) {
            if (temp.data == x)
                return true;
            temp = temp.next;
        }
        return false;
    }

    public DoublyLinkedList cloneWithoutDuplicates() {
        DoublyLinkedList linkedList = new DoublyLinkedList();
        Node temp = head;
        while (temp != null) {
            if (!linkedList.searchvalue(temp.data))
                linkedList.push(temp.data);
            temp = temp.next;
        }
        return linkedList;

    }

    public void substitute(int x, Comparator<Integer> cmp) {
        int[] arr = search(x);
        /*System.out.println("x" + arr[0]);*/
        if (arr != null) {
            Node temp = head;
            int x1 = 0;
            int y1 = 0;
            int z1 = 0;
            for (int i = 0; i < arr.length; i++) {
                temp = head;
                int count = 0;
                while (temp != null) {
                    if (count == arr[i])
                        x1 = temp.data;
                    if (count == arr[i] - 1)
                        y1 = temp.data;
                    if (count == arr[i] + 1)
                        z1 = temp.data;
                    temp = temp.next;
                    count++;
                }
               /* System.out.println("x1" + x1);
                System.out.println("y1" + y1);
                System.out.println("z1" + z1);*/

                temp = head;
                count = 0;
                while (temp != null) {
                    if (count == (arr[i] - 1))
                        temp.data = x1;
                    else if (count == (arr[i] + 1))
                        temp.data = y1;
                    temp = temp.next;
                    count++;
                }

            }
        }


    }

    public void checkAndSwap(int index1, int index2) {
        int value1 = 0;
        int value2 = 0;
        int value3 = 0;
        int value4 = 0;
        Node temp = head;
        int count = 0;
        while (temp != null) {
            if (count == index1)
                value1 = temp.data;
            if (count == index2)
                value2 = temp.data;
            if (count == index1 + 1)
                value3 = temp.data;
            if (count == index2 + 1)
                value4 = temp.data;
            temp = temp.next;
            count++;
        }
        if (value1 > value2) {
            temp = head;
            count = 0;
            while (temp != null) {
                if (count == index1)
                    temp.data = value2;
                else if (count == index2)
                    temp.data = value1;
                temp = temp.next;
                count++;
            }
        } else {
            temp = head;
            count = 0;
            while (temp != null) {
                if (count == index1 + 1)
                    temp.data = value4;
                else if (count == index2 + 1)
                    temp.data = value3;
                temp = temp.next;
                count++;
            }

        }

    }
    

    public void printlist() {
        Node node = head;
        Node last = null;
        System.out.println("Traversal in forward Direction");
        while (node != null) {
            System.out.print(node.data + " ");
            last = node;
            node = node.next;
        }
        System.out.println();
        System.out.println("Traversal in reverse direction");
        while (last != null) {
            System.out.print(last.data + " ");
            last = last.prev;
        }
    }

    public static void main(String... args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.push(1);
        dll.push(3);
        dll.push(5);
        dll.push(6);
        dll.push(2);
        dll.push(6);
        dll.printlist();
        dll.checkAndSwap(1, 2);
        dll.printlist();
        DoublyLinkedList ll = dll.cloneWithoutDuplicates();
        ll.printlist();

    }


}