1 answer

Data Structures - Singly Linked Lists You will add a method swapNodes to SinglyLinkedList class (below). This method should swap

Question:

Data Structures - Singly Linked Lists

You will add a method swapNodes to SinglyLinkedList class (below). This method should swap two nodes node1 and node2 (and not just their contents) given references only to node1 and node2. The new method should check if node1 and node2 are the same node, etc. Write the main method to test the swapNodes method. You may need to traverse the list.

package linkedlists;
public class SinglyLinkedList<E> implements Cloneable {
   // ---------------- nested Node class ----------------
   /**
   * Node of a singly linked list, which stores a reference to its element and to
   * the subsequent node in the list (or null if this is the last node).
   */
   private static class Node<E> {

       /** The element stored at this node */
       private E element; // reference to the element stored at this node

       /** A reference to the subsequent node in the list */
       private Node<E> next; // reference to the subsequent node in the list

       /**
       * Creates a node with the given element and next node.
       *
       * @param e the element to be stored
       * @param n reference to a node that should follow the new node
       */
       public Node(E e, Node<E> n) {
           element = e;
           next = n;
       }

       // Accessor methods
       /**
       * Returns the element stored at the node.
       *
       * @return the element stored at the node
       */
       public E getElement() {
           return element;
       }

       /**
       * Returns the node that follows this one (or null if no such node).
       *
       * @return the following node
       */
       public Node<E> getNext() {
           return next;
       }

       // Modifier methods
       /**
       * Sets the node's next reference to point to Node n.
       *
       * @param n the node that should follow this one
       */
       public void setNext(Node<E> n) {
           next = n;
       }

   } // ----------- end of nested Node class -----------

   // instance variables of the SinglyLinkedList
   /** The head node of the list */
   private Node<E> head = null; // head node of the list (or null if empty)

   /** The last node of the list */
   private Node<E> tail = null; // last node of the list (or null if empty)

   /** Number of nodes in the list */
   private int size = 0; // number of nodes in the list

   /** Constructs an initially empty list. */
   public SinglyLinkedList() {
   } // constructs an initially empty list

   // access methods
   public int size() {
       return size;
   }
   public boolean isEmpty() {
       return size == 0;
   }
   public E first() { // returns (but does not remove) the first element
       if (isEmpty())
           return null;
       return head.getElement();
   }
   public E last() { // returns (but does not remove) the last element
       if (isEmpty())
           return null;
       return tail.getElement();
   }

   // update methods
   public void addFirst(E e) { // adds element e to the front of the list
       head = new Node<>(e, head); // create and link a new node
       if (size == 0)
           tail = head; // special case: new node becomes tail also
       size++;
   }

   public void addLast(E e) { // adds element e to the end of the list
       Node<E> newest = new Node<>(e, null); // node will eventually be the tail
       if (isEmpty())
           head = newest; // special case: previously empty list
       else
           tail.setNext(newest); // new node after existing tail
       tail = newest; // new node becomes the tail
       size++;
   }
   public E removeFirst() { // removes and returns the first element
       if (isEmpty())
           return null; // nothing to remove
       E answer = head.getElement();
       head = head.getNext(); // will become null if list had only one node
       size--;
       if (size == 0)
           tail = null; // special case as list is now empty
       return answer;
   }

   @SuppressWarnings({ "unchecked" })
   public boolean equals(Object o) {
       if (o == null)
           return false;
       if (getClass() != o.getClass())
           return false;
       SinglyLinkedList other = (SinglyLinkedList) o; // use nonparameterized type
       if (size != other.size)
           return false;
       Node walkA = head; // traverse the primary list
       Node walkB = other.head; // traverse the secondary list
       while (walkA != null) {
           if (!walkA.getElement().equals(walkB.getElement()))
               return false; // mismatch
           walkA = walkA.getNext();
           walkB = walkB.getNext();
       }
       return true; // if we reach this, everything matched successfully
   }

