Need help with a Java problem OrderedLinkedList.java package orderedList; public

Question

Need help with a Java problem

OrderedLinkedList.java

package orderedList;

public class OrderedLinkedList<Item extends Comparable<? super Item>> {

   private class Node {
       private Item data;
       private Node next;

       public Node(Item data) {
           this.data = data;
           this.next = null;
       }

       public Item getData() {
           return this.data;
       }

       public Node getNext() {
           return this.next;
       }

       public void setData(Item data) {
           this.data = data;
       }

       public void setNext(Node next) {
           this.next = next;
       }
   }

   private Node head;

   public OrderedLinkedList() {
       head = null;
   }

   public void insert(Item newData) {
       // Create a new Node containing newData.
       // Declare two Node reference variables, previous (intialized to null)
       // and current (initialized to head).
       // while true {
       //     if current == null or newData is less then current.getData() then {
       //         // If current is null, that means this new node is being inserted
       //         // at the end. If not null, it's being inserted elsewhere.
       //         newNode.setNext(current)
       //         if previous == null then {
       //             // Special case: Inserting new node as first node in the linked list.
       //             head = newNode
       //         } else {
       //             previous.setNext(newNode)
       //         }
       //         return
       //     }
       //     previous = current
       //     current = current.getNext()
       // }
       //
   }

   public void remove(Item oldData) {
       // Declare two Node reference variables, previous (intialized to null)
       // and current (initialized to head).
       // while current != null {
       //     if current.getData() is equal to oldData then {
       //         if previous == null then {
       //             // Special case: Removing the first node in the linked list.
       //             head = head.getNext()
       //         } else {
       //             previous.setNext(current.getNext())
       //         }
       //         return
       //     }
       //     previous = current
       //     current = current.getNext()
       // }
   }

   public String toString() {
       String s = "[";
       boolean firstItem = true;
       for (Node current = head; current != null; current = current.getNext()) {
           if (firstItem) {
               firstItem = false;
               s += current.getData();
           } else {
               s += ", " + current.getData();
           }
       }
       s += "]";
       return s;
   }

}

Create a package called orderedList. Copy into it the incompletely written reference class orderedLinkedList.java. You will also place into a program class TestOLL.java written according to the instructions below. Specifications The ordered linked list class is a generic class that holds values in a linked list in ascending order Looking at the code, you will see that the insert and remove methods contain pseudocode. You are to translate that pseudocode into Java After doing that, write a program calledTestOLL. java that tests your updated linked list class. It should: 1. Declare and initialize an empty ordered linked list for strings, 2. Fill it with the strings: "goodbye adios buenos dias bonjour adieu "guten Tag", hello and "auf Wiedersehen 3. Print the list out. This can be done in a single stdout.println(list) statement because the method tos tring is defined for the linked list class.

Explanation / Answer

class LinkedList
{
    Node head; // head of list

    /* Linked list Node*/
    class Node
    {
        int data;
        Node next;
        Node(int d) {data = d; next = null; }
    }

    /* function to insert a new_node in a list. */
    void sortedInsert(Node new_node)
    {
         Node current;

         /* Special case for head node */
         if (head == null || head.data >= new_node.data)
         {
            new_node.next = head;
            head = new_node;
         }
         else {

            /* Locate the node before point of insertion. */
            current = head;

            while (current.next != null &&
                   current.next.data < new_node.data)
                  current = current.next;

            new_node.next = current.next;
            current.next = new_node;
         }
     }
*Utility functions*/

    /* Function to create a node */
    Node newNode(int data)
    {
       Node x = new Node(data);
       return x;
    }

     /* Function to print linked list */
     void printList()
     {
         Node temp = head;
         while (temp != null)
         {
            System.out.print(temp.data+" ");
            temp = temp.next;
         }
     }

     /* Drier function to test above methods */
     public static void main(String args[])
     {
         LinkedList llist = new LinkedList();
         Node new_node;
         new_node = llist.newNode(5);
         llist.sortedInsert(new_node);
         new_node = llist.newNode(10);
         llist.sortedInsert(new_node);
         new_node = llist.newNode(7);
         llist.sortedInsert(new_node);
         new_node = llist.newNode(3);
         llist.sortedInsert(new_node);
         new_node = llist.newNode(1);
         llist.sortedInsert(new_node);
         new_node = llist.newNode(9);
         llist.sortedInsert(new_node);
         System.out.println("Created Linked List");
         llist.printList();
     }
}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.