Java: When I insert into my circular doubly-linked list with a header dummy node, my dummy node is shuffled around. Why?

Question

I have written a circular doubly-linked list with a dummy node at the front. During the initialization of my DLL class, I create the dummy node. When I use the debugger in jGrasp and use the visualization tool, after inserting several numbers, my dummy node gets shuffled around and does not stay at the front. I don't understand how I am modifying my linked list. As a preface, my node class has has an integer val and two pointers named prev and next. One thing I notice is that after the assignment statement curr = dummy, dummy node is shuffled to the curr from the previous insertion.

public class DLL {

    Node curr;
    Node help;
    Node dummy = new Node(null, null, -1);

    public DLL() {
        this.curr = curr;
        this.help = help;
        dummy.next = dummy;
        dummy.prev = dummy;
    }

    public boolean isEmpty() {
        if (dummy.next == dummy && dummy.prev == dummy) {
            return true;
        }
        return false;
    }

    public void push(int elem) {
        if (isEmpty()) {
            Node sec = new Node(dummy, dummy, elem);
            dummy.next = sec;
            dummy.prev = sec;
        } else {
            curr = dummy;
            while (curr.next != dummy) {
                curr = curr.next;
            }
            Node n = new Node(curr, dummy, elem);
            curr.next = n;
            dummy.prev = n;
        }
    }

    public void reverse() {
        curr = dummy;
        help = dummy;
        while (curr.next != help || curr != help) {
            curr = curr.next; // increment curr
            help = help.prev; // decrement help    
            swap(curr, help); // swap
        }
    }
    public void swap(Node curr, Node help) {
        int temp = curr.val;
        curr.val = help.val;
        help.val = temp;
    }
    public boolean contains(int elem) {
        curr = dummy.next;
        while (curr != dummy && elem != curr.val) {
            curr = curr.next;
            if (curr == dummy) {
                return false;
            }
        }

        return true;
    }
}

Here is the small test class I used:

public class testDLL {
    public static void main(String[] args) {
        DLL dlink = new DLL();
        dlink.push(4);
        dlink.push(6);
        dlink.push(3);
        dlink.push(2);
        assert dlink.contains(4) == true;
        assert dlink.contains(6) == true;
        assert dlink.contains(3) == true;
        assert dlink.contains(2) == true;
        dlink.reverse();

    }
}

This would be a great time for you to learn how to use a debugger. Add a breakpoint, and step through your code to see what is happening. Without telling us where the problem might be, it could be hard for anyone to give you an answer. — Tim Biegeleisen
– Tim Biegeleisen, Commented Dec 3, 2018 at 6:07

sprinter · Accepted Answer · 2018-12-03 06:26:30Z

1

Welcome to SO. Rather than finding the problem for you, I'll suggest how you might tackle it yourself.

Your test is trying to test too much in one go. For your test to work all of the methods need to work. Better is to test each method in isolation (as far as possible) and then build to testing more complicated scenarios.

So try to get this test working first:

DLL list = new DLL();
assertTrue(list.isEmpty());

Then

DLL list = new DLL();
list.push(5);
assertTrue(list.contains(5));

Pretty soon you'll find you need a method to get the list in a different format for test purposes. This is pretty typical.

DLL list = new DLL();
list.push(5);
list.push(7);
list.push(5);
assertEquals(list.asList(), List.of(5, 7, 5));

DLL list = new DLL();
list.push(5);
list.push(7);
list.reverse();
assertEquals(list.asList(), List.of(7, 5));

And so on.

That way you can check each method works with basic values before moving on.

Now a couple of design pointers: your use of a dummy node to store the head and tail is unusual. It would be easy to mess values up (as you've done). Better is to store the head and tail as separate variables that are null (or, better, Optional.empty) if the list is empty and point to the same node for a single item.

answered Dec 3, 2018 at 6:26

sprinter

28.1k8 gold badges51 silver badges81 bronze badges

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

1 Comment

Xenon Over a year ago

I will be sure to do the above. However, I only have a header dummy node. That is, I am not storing a header and trailer, only a header. @sprinter

Xenon · Accepted Answer · 2018-12-03 06:46:41Z

0

I have resolved this issue I believe. Instead of setting curr = dummy, I set curr = head. Immediately after initializing dummy at the top of DLL, I set head = dummy. This way I do not alter head as I go along.

answered Dec 3, 2018 at 6:46

Xenon

3115 silver badges13 bronze badges

Collectives™ on Stack Overflow

Java: When I insert into my circular doubly-linked list with a header dummy node, my dummy node is shuffled around. Why?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related