1. Engineering
  2. Computer Science
  3. question swapping nodes in a singularly linked list how do...

Question: question swapping nodes in a singularly linked list how do...

Question details

Question: SWAPPING NODES IN A SINGULARLY LINKED LIST: How do I account for conditions such as Nodes at the beginning or end of the list?

Code: (SWAPPING METHOD AND TEST LINE BOLDED)

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
/**
* Returns the number of elements in the linked list.
* @return number of elements in the linked list
*/
public int size() { return size; }

/**
* Tests whether the linked list is empty.
* @return true if the linked list is empty, false otherwise
*/
public boolean isEmpty() { return size == 0; }

/**
* Returns (but does not remove) the first element of the list
* @return element at the front of the list (or null if empty)
*/
public E first() { // returns (but does not remove) the first element
if (isEmpty()) return null;
return head.getElement();
}

/**
* Returns (but does not remove) the last element of the list.
* @return element at the end of the list (or null if empty)
*/
public E last() { // returns (but does not remove) the last element
if (isEmpty()) return null;
return tail.getElement();
}

// update methods
/**swapNodes
* @param positionOfNode1
* @param positionOfNode2
*/

public void swapNodes(int positionOfNode1, int positionOfNode2){
  
  
   if (positionOfNode1 >= size() || positionOfNode2 >= size()) {
   throw new IndexOutOfBoundsException();
   }
   if(positionOfNode1==positionOfNode2)return;//Don't do anything if they're the same
  

  
  
// Note - Edge conditions such as the first and last elements not taken care of.
Node<E> previousOfNode1 = null;
Node<E> previousOfNode2 = null;


  
/* 1. Find the previous node of nodes to be swapped. */
Node<E> currentNode = head;
  

int position = 1;
while( currentNode!= null && currentNode.getNext()!= null )
{
     
// -1 used to find the previous node
if(position == positionOfNode1 - 1){
previousOfNode1 = currentNode;
}
else if(position == positionOfNode2 - 1){
previousOfNode2 = currentNode;
}
  
if(null != previousOfNode1 && null != previousOfNode2){
break;
}
currentNode = currentNode.getNext();
position++;
}
  
/* 2.Do swapping */
// Preparing temp variable - Actual nodes to be swapped.
Node<E> node1 = previousOfNode1.getNext();
Node<E> node2 = previousOfNode2.getNext();
// Preparing temp variable - Node 1 & Node 2 links in the list.
Node<E> node1Next = node1.getNext();
Node<E> node2Next = node2.getNext();
  
// Initiate swaps - Making assignments.
previousOfNode1.setNext(node2);
previousOfNode2.setNext(node1);
// Closing swap - Establishing links with the rest of the link.
node2.setNext(node1Next);
node1.setNext(node2Next);
}


  
  
  
  
/**
* Adds an element to the front of the list.
* @param e the new element to add
*/
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++;
}

/**
* Adds an element to the end of the list.
* @param e the new element to add
*/
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++;
}

/**
* Removes and returns the first element of the list.
* @return the removed element (or null if empty)
*/
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<E> 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
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<E> 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;
}

/**
* Produces a string representation of the contents of the list.
* This exists for debugging purposes only.
*/
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();
}
  
  
  
//main method
public static void main(String[] args)
{
  
   SinglyLinkedList<String> list = new SinglyLinkedList<String>();
   list.addFirst("MSP");
   list.addLast("ATL");
   list.addLast("BOS");
   list.addLast("BOT");

   //
   list.addFirst("LAX");
   System.out.println(list);
   //swap nodes & print them
   list.swapNodes(2,4);
   System.out.println(list);

  
}
  
}

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution