# 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.

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. */
} // 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;
}
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
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())
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
size--;
if (size == 0)
tail = null; // special case as list is now empty
}

@SuppressWarnings({ "unchecked" })
public boolean equals(Object o) {
if (o == null)
return false;
if (getClass() != o.getClass())
return false;
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

if (size > 0) { // we need independent chain of nodes
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);
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("(");
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;
tail = curr;
while (curr != null) {
Node<E> next = curr.next;
curr.next = reversedPart;
reversedPart = curr;
curr = next;

}
}
// main method
public static void main(String[] args) {

//

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

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

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

}
}

#### Similar Solved Questions

##### 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...
##### 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...
##### 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)....
##### 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...
##### 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. 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....
##### (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...
##### 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...
##### 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 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?...
##### 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) ...