   @SuppressWarnings({ "unchecked" })
   public SinglyLinkedList<E> clone() throws CloneNotSupportedException {
       // always use inherited Object.clone() to create the initial copy
       SinglyLinkedList<E> other = (SinglyLinkedList<E>) super.clone(); // safe cast
       System.out.println(other.head.getElement());

       if (size > 0) { // we need independent chain of nodes
           other.head = new Node<>(head.getElement(), null);
           Node<E> walk = head.getNext(); // walk through remainder of original list
           Node<E> otherTail = other.head; // remember most recently created node
           while (walk != null) { // make a new node storing same element
               Node<E> newest = new Node<>(walk.getElement(), null);
               otherTail.setNext(newest); // link previous node to this one
               otherTail = newest;
               walk = walk.getNext();
           }
       }

       return other;
   }

   public int hashCode() {
       int h = 0;
       for (Node walk = head; walk != null; walk = walk.getNext()) {
           h ^= walk.getElement().hashCode(); // bitwise exclusive-or with element's code
           h = (h << 5) | (h >>> 27); // 5-bit cyclic shift of composite code
       }
       return h;
   }
   public String toString() {
       StringBuilder sb = new StringBuilder("(");
       Node<E> walk = head;
       while (walk != null) {
           sb.append(walk.getElement());
           if (walk != tail)
               sb.append(", ");
           walk = walk.getNext();
       }
       sb.append(")");
       return sb.toString();
   }

      public void reverse() {
       Node<E> reversedPart = null;
       Node<E> curr = head;
       tail = curr;
       while (curr != null) {
           Node<E> next = curr.next;
           curr.next = reversedPart;
           reversedPart = curr;
           curr = next;

       }
       head = reversedPart;
   }
  // main method
   public static void main(String[] args) {

       SinglyLinkedList<String> list = new SinglyLinkedList<String>();
       list.addFirst("MSP");
       list.addLast("ATL");
       list.addLast("BOS");
       //
       list.addFirst("LAX");

       System.out.println("Original List: "+list);

       //
       list.reverse();
       System.out.println("Reversed List: "+list);
      

       System.out.println("Swaped List: "+list);

   }
}


Answers

