Question

THIS QUESTION IS BASED UPON JAVA PROGRAMMING.

Exercise 1 In this exercise, you will add a method swapNodes to SinglyLinkedList class. This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same nodes, etc. Write the main method to test the swapNodes method. Hint: You may need to traverse the list.

Exercise 2 In this exercise, you will use the DoublyLinkedList implementation of the textbook. Write a method for concatenating two doubly-linked lists L and M, with header and trailer sentinel nodes, into a single list L′. Write a main method to test the new method. Hint: Connect the end of L into the beginning of M.

Answer 1

Exercise 1 :

In Exercise 1, first we have to check if two nodes are equal then don't need to swap. Otherwise, first find the node1 from the linkedlist and store the prev and curr node and same for node2 then after swap the nodes. If the any node is not present then swapping is not possible for two nodes.

sawapTwoNodes() method will swap the two nodes of the linkedlist.

Program:-

public class SinglyLinkedList {
    
    class Node {
        
        // LinkedList node contain integer
        public int item;
        
        // points to the next node
        public Node next;
        
        // prarameterized constructor which create new node for the linkedlist
        public Node(int item){
            
            this.item = item;
            this.next = null;
        }
        
        // prarameterized constructor which add a node with the linkedlist
        public Node(int item, Node next){
            
            this.item = item;
            this.next = next;
        }
    }
    
    // it will point to the head node of the linked list
    private Node head;
    
    // add node at the head of linked list
    public void addFirst(int a){
        
        // add newNode as a head node
        head = new Node(a, head);
    }
    
    
    // This method print the whole linkedlist
    public void printList(){
        
        Node node = head; 
        while (node != null) 
        { 
            // print last node without aerrow
            if(node.next == null)
                System.out.print(node.item); 
            else
                System.out.print(node.item+" -> "); 
            
            node = node.next; 
        } 
    }
    
    // This method will swap the node if they are present in the linkedlist
    public void swapTwoNodes(int node1, int node2){
        
        // if two nodes are equal then dont need to swap that nodes
        if(node1 == node2){
            System.out.println("\nBoth Nodes are equal");
            return;
        }
        
        // search node1 from the linkedlist and save prev and curr node
        Node prevNode1 = null, currNode1 = head; 
        while (currNode1 != null && currNode1.item != node1) 
        { 
            // store previous node
            prevNode1 = currNode1; 
            
            // go to the next node
            currNode1 = currNode1.next; 
        } 
  
        // search node 2 from the linkedlist and save prev and curr node
        Node prevNode2 = null, currNode2 = head; 
        while (currNode2 != null && currNode2.item != node2) 
        { 
            // store previous node
            prevNode2 = currNode2;
            
            // go to the next node
            currNode2 = currNode2.next; 
        } 
  
        // check whether node1 and node2 are present or not? 
        if (currNode1 == null || currNode2 == null){
            
            if(currNode1 == null)
                System.out.println("\n"+node1+" is not present in the linkedlist");
            
            if(currNode2 == null)
                System.out.println("\n"+node2+" is not present in the linkedlist");
            
            System.out.println("Sorry! Swapping is not possible");
            return;
        } 
            
  
        // If node1 is not head of linked list 
        if (prevNode1 != null){
            // prev node point to the node2
            prevNode1.next = currNode2; 
        }
        else{
            // otherwise create node2 as a head 
            head = currNode2; 
        }
  
        // If node2 is not head of linked list 
        if (prevNode2 != null){ 
            // prev node point to the node1
            prevNode2.next = currNode1; 
        }
        else{
            // otherwise create node1 as a head 
            head = currNode1; 
        }
  
        // Now Swap next pointers only  
        Node temp = currNode1.next; 
        currNode1.next = currNode2.next; 
        currNode2.next = temp; 
        
    }
    
    /*
        main() method test the swapNodes() method.
    */
    public static void main(String[] args) {
        
        SinglyLinkedList list = new SinglyLinkedList();
        
        // add fisrt node to the linked list
        list.addFirst(40);
        list.addFirst(30);
        list.addFirst(20);
        list.addFirst(10);
        
        System.out.println("\nLinked list before calling swapTwoNodes(nod1, node2): "); 
        list.printList(); 
  
        list.swapTwoNodes(20, 20); 
  
        System.out.println();
        
        System.out.println("\nLinked list after calling swapTwoNodes(node1, node2): "); 
        list.printList(); 
        
        System.out.println();
    }
}

