Question

Due in25 minutes,Java8 programming linkedlist node

Given the following definition for a Node class: public class Node<T extends Comparable<T>>{ public T val; public Node<T> prev; public Node<T> next; } Create an add method for a Sorted Linked Set. The collection is stored as a linked list, however has a few extra properties. First, as it is a Set, values stored in the list are distinct. Second, the list is sorted (so if 4, 2, 3, 1 were added, they would be stored 1, 2, 3, 4). The Comparable interface has one method, compareTo(T other) which returns a negative number if the first object is lesser, O if they are equal, and a positive number if the first object is greater. For example: • 1.compare To(2) returns -1 • 1.compareTo(1) returns 0 1.compare To(0) returns 1 . If the value provided to the method is null, or it is already present in the set, do nothing and return the original head. Otherwise, insert the value and return the head of the set. public Node<T> add(Node<T> head, T value)

Answer 1

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. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

//required method

public Node<T> add(Node<T> head, T value) {

      // if the value to be added is null, returning current head

      if (value == null) {

            return head;

      }

      // creating a new node

      Node<T> newNode = new Node<T>();

      // setting value as val

      newNode.val = value;

      if (head == null) { //if current head is empty

            return newNode; //returning as new head

      }

      // if value is same as head's value, returning without adding

      if (value.compareTo(head.val) == 0) {

            return head;

      }

      // checking if value is smaller than value at current head

      if (value.compareTo(head.val) < 0) {

            // adding before current head and returning as new head

            newNode.next = head;

            head.prev = newNode;

            return newNode;

      }

      // otherwise taking a reference to head node

      Node<T> temp = head;

      // looping until temp is the last node

      while (temp.next != null) {

            // checking if value and next node's value are same

            if (value.compareTo(temp.next.val) == 0) {

                  // returning head without adding

                  return head;

            }

            // otherwise checking if value is smaller than next node's value

            if (value.compareTo(temp.next.val) < 0) {

                  // adding new node between temp and temp.next and adjusting all

                  // links

                  newNode.next = temp.next;

                  temp.next.prev = newNode;

                  temp.next = newNode;

                  newNode.prev = temp;

                  return head; // returning head

            }

            // otherwise moving to next node

            temp = temp.next;

      }

      // if still not added, adding as last node and returning head

      temp.next = newNode;

      newNode.prev = temp;

      return head;

}