How to fix error in doubleLinkedList java code where when adjacent nodes are inputted to switch the second node is twice, removing the first node

Question

I am making a project right now to practice double linked lists and I have been working on a method in my double linked lists class which switches node locations. It works fine when trying to switch non adjacent nodes but when trying to switch adjacent nodes the error occurs for example.

If the starting list is:

1. Carrot
2. Candy
3. Watermelon
4. Bread

The output will be

1. Carrot
2. Watermelon
3. Watermelon
4. Bread

Im trying to figure out the error but my knowledge is lacking there, Any help would be great I appreciate it!

I tried creating a temp node to hold the original prev and next for the nodes, but that didnt work. I tried if statements which checked if the prev and next were equal and that didnt work.

Here is my code

public void switchNodes(int firstSpace, int secondSpace){
    
    //If statement which checks isEmpty(), and if firstSpace and secondSpace is less than 0.
    if(isEmpty()|| firstSpace < 0 || secondSpace < 0){
        System.out.println("List is empty or one of spaces is entered does not have anything in it.");//If any of the previous if scenarios is met, prints a message telling the user that.
    }
    else{
    Node<E> firstN = current(firstSpace); //Creates a node firstN by calling the current method and using the imported firstSpace int.
    Node<E> secondN = current(secondSpace); //Creates a node secondN by calling the current method and using the imported secondSpace int.
    
    switchSpace(firstN, secondN);//Calls the switchSpace method with nodes firstN and secondN.

    }  
}

  /**
   *Private method which takes in two nodes and switches their positions on the list.
   * Done by creating two nodes with the information imported from the switchNodes method.
   * The created nodes contain the same element and the swapped prev and next.
   * The nodes around the swapped nodes are then accessed and replaced to the swapped nodes address.
   */
  private void switchSpace(Node<E> firstSwitch, Node<E> secondSwitch){
    
    //Creates switchedFirst node to contain the element of the imported firstSwitch node and the addresses of the secondSwitch node.
    Node<E> switchedFirst = new Node<E>(firstSwitch.getElement(), secondSwitch.getPrev(), secondSwitch.getNext());
    //Creates switchedSecond node to contain the element of the imported secondSwitch node and the addresses of the firstSwitch node.
    Node<E> switchedSecond = new Node<E>(secondSwitch.getElement(), firstSwitch.getPrev(), firstSwitch.getNext());
    
    switchedFirst.getNext().setPrev(switchedFirst);//The node after the switchedFirst nodes new position is accessed and the prev address is set to switchedFirst.
    switchedFirst.getPrev().setNext(switchedFirst);//The node before the switchedFirst nodes new position is accessed and the next address is set to switchedFirst.

    switchedSecond.getNext().setPrev(switchedSecond);//The node after the switchedSecond nodes new position is accessed and the prev address is set to switchedSecond.
    switchedSecond.getPrev().setNext(switchedSecond);//The node before the switchedSecond nodes new position is accessed and the next address is set to switchedSecond.
    
  
}

Answer 1

Your problem comes from the way you are creating the updated nodes. Lets say you have this list (Sorry for the bad drawing):

a <--> b <--> c <--> d

and you want to switch b and c.

Your are creating the updated b(ub) by setting its prev and next to c's prev and next respectively. Similarly, the updated c(uc) is created by setting its prev and next to b's prev and next respectively.

        <----ub---->
       /            \
a <--> b <--> c <--> d
\             /   
 <------uc--->       

Now you are trying to link the old prev and next to the new ones.

        <---ub<---->
       /            \
a <--- b <--> c --> d
\             /   
 <--->uc----->       

Now, if you traverse it, you will get

a, uc, c, d

This problem only occurs if the prev/next points to any node that is to be replaced. To solve this, you need to replace the old nodes with the updated nodes if any next/prev points to it. Here, is the updated code

    private void switchSpace(Node<E> firstSwitch, Node<E> secondSwitch){
        // Creates updatedFirst node to contain the element of the second node
        // Don't set the prev and next yet
        Node<E> updatedFirst = new Node<E>(secondSwitch.getElement(), null, null);
        // Creates updatedSecond node to contain the element of the First node
        // Don't set the prev and next yet
        Node<E> updatedSecond = new Node<E>(firstSwitch.getElement(), null, null);

        // Find the prev and next of the old nodes. If any prev/next point to any old element that is
        // about to be replaced, use the new one in its place
        Node<E> prev1 = firstSwitch.getPrev() == secondSwitch ? updatedSecond : firstSwitch.getPrev();
        Node<E> next1 = firstSwitch.getNext() == secondSwitch ? updatedSecond : firstSwitch.getNext();
        Node<E> prev2 = secondSwitch.getPrev() == firstSwitch ? updatedFirst : secondSwitch.getPrev();
        Node<E> next2 = secondSwitch.getNext() == firstSwitch ? updatedFirst : secondSwitch.getNext();

        // Set the prev and next of the updated nodes
        if (next2 != null) {
            next2.setPrev(updatedSecond);
            updatedSecond.setNext(next2);
        }

        if (prev2 != null) {
            prev2.setNext(updatedSecond);
            updatedSecond.setPrev(prev2);
        }

        if (next1 != null) {
            next1.setPrev(updatedFirst);
            updatedFirst.setNext(next1);
        }

        if (prev1 != null) {
            prev1.setNext(updatedFirst);
            updatedFirst.setPrev(prev1);
        }

        // Check if the head needs to be updated
//        if (head == firstSwitch) {
//            head = updatedFirst;
//        } else if (head == secondSwitch) {
//            head = updatedSecond;
//        }
    }

Also, you will have to update the head of the list if the first node gets replaced. The last four commented out lines do that.

The easiset way to swap two nodes would be to swap just the elements. In that way you don't need to bother with other links.

    private void switchSpace(Node<E> firstSwitch, Node<E> secondSwitch){
        // Swap the elements
        E temp = firstSwitch.getElement();
        firstSwitch.setElement(secondSwitch.getElement());
        secondSwitch.setElement(temp);
    }

Hope this helps.