Output :-

1> When both nodes are present

2> When both nodes are not present

3> When both nodes are equal

Exercise 2 :

In exercise 2, we will concatenate two doubly linkedlist where end of the first linked list will point to the head of second linked list.

concatenateTwoDoublyLinkedList() method will concatenate the two doublylinkedlist.

Program :-

public class DoublyLinkedList {    

    //This class repersents node for doubly linked list
    class Node{  
        
        // instance members for doubly linked list
        int item;  
        Node prev;  
        Node next;  
   
        //constructor for doubly linked list
        public Node(int item) {  
            this.item = item;  
        }  
    }  
    
    //Initially, heade and last is set to null
    Node head, last;  
   
    
    // This method addNode at the end of the doubly linked list
    public void addNodeAtTheEnd(int item) { 
        
        //Create a new node  
        Node newNode = new Node(item);  
   
        //if list is empty, head and last points to newNode  
        if(head == null) {  
            
            head = last = newNode;  
            
            //head's prev will be null  
            head.prev = null;  
            
            //last's next will be null  
            last.next = null;  
        }  
        else {  
            
            //add newNode to the end of list. last->next set to newNode  
            last.next = newNode;  
            
            //set new node prev as a last  
            newNode.prev = last;  
            
            //newNode becomes new last  
            last = newNode;  
            
            //last next will be null  
            last.next = null;  
        }  
    }  
   
    // This method will print the doubly linkedlist
    public void printList(){
        
        Node node = head; 
        while (node != null) 
        { 
            // print last node without aerrow
            if(node.next == null)
                System.out.print(node.item); 
            else
                System.out.print(node.item+" -> "); 
            
            node = node.next; 
        } 
    }
    
    public void concatenateTwoDoublyLinkedList(DoublyLinkedList list2){
        
        // if list2 is null then return;
        if(list2.head == null)
            return;
        
        // store head of the list2
        Node list2Head = list2.head;
        
        // if list1 is null then create list2 as a list1
        if(this.head == null){
            
            // store head to the first doublylinkedlist
            this.head = list2Head;
            return;
        }
        
        // now store the head to the next of last node of first doubly linked list
        this.last.next = list2Head;
        
        // connect last node of first doublylinkedlist with the head of second doubly linkedlist
        list2Head.prev = this.last;
        
        System.out.println("\nConcatenation Of Two DoublyLinkedList successful");
    }
    
    /*
        main() method test the concatenationTwoDoublyLinkedList() method.
    */
    public static void main(String[] args) {  
        
        //create first DoublyLinkedList object
        DoublyLinkedList dll1 = new DoublyLinkedList();  
        
        // add node into the first doubly linkedlist
        dll1.addNodeAtTheEnd(10);
        dll1.addNodeAtTheEnd(20);
        dll1.addNodeAtTheEnd(30);
        dll1.addNodeAtTheEnd(40);
        
        //create second DoublyLinkedList object
        DoublyLinkedList dll2 = new DoublyLinkedList();  
        
        // add node into the second doubly linkedlist
        dll2.addNodeAtTheEnd(50);
        dll2.addNodeAtTheEnd(60);
        dll2.addNodeAtTheEnd(70);
        dll2.addNodeAtTheEnd(80);
        
        // display first linkedlist
        System.out.println("\nFirst DoublyLinkedList : ");
        dll1.printList();
        
        // display second linkedlist
        System.out.println("\nSecond DoublyLinkedList : ");
        dll2.printList();
        
        // concatenate above two linkedlist
        dll1.concatenateTwoDoublyLinkedList(dll2);
        
        // print concatenated doublylinkedlist
        System.out.println("\nConcatenated DoublyLinkedList");
        dll1.printList();
        
        System.out.println();
    }  
}

Output:-

I mentioned the printList() method in above two Exercise (1 & 2) which will print the whole linkedlist.

I hope you will understand above two programs.

Do you feel needful and useful then please upvote me.

Thank you.