Question

1. Implement a method called count with the following signature:

public int count();

such that the method returns the number of nodes currently contained in the list. The method must compute this number by traversing the entire list.

2. Implement a method called sndLast with the following signature:

public E sndLast();

such that the method returns the data stored at the second-to-last node of the linked list. If the size of the list is less than 2, then the method should return null. Hint: Recall, the last node of the list has its next eld set to null.

3. Implement a method called reverse with the following signature:

public SinglyLinkedList reverse();

such that the method returns a reference to a new linked list, containing the same elements as the current list, except in the reverse order. Page

// SinglyLinkedList.java

package LinkedLists;

public class SinglyLinkedList<E> {
   private static class node<E> {
       private node<E> next; // Pointer to the next node in the list.
       private E data; //Contains a reference to the data stored at this node.
       public node(E e, node<E> n) {
           next = n;
           data = e;
       }
       public node<E> getNext() { return next; }
       public E getData() { return data; }
       public void setNext(node<E> n) { next = n; }
   }
   private node<E> head = null; //Pointer to the head of the list.
   private node<E> tail = null; //Pointer to the tail of the list.
   private int size = 0; //Track the number of nodes in the list.
   public SinglyLinkedList() { }
   //Methods begin here//
   public int getSize() { return size; }
   public boolean isEmpty() { return size == 0; }
   public E first() {
       if(isEmpty()) {
           return null;
       }
       return head.getData();
   }
   public E last() {
       if(isEmpty()) {
           return null;
       }
       return tail.getData();
}
   public void addFirst(E e) {
       node<E> n = new node<>(e,head);
       head = n;
       if(isEmpty()) {
           tail = n;
       }
       size++}   
}
   public void addLast(E e) {
       node<E> n = new node<>(e, null);
       if(isEmpty()) {
           head = n;
       } else {
           tail.setNext(n);
}
       tail = n;
       size++;
}
   public E removeFirst() {
       // Check for the empty list.
       if(isEmpty()) {
           return null;
       }
       E val = head.getData();
       head = head.getNext();
       size--;
       if(size == 0) {
           tail = null;
       }
       return val;
}
   // WARNING: print method is not efficient in general.
   public void print() {
       node<E> walk = head;
       int counter = 0;
       while(walk != null) {
           System.out.println("Count = " + (counter+1) + " " + walk.getData());          
           walk = walk.getNext();
           counter++;
       }  
}
   // WARNING: find is not efficient in general.
   public boolean find(E x) {
       node<E> walk = head;
       while(walk != null) {
           if(walk.getData().equals(x)) {
               return true;
           }
           walk = walk.getNext();
       }
       return false;
   }
   // Equality for linked lists given by definition.
   public boolean equals(Object o) { // accept ANY parameter value
       if( o == null) { return false; {
       if(getClass() != o.getClass()) { return false; } // Return false if types are not the same
       SinglyLinkedList y = (SinglyLinkedList) o;
       if(size != y.getSize()) { return false; }
       node walkA = head; // Start of THIS list.
       node walkB = y.head;
       while(walkA != null) {
           if(!walkA.getData().equals(walkB.getData())) { return false; }
           walkA = walkA.getNext();
           walkB = walkB.getNext();  
}
       return true;
}
   public SinglyLinkedList<E> clone() throws CloneNotSupportedException {
       SinglyLinkedList<E> other = (SinglyLinkedList<E>) super.clone();
       if(size > 0) { //Build independent chain of nodes.  
       }
   }
}

//SinglyLinkedListTest.java

package applications;

import LinkedLists.SinglyLinkedList;
import java.util.Random;

public class SinglyLinkedListTest {

   public static class Record {
       private int id;
       private String name;
       private double grade;
       public Record(int i, String n, double g) {
           id = i;
           name = n;
           grade = g;
       }
       public String getName() { return name; }
       public double getGrade() { return grade; }
       public String toString() {return name + " " + grade;
       }
   }
   public static void main(String[] args) {
       SinglyLinkedList<Record> L4 = new SinglyLinkedList<>();
       L4.addLast(new Record(0, "name", 4.0));
       L4.addLast(new Record(1, "name2", 3.6));
       //L4.print();
      
       SinglyLinkedList<Integer> L1 = new SinglyLinkedList<>();
       L1.addLast(35); // 35 is auto-boxed to type Integer
       L1.addLast(67);
       L1.addLast(99);
       L1.addLast(202);
       L1.addLast(11);
       L1.addLast(302);
       //L1.print();
      
       SinglyLinkedList<String> L2 = new SinglyLinkedList<>();
       L2.addLast("hello");
       L2.addLast("world");
       L2.addLast("java");
       //L2.print();
      
       SinglyLinkedList<Double> L3 = new SinglyLinkedList<>();
       L3.addLast(3.14);
       L3.addLast(3.1415);
       L3.addFirst(2.7);
       //L3.print();
      
       int size = 100;
       SinglyLinkedList<Integer> L5 = new SinglyLinkedList<>();
       Random r = new Random();
      
       System.out.println("Starting random numbers!");
       for(int i = 0; i < size; i++) {
          
           L5.addLast(r.nextInt());
      
          
       }
       System.out.println("End of list generation!");
       //L5.print();
       L5.addLast(r.nextInt());
       //L5.print();
       System.out.println("End of insert operation!");
       L5.addLast(0);
       System.out.println(L5.find(0));
      
       System.out.println(L2.equals(L5));
      
       SinglyLinkedList<String> L6 = new SinglyLinkedList<>();
       L6.addLast("hello");
       L6.addLast("world");
       L6.addLast("java");
      
       System.out.println(L2 == L6);
       System.out.println(L2.equals(L6));
      
   }
  
}

Answer 1

Implemented the required methods in SinglyLinkedList.java file. Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// SinglyLinkedList.java

public class SinglyLinkedList<E> {

      private static class node<E> {

            private node<E> next; // Pointer to the next node in the list.

            private E data; // Contains a reference to the data stored at this node.

            public node(E e, node<E> n) {

                  next = n;

                  data = e;

            }

            public node<E> getNext() {

                  return next;

            }

            public E getData() {

                  return data;

            }

            public void setNext(node<E> n) {

                  next = n;

            }

      }

      private node<E> head = null; // Pointer to the head of the list.

      private node<E> tail = null; // Pointer to the tail of the list.

      private int size = 0; // Track the number of nodes in the list.

      public SinglyLinkedList() {

      }

      // Methods begin here//

      public int getSize() {

            return size;

      }

      public boolean isEmpty() {

            return size == 0;

      }

      public E first() {

            if (isEmpty()) {

                  return null;

            }

            return head.getData();

      }

      public E last() {

            if (isEmpty()) {

                  return null;

            }

            return tail.getData();

      }

      public void addFirst(E e) {

            node<E> n = new node<E>(e, head);

            head = n;

            if (isEmpty()) {

                  tail = n;

            }

            size++;

      }

      public void addLast(E e) {

            node<E> n = new node<E>(e, null);

            if (isEmpty()) {

                  head = n;

            } else {

                  tail.setNext(n);

            }

            tail = n;

            size++;

      }

      public E removeFirst() {

            // Check for the empty list.

            if (isEmpty()) {

                  return null;

            }

            E val = head.getData();

            head = head.getNext();

            size--;

            if (size == 0) {

                  tail = null;

            }

            return val;

      }

      // WARNING: print method is not efficient in general.

      public void print() {

            node<E> walk = head;

            int counter = 0;

            while (walk != null) {

                  System.out.println("Count = " + (counter + 1) + " "

                              + walk.getData());

                  walk = walk.getNext();

                  counter++;

            }

      }

      // WARNING: find is not efficient in general.

      public boolean find(E x) {

            node<E> walk = head;

            while (walk != null) {

                  if (walk.getData().equals(x)) {

                        return true;

                  }

                  walk = walk.getNext();

            }

            return false;

      }

      // Equality for linked lists given by definition.

      public boolean equals(Object o) { // accept ANY parameter value

            if (o == null) {

                  return false;

            }

            if (!(o instanceof SinglyLinkedList)) {

                  return false;

            } // Return false if types are not the same

            SinglyLinkedList y = (SinglyLinkedList) o;

            if (size != y.getSize()) {

                  return false;

            }

            node walkA = head; // Start of THIS list.

            node walkB = y.head;

            while (walkA != null) {

                  if (!walkA.getData().equals(walkB.getData())) {

                        return false;

                  }

                  walkA = walkA.getNext();

                  walkB = walkB.getNext();

            }

            return true;

      }

      public SinglyLinkedList<E> clone() throws CloneNotSupportedException {

            SinglyLinkedList<E> other = new SinglyLinkedList<E>();

            // looping and adding each element from this list to other

            for (node<E> temp = head; temp != null; temp = temp.next) {

                  other.addLast(temp.data);

            }

            return other;

      }

      // returns the number of nodes currently on the list

      public int count() {

            int c = 0;

            // looping and counting nodes until the end

            for (node<E> temp = head; temp != null; temp = temp.next) {

                  c++;

            }

            return c;

      }

      // returns the second last element on the list

      public E sndLast() {

            // if count is less than 2, returning null

            if (count() < 2) {

                  return null;

            }

            // taking a reference to head node

            node<E> temp = head;

            // looping until next of next of temp becomes null, or in other words,

            // temp becomes the second last node

            while (temp.next.next != null) {

                  // advancing temp

                  temp = temp.next;

            }

            // returning data

            return temp.data;

      }

      // returns a new list with elements reversed

      public SinglyLinkedList reverse() {

            // creating a list

            SinglyLinkedList<E> reversedList = new SinglyLinkedList<E>();

            // looping through each node

            for (node<E> temp = head; temp != null; temp = temp.next) {

                  // adding data to first position of the reversed list, so that

                  // elements will be in reverse order.

                  reversedList.addFirst(temp.data);

            }

            return reversedList;

      }

}