Question

9.7 LAB: Inserting an integer in descending order (doubly-linked list)

Given main() and an IntNode class, complete the IntList class (a linked list of IntNodes) by writing the insertInDescendingOrder() method to insert new IntNodes into the IntList in descending order.

Ex. If the input is:

3 4 2 5 1 6 7 9 8 -1

the output is:

9 8 7 6 5 4 3 2 1

Sortedlist.java

import java.util.Scanner;

public class SortedList {

public static void main (String[] args) {
Scanner scnr = new Scanner(System.in);
IntList intList = new IntList();
IntNode curNode;
int num;

num = scnr.nextInt();

while (num != -1) {
// Insert into linked list in descending order   
curNode = new IntNode(num);
intList.insertInDescendingOrder(curNode);
num = scnr.nextInt();
}
  
intList.printIntList();
}
}

intlist.java

import java.util.Scanner;

public class SortedList {

public static void main (String[] args) {
Scanner scnr = new Scanner(System.in);
IntList intList = new IntList();
IntNode curNode;
int num;

num = scnr.nextInt();

while (num != -1) {
// Insert into linked list in descending order   
curNode = new IntNode(num);
intList.insertInDescendingOrder(curNode);
num = scnr.nextInt();
}
  
intList.printIntList();
}
}

intnode.java

public class IntNode {
public int dataVal;
public IntNode prevNode; // Reference to the previous node   
public IntNode nextNode; // Reference to the next node   

public IntNode() {
dataVal = 0;
prevNode = null;
nextNode = null;
}

// Constructor   
public IntNode(int dataInit) {
this.dataVal = dataInit;
this.prevNode = null;
this.nextNode = null;
}

// Constructor   
public IntNode(int dataInit, IntNode prevNode, IntNode newNextNode) {
this.dataVal = dataInit;
this.prevNode = prevNode;
this.nextNode = newNextNode;
}

// Print node information
public void printNodeData() {
System.out.print(this.dataVal);
}
}

Answer 1

//IntNode.java

public class IntNode {

      

       public int dataVal;

       public IntNode prevNode; // Reference to the previous node  

       public IntNode nextNode; // Reference to the next node  

       public IntNode() {

             dataVal = 0;

             prevNode = null;

             nextNode = null;

       }

      

       // Constructor  

       public IntNode(int dataInit) {

             this.dataVal = dataInit;

             this.prevNode = null;

             this.nextNode = null;

       }

       // Constructor  

       public IntNode(int dataInit, IntNode prevNode, IntNode newNextNode) {

             this.dataVal = dataInit;

             this.prevNode = prevNode;

             this.nextNode = newNextNode;

       }

      

       // Print node information

       public void printNodeData() {

             System.out.print(this.dataVal);

       }

}

//end of IntNode.java

//IntList.java

public class IntList {

      

       private IntNode head;

      

       // constructor to create an empty list

       public IntList()

       {

             head = null;

       }

      

       // method to insert the nodes in descending order

       public void insertInDescendingOrder(IntNode node)

       {

             // if empty list, make the node the first element

             if(head == null )

                    head = node;

             // if value of node > value at head, insert it at the front

             else if(head.dataVal < node.dataVal)

             {

                    node.nextNode = head;

                    head.prevNode = node;

                    head = node;

             }else

             {

                    IntNode temp = head;

                    // loop to continue till we get the position of the insert or we reach the element at the end of the list

                    while(temp.nextNode != null)

                    {

                           // check if this is the position of insert, then insert the node

                           if(temp.dataVal < node.dataVal)

                           {

                                 temp.prevNode.nextNode = node;

                                 node.prevNode = temp.prevNode;

                                 node.nextNode = temp;

                                 temp.prevNode= node;

                                 return;

                           }

                          

                           temp = temp.nextNode;

                    }

                   

                    // if last value is less than node value

                    if(temp.dataVal < node.dataVal)

                    {

                           node.prevNode = temp.prevNode;

                           temp.prevNode.nextNode = node;

                           node.nextNode = temp;

                           temp.prevNode= node;

                    }else // insert at the last

                    {

                           node.prevNode = temp;

                           temp.nextNode = node;

                           node.nextNode = null;

                    }

             }

       }

      

       // method to print the list

       public void printIntList()

       {

             if(head == null) // empty list

             {

                    System.out.println("Empty List");

             }else // non-empty list

             {

                    IntNode curr = head;

                    // loop to print the elements of the list

                    while(curr != null)

                    {

                           System.out.print(curr.dataVal+" ");

                           curr = curr.nextNode;

                    }

             }

       }

}

//end of IntList.java

//SortedList.java

import java.util.Scanner;

public class SortedList {

public static void main (String[] args) {
Scanner scnr = new Scanner(System.in);
IntList intList = new IntList();
IntNode curNode;
int num;

num = scnr.nextInt();

while (num != -1) {
// Insert into linked list in descending order   
curNode = new IntNode(num);
intList.insertInDescendingOrder(curNode);
num = scnr.nextInt();
}
  
intList.printIntList();
}
}

//end of SortedList.java

Output: