Question

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 (READ ONLY!!!)

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

public class IntList {

// Linked list nodes

public IntNode headNode;

public IntNode tailNode;

public IntList() {

// Front of nodes list

headNode = null;

tailNode = null;
}

// prepend

public void prepend(IntNode newNode) {

if (headNode == null) { // list empty

headNode = newNode;

tailNode = newNode;

} else {

newNode.nextNode = headNode;

headNode = newNode;

}

}

// insertAfter

public void insertAfter(IntNode curNode, IntNode newNode) {

if (headNode == null) { // List empty

headNode = newNode;

tailNode = newNode;

} else if (curNode == tailNode) { // Insert after tail

tailNode.nextNode = newNode;

tailNode = newNode;

} else {

newNode.nextNode = curNode.nextNode;

curNode.nextNode = newNode;

}

}

// method to insert a node in proper position so that the list will be in

// sorted order

public void insertInAscendingOrder(IntNode newNode) {

// checking if headNode is null (empty list - case 1)

if (headNode == null) {

// adding as both head node and tail node

headNode = newNode;

tailNode = newNode;

// returning from function

return;

}

// checking if new element could be added before current head node (case

// 2)

if (newNode.dataVal < headNode.dataVal) {

// adding before head node and updating head node

newNode.nextNode = headNode;

headNode = newNode;

return;

}

// taking a reference to first two nodes

IntNode current = headNode;

IntNode nextNode = headNode.nextNode;

// looping and checking if the element can be added in between any pairs

// of node (case 3)

while (nextNode != null) {

if (newNode.dataVal >= current.dataVal

&& newNode.dataVal <= nextNode.dataVal) {

// new node can be added between current and next node

newNode.nextNode = nextNode;

current.nextNode = newNode;

return;

}

// advancing to next pair of nodes

current = nextNode;

nextNode = current.nextNode;

}

// at the end, if the new node is still not added, adding to tail (case

// 4)

tailNode.nextNode = newNode;

tailNode = newNode;

}

public void printIntList() {

IntNode curNode;

curNode = headNode;

while (curNode != null) {

curNode.printNodeData();

System.out.print(" ");

curNode = curNode.nextNode;

}

}

}

____________________________________________________________________________________________________________________________________________________

IntNode.java (READ ONLY!!!!)

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

class IntList {

        // Linked list nodes

        public IntNode headNode;
        public IntNode tailNode;

        public IntList() {
                // Front of nodes list
                headNode = null;
                tailNode = null;
        }

        // prepend
        public void prepend(IntNode newNode) {
                if (headNode == null) { // list empty
                        headNode = newNode;
                        tailNode = newNode;
                } else {
                        newNode.nextNode = headNode;
                        headNode = newNode;
                }
        }

        // insertAfter
        public void insertAfter(IntNode curNode, IntNode newNode) {

                if (headNode == null) { // List empty
                        headNode = newNode;
                        tailNode = newNode;
                } else if (curNode == tailNode) { // Insert after tail
                        tailNode.nextNode = newNode;
                        tailNode = newNode;
                } else {
                        newNode.nextNode = curNode.nextNode;
                        curNode.nextNode = newNode;
                }
        }

        // method to insert a node in proper position so that the list will be in
        // sorted order
        public void insertInAscendingOrder(IntNode newNode) {

                // checking if headNode is null (empty list - case 1)
                if (headNode == null) {
                        // adding as both head node and tail node
                        headNode = newNode;
                        tailNode = newNode;
                        // returning from function
                        return;
                }

                // checking if new element could be added before current head node (case
                // 2)
                if (newNode.dataVal < headNode.dataVal) {
                        // adding before head node and updating head node
                        newNode.nextNode = headNode;
                        headNode = newNode;
                        return;
                }

                // taking a reference to first two nodes
                IntNode current = headNode;
                IntNode nextNode = headNode.nextNode;
                
                // looping and checking if the element can be added in between any pairs
                // of node (case 3)
                while (nextNode != null) {

                        if (newNode.dataVal >= current.dataVal
                                        && newNode.dataVal <= nextNode.dataVal) {
                                // new node can be added between current and next node
                                newNode.nextNode = nextNode;
                                current.nextNode = newNode;
                                return;
                        }

                        // advancing to next pair of nodes
                        current = nextNode;
                        nextNode = current.nextNode;
                }

                // at the end, if the new node is still not added, adding to tail (case
                // 4)
                tailNode.nextNode = newNode;
                tailNode = newNode;
        }

        public void printIntList() {
                IntNode curNode;
                curNode = headNode;

                while (curNode != null) {
                        curNode.printNodeData();
                        System.out.print(" ");
                        curNode = curNode.nextNode;
                }
        }

        public void insertInDescendingOrder(IntNode newNode) {
                // checking if headNode is null (empty list - case 1)
                if (headNode == null) {
                        // adding as both head node and tail node
                        headNode = newNode;
                        tailNode = newNode;
                        // returning from function
                        return;
                }

                // checking if new element could be added before current head node (case
                // 2)
                if (newNode.dataVal > headNode.dataVal) {
                        // adding before head node and updating head node
                        newNode.nextNode = headNode;
                        headNode = newNode;
                        return;
                }

                // taking a reference to first two nodes
                IntNode current = headNode;
                IntNode nextNode = headNode.nextNode;
                
                // looping and checking if the element can be added in between any pairs
                // of node (case 3)
                while (nextNode != null) {

                        if (newNode.dataVal <= current.dataVal
                                        && newNode.dataVal >= nextNode.dataVal) {
                                // new node can be added between current and next node
                                newNode.nextNode = nextNode;
                                current.nextNode = newNode;
                                return;
                        }

                        // advancing to next pair of nodes
                        current = nextNode;
                        nextNode = current.nextNode;
                }

                // at the end, if the new node is still not added, adding to tail (case
                // 4)
                tailNode.nextNode = newNode;
                tailNode = newNode;
                
        }

}

please upvote. if any issues, please ask in comments.