Java; Swapping two elements in a DoublyLinkedList without changing the data without collections

Question

Okay, so I'm trying to swap two elements in a doubly linked list without altering the data and without using collections. Here's what I have so far;

package q2b;

public class DoublyLinkedList {
    static Node first;
    static Node last;
    
    public DoublyLinkedList() {
        first = null;
        last = null;
    }
    
    public void display() {
        Node current = first;

        if(first == null) {
            System.out.println("List is empty.");
        }
        System.out.print("Nodes: ");
        while(current != null) {
            System.out.print(current.data+", ");
            current = current.next;
        }
        System.out.println();
    }
    
    public void add(int x) {
        if (last==null) {
            Node temp = new Node(x);
            last = temp;
            first = temp;
        }
        
        else {
            Node temp = new Node(x);
            last.next = temp;
            temp.prev = last;
            last = temp;
        }
    }
    
    public Pair find(int x, int y) {
        Node n1 = null;
        Node n2 = null;
        Node temp = first;
        
        while (temp != null) {
            if (temp.data == x) {
                n1 = temp;
            }
            else if (temp.data == y) {
                n2 = temp;
            }
            temp = temp.next;
        }
        return new Pair(n1,n2);
    }
    
    public void swap(int x, int y) {
        if (first == null || first.next == null || x == y) {
            return;
        }
        
        Pair p = find(x,y);
        
        Node n1 = p.first;
        Node n2 = p.second;
        
        if (n1==first) {
            first = n2;
        }
        else if (n2 == first) {
            first = n1;
        }
        
        if (n1 == last) {
            last = n2;
        }
        else if (n2 == last) {
            last = n1;
        }
        
        Node temp;
        temp = n1.next;
        n1.next = n2.next;
        n2.next = temp;
        
        if (n1.next != null) {
            n1.next.prev = n1;
        }
        if (n2.next != null) {
            n2.prev.next = n2;
        }
        
        temp = n1.prev;
        n1.prev = n2.prev;
        n2.prev = temp;
        
        if (n1.prev != null) {
            n1.prev.next = n1;
        }
        if (n2.prev != null) {
            n2.prev.next = n2;
        }
    }
}

And my main;

public class Main {
    public static void main(String[] args) {
        DoublyLinkedList list = new DoublyLinkedList();
        list.add(2);
        list.add(4);
        list.add(6);
        list.add(8);
        list.add(10);
        list.display();
        list.swap(6, 8);
        list.display();
    }
}

Now when I go to run the code, it just infinitely runs until it crashes. I assume I'm missing something in the swap function that is sending it into a death spiral, but I'm not sure what it is. Can anyone give me some insight?

And if your code is crashing, it is not running infinitely. Edit your question to include the error message and stack trace. — tgdavies
– tgdavies, Commented Apr 18, 2023 at 4:13
I can't get to the debugger because when I start it, my IDE locks up and I have to ctrl-alt-delete to exit the program. There is no crash and error message. — Dash Harber
– Dash Harber, Commented Apr 18, 2023 at 14:22
Which IDE are you using? Anyway, put a breakpoint near the start, and step after execution hits it. — tgdavies
– tgdavies, Commented Apr 18, 2023 at 22:34

eiljoe · Accepted Answer · 2023-04-18 07:05:35Z

1

Your problem is in:

if (n2.next != null) {
   n2.prev.next = n2;
}

This is because n1 and n2 are originally consecutive nodes, which means that the prev of n2 is n1. So after you swapped the nexts of n1 and n2 the expression n2.prev.next = n2 is equal to n1.next = n2, which overrides the n1.next = n2.next you did a few lines before and points n1's next back to n2 while n2's next is n1, so now you have a circle where n1.next points to n2 and n2.next points to n1 - that creates an endless loop when you try to traverse the nodes in display() and that's why your code never returns. One possible solution is to change the if to:

if (n2.next != null && n2.prev != n1) {
   n2.prev.next = n2;
}

I think you'll have to apply a similar treatment to the other three ifs

answered Apr 18, 2023 at 7:05

eiljoe

413 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dash Harber Over a year ago

So I should always check to make sure the previous node does not equal the opposite? What about in the last two branches where I'm already dealing with the previous node?

eiljoe Over a year ago

As I said you'll probably need to augment the condition of all 4 ifs. These two: if (n1.next != null) { n1.next.prev = n1; } if (n2.next != null) { n2.prev.next = n2; } and these two: if (n1.prev != null) { n1.prev.next = n1; } if (n2.prev != null) { n2.prev.next = n2; }

Collectives™ on Stack Overflow

Java; Swapping two elements in a DoublyLinkedList without changing the data without collections

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related