The SinglyLinkedList code

 

package HW4_Skeleton;

public class SinglyLinkedList {

   private SinglyLinkedNode head;
   private int size;

   public SinglyLinkedList(){
       this.head = null;
       this.size = 0;
   }

   // add a new node at the beginning of the list
   public void addAtBeginning(int value){
       SinglyLinkedNode newNode = new SinglyLinkedNode(value);

       newNode.setNextNode(this.head);
       this.head=newNode;

       this.size++;
   }

   public void reverse() {

   }

 

 

   public SinglyLinkedNode getHead() { return this.head; }

   public int getSize() {
       return this.size;
   }

   @Override
   public String toString(){
       String str = "";
       SinglyLinkedNode curr = this.head;
       while(curr != null){
           str += "->" + curr.getData();
           curr = curr.getNextNode();
       }
       return str;
   }

}

 

The SinglyLinkedListStarter

 

package HW4_Skeleton;

public class SinglyLinkedListStarter {

 

   public static void main(String args[]) {
       
       SinglyLinkedList myLinkedList = new SinglyLinkedList();

       myLinkedList.addAtBeginning(4);
       myLinkedList.addAtBeginning(7);
       myLinkedList.addAtBeginning(1);
       myLinkedList.addAtBeginning(2);

       System.out.println(myLinkedList.toString());
       System.out.println(myLinkedList.getSize());
       System.out.println(myLinkedList.getHead());

       myLinkedList.reverse();

       System.out.println(myLinkedList.toString());
       System.out.println(myLinkedList.getSize());
       System.out.println(myLinkedList.getHead());

   }
}
 

The SinglyLinkedNode

 

package HW4_Skeleton;

public class SinglyLinkedNode {
   private int item;
   private SinglyLinkedNode next;

   public SinglyLinkedNode(int data, SinglyLinkedNode nextNode) {
       this.item = data;
       this.next = nextNode;
   }

   public SinglyLinkedNode(int data) {
       this(data, null);
   }

   public int getData() {
       return item;
   }

   public SinglyLinkedNode getNextNode() {
       return next;
   }

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

   public void setNextNode(SinglyLinkedNode nextNode) {
       this.next = nextNode;
   }

   @Override
   public String toString() {
       return ""+this.item;
   }

}

Transcribed Image Text:

(2) (25 points) In the downloaded skeleton code archive, you find the classes SinglyLinkedNode, SinglyLinkedList, and SinglyLinkedListStarter. This time, you are working with a singly linked list. However, it is not double-ended. Each node in this list in contrast to the previous task only maintains the location of the next node and not the previ- ous one. Also, the list maintains a pointer to the head node only. It does not provide a tail pointer. You can test your code using the class SinglyLinkedListStarter. In this problem, you will write the method reverse () in the class SinglyLinkedList that reverses a singly linked list. Your algorithm must have a worst-case runtime of O(n) and a worst-case space complexity of O(1) beyond the input. For example, if the list contains the integers 5 7 1 2 3 in this order (the head pointer refers to the node containing the item value 5) then the reversed list will look like: 32175 (the head pointer now refers to the node containing the item value 3). That means that you need to modify (2) (25 points) In the downloaded skeleton code archive, you find the classes SinglyLinkedNode, SinglyLinkedList, and SinglyLinkedListStarter. This time, you are working with a singly linked list. However, it is not double-ended. Each node in this list in contrast to the previous task only maintains the location of the next node and not the previ- ous one. Also, the list maintains a pointer to the head node only. It does not provide a tail pointer. You can test your code using the class SinglyLinkedListStarter. In this problem, you will write the method reverse () in the class SinglyLinkedList that reverses a singly linked list. Your algorithm must have a worst-case runtime of O(n) and a worst-case space complexity of O(1) beyond the input. For example, if the list contains the integers 5 7 1 2 3 in this order (the head pointer refers to the node containing the item value 5) then the reversed list will look like: 32175 (the head pointer now refers to the node containing the item value 3). That means that you need to modify