// ---------------- nested Node class ----------------
   /**
   * Node of a singly linked list, which stores a reference to its element and to
   * the subsequent node in the list (or null if this is the last node).
   */
   private static class Node<E> {

       /** The element stored at this node */
       private E element; // reference to the element stored at this node

       /** A reference to the subsequent node in the list */
       private Node<E> next; // reference to the subsequent node in the list

       /**
       * Creates a node with the given element and next node.
       *
       * @param e the element to be stored
       * @param n reference to a node that should follow the new node
       */
       public Node(E e, Node<E> n) {
           element = e;
           next = n;
       }

       // Accessor methods
       /**
       * Returns the element stored at the node.
       *
       * @return the element stored at the node
       */
       public E getElement() {
           return element;
       }

       /**
       * Returns the node that follows this one (or null if no such node).
       *
       * @return the following node
       */
       public Node<E> getNext() {
           return next;
       }

       // Modifier methods
       /**
       * Sets the node's next reference to point to Node n.
       *
       * @param n the node that should follow this one
       */
       public void setNext(Node<E> n) {
           next = n;
       }

   } // ----------- end of nested Node class -----------

   // instance variables of the SinglyLinkedList
   /** The head node of the list */
   private Node<E> head = null; // head node of the list (or null if empty)

   /** The last node of the list */
   private Node<E> tail = null; // last node of the list (or null if empty)

   /** Number of nodes in the list */
   private int size = 0; // number of nodes in the list

   /** Constructs an initially empty list. */
   public SinglyLinkedList() {
   } // constructs an initially empty list

   // access methods
   public int size() {
       return size;
   }
   public boolean isEmpty() {
       return size == 0;
   }
   public E first() { // returns (but does not remove) the first element
       if (isEmpty())
           return null;
       return head.getElement();
   }
   public E last() { // returns (but does not remove) the last element
       if (isEmpty())
           return null;
       return tail.getElement();
   }

   // update methods
   public void addFirst(E e) { // adds element e to the front of the list
       head = new Node<>(e, head); // create and link a new node
       if (size == 0)
           tail = head; // special case: new node becomes tail also
       size++;
   }


   public void addLast(E e) { // adds element e to the end of the list
       Node<E> newest = new Node<>(e, null); // node will eventually be the tail
       if (isEmpty())
           head = newest; // special case: previously empty list
       else
           tail.setNext(newest); // new node after existing tail
       tail = newest; // new node becomes the tail
       size++;
   }
   public E removeFirst() { // removes and returns the first element
       if (isEmpty())
           return null; // nothing to remove
       E answer = head.getElement();
       head = head.getNext(); // will become null if list had only one node
       size--;
       if (size == 0)
           tail = null; // special case as list is now empty
       return answer;
   }

   @SuppressWarnings({ "unchecked" })
   public boolean equals(Object o) {
       if (o == null)
           return false;
       if (getClass() != o.getClass())
           return false;
       SinglyLinkedList other = (SinglyLinkedList) o; // use nonparameterized type
       if (size != other.size)
           return false;
       Node walkA = head; // traverse the primary list
       Node walkB = other.head; // traverse the secondary list
       while (walkA != null) {
           if (!walkA.getElement().equals(walkB.getElement()))
               return false; // mismatch
           walkA = walkA.getNext();
           walkB = walkB.getNext();
       }
       return true; // if we reach this, everything matched successfully
   }

   @SuppressWarnings({ "unchecked" })
   public SinglyLinkedList<E> clone() throws CloneNotSupportedException {
       // always use inherited Object.clone() to create the initial copy
       SinglyLinkedList<E> other = (SinglyLinkedList<E>) super.clone(); // safe cast
       System.out.println(other.head.getElement());

       if (size > 0) { // we need independent chain of nodes
           other.head = new Node<>(head.getElement(), null);
           Node<E> walk = head.getNext(); // walk through remainder of original list
           Node<E> otherTail = other.head; // remember most recently created node
           while (walk != null) { // make a new node storing same element
               Node<E> newest = new Node<>(walk.getElement(), null);
               otherTail.setNext(newest); // link previous node to this one
               otherTail = newest;
               walk = walk.getNext();
           }
       }

       return other;
   }

   public int hashCode() {
       int h = 0;
       for (Node walk = head; walk != null; walk = walk.getNext()) {
           h ^= walk.getElement().hashCode(); // bitwise exclusive-or with element's code
           h = (h << 5) | (h >>> 27); // 5-bit cyclic shift of composite code
       }
       return h;
   }
   public String toString() {
       StringBuilder sb = new StringBuilder("(");
       Node<E> walk = head;
       while (walk != null) {
           sb.append(walk.getElement());
           if (walk != tail)
               sb.append(", ");
           walk = walk.getNext();
       }
       sb.append(")");
       return sb.toString();
   }

      public void reverse() {
       Node<E> reversedPart = null;
       Node<E> curr = head;
       tail = curr;
       while (curr != null) {
           Node<E> next = curr.next;
           curr.next = reversedPart;
           reversedPart = curr;
           curr = next;

       }
       head = reversedPart;
   }
  // main method
   public static void main(String[] args) {

       SinglyLinkedList<String> list = new SinglyLinkedList<String>();
       list.addFirst("MSP");
       list.addLast("ATL");
       list.addLast("BOS");
       //
       list.addFirst("LAX");

       System.out.println("Original List: "+list);

       //
       list.reverse();
       System.out.println("Reversed List: "+list);
      


       System.out.println("Swaped List: "+list);

   }
}

.

Similar Solved Questions

1 answer
Frederick Company's January 1, 2018 finished goods inventory was $43,000. The January 1, 2019 finished goods...
Frederick Company's January 1, 2018 finished goods inventory was $43,000. The January 1, 2019 finished goods inventory is $54,000. Cost of goods manufactured for the FY 2018 was $306,000. Use this information to determine the dollar amount of the FY 2018 cost of goods sold. (Round dollar values ...
1 answer
Cost of goods sold is: Multiple Choice An expense account. A permanent equity account An asset...
Cost of goods sold is: Multiple Choice An expense account. A permanent equity account An asset account A revenue account...
1 answer
A) 5.1 B) 5.4 C) 5.7 09: A conducting solid sphere of radius R=12cm creates an...
A) 5.1 B) 5.4 C) 5.7 09: A conducting solid sphere of radius R=12cm creates an electric field of 220KN/C at a distance r = 24cm from its center, the surface charge density (in uC/m) of the sphere is A) 7.788 B) 9.313 C) 11.092 D) 14.656...
1 answer
Give two examples of Le Chatelier's principle in this experiment when a shift in equilibrium occurs....
Give two examples of Le Chatelier's principle in this experiment when a shift in equilibrium occurs. Explain the two scenarios where this principle is utilized the most. (this lab is on Aluminum Nickel Group ions)....
1 answer
A select list of transactions for Anuradha's Goals follows (Click the icon to view the transactions)...
A select list of transactions for Anuradha's Goals follows (Click the icon to view the transactions) For each transaction, identify what type of adjusting entry would be needed. Select from the following four types of adjusting entries deferred expense, deferred revenue accrued expense, and accr...
1 answer
Say that the interest rate is 12% and you invest $400 today, and then another $400...
Say that the interest rate is 12% and you invest $400 today, and then another $400 exactly two years from today. What is the total future value of these investments three years from today? $905.45 $995.45 $1,009.97 $1,063.73...
1 answer
Numver 7 please
numver 7 please...
1 answer
1. Discuss the trails and skills CSRs should possess. 2. Discuss ways to communicate effectively with...
1. Discuss the trails and skills CSRs should possess. 2. Discuss ways to communicate effectively with disabled persons....
1 answer
(g(n)), g(n) is (f(n)), or both. 1. For each of the following pairs of functions determine...
(g(n)), g(n) is (f(n)), or both. 1. For each of the following pairs of functions determine if f(n) is f(n) = (na – n)/2, g(n) = 3n · f(n) = n log n, g(n) = n/n/2...
1 answer
N Does ight rime T depend on the initial velocity e, of the balt Whyt Projectile...
n Does ight rime T depend on the initial velocity e, of the balt Whyt Projectile inntions with same tるandaw-yw, but wit Which one in the following cases bss the largest horizontal distance based on the formula -sin 20gwhere g-9.8 m/s 2. ti 30° Tb) θ-45。 Projectile motions wit...
1 answer
Lab 3: Homework Assignment (30 pts.) Using the data from Table 2 below, calculate the statistics...
Lab 3: Homework Assignment (30 pts.) Using the data from Table 2 below, calculate the statistics and fill in the cells of Worksheet 1 below. Use these data to make a table in MS Excel that lists the population name (Lake) and the sample statistics for each population including mean ducklings fledged...
1 answer
(1 point) Find the least-squares regression line y = bo + by a through the points...
(1 point) Find the least-squares regression line y = bo + by a through the points (-3,1), (2,9), (5, 14), (9, 18), (9,24). For what value of x is y=0?...
1 answer
Independent random samples of professional football and basketball players gave the following Information. Assume that the...
Independent random samples of professional football and basketball players gave the following Information. Assume that the weight distributions are Welghts (In Ib) of pro football players: xq; n = 21 244 262 256 251 244 276 240 265 257 252 282 256 250 264 270 275 245 275 253 265 271 Weights (in lb) ...
1 answer
When looking at MAT locus of yeast a type cells briefly describe the state (activated/inactivated) and function for the following: -02 . aS C. Sg . hs When looking at MAT locus of yeast a type c...
When looking at MAT locus of yeast a type cells briefly describe the state (activated/inactivated) and function for the following: -02 . aS C. Sg . hs When looking at MAT locus of yeast a type cells briefly describe the state (activated/inactivated) and function for the following: -02 . aS C. Sg . ...
1 answer
3. (5 pts.) FMC corporation has estimated its profit function as: II =-1/3Q3 + 202 +12Q...
3. (5 pts.) FMC corporation has estimated its profit function as: II =-1/3Q3 + 202 +12Q - 6 a. Determine the output level that maximizes FMC's profit. b. Find the maximum profit that FMC can get. * *...
1 answer
17. Predict the electron configuration of element with the atomic number 123. a. [Og] 7d5 b....
17. Predict the electron configuration of element with the atomic number 123. a. [Og] 7d5 b. (Og) 8s 5g? C. (Og] 852 8p3 d. (Og] 8s 6f e. [Og] 8s 7d3 18. Predict the 4 quantum numbers for the last electron Yttrium. Selection ms 4 a b 5 4 4 2 - 2 +2 -Y2 е 8...
1 answer
Please answer all the questions. I want to learn how to answer this question properly. thank...
please answer all the questions. I want to learn how to answer this question properly. thank you, I will rate asap. Two Step Reaction COOH 1. What reagent(s) would you use in the first step? 2. Draw the proposed intermediate product. 3. What reagent(s) would you use in the second step? 4. Draw th...