Double Linked List with String Java

Question

I wrote the following program:

public class DLinkedList<T extends Comparable<T>> {

    private class DNode<T> {
        private DNode<T> prev, next;
        private T nodeValue;
        public DNode() {
            nodeValue = null;
            next = prev = this;
            }

        public DNode(T val) {
            nodeValue = val;
            next = prev = this;
            }
        }

    private DNode<T> header;

    private int size;

    public DLinkedList() {
        header = new DNode<T>();
        size = 0;
    }

    public Boolean empty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void addOrder(T val) {
        DNode<T> newNode = new DNode<T>(val);
        DNode<T> curr = header.next;
        int count = 0;

        while (curr != header &&
            curr.nodeValue.compareTo(newNode.nodeValue) < 0 ) {

            curr = curr.next;
            newNode.prev = curr;
            newNode.next = curr.next;
            newNode.next.prev = curr;
            count++;
        }

        if (count == 1) {
            newNode.prev = curr;
            newNode.next = curr.prev;
            curr.prev.next.next = newNode;

        } else {
            newNode.prev = curr.prev;
            newNode.next = curr;
            curr.prev.next = newNode;
            count++;
        }
    }

    public String toString() {
        String str = "";
        DNode<T> curr = header.next;
        while (curr != header) {
            str += curr.nodeValue + ", ";
            curr = curr.next;
        }
        if (str.length() > 0) {
            return str.substring(0, str.lastIndexOf(", "));
        } else {
            return str;
        }
    }

    public static void main(String[] args) {
            DLinkedList<String> d = new DLinkedList<String>();
            d.addOrder("t");
            d.addOrder("y");
            d.addOrder("e");
            d.addOrder("b");
            d.addOrder("p");
            System.out.println("List 1: t, y, e, b, p" + "\nList 1 added and sort : " +d);
    }
}

I am confused/lost as to how to fix my issue. I want to create a double linked list of nodes that hold String values and as I add those string values into the list, the list auto-sort it by way of insertion sort.

I start it off with a node call header which has a null value. Then as I add the String "t, y, e, b, p" into the list using the addOrder(T val) method everything seem to work. It will print out in sorted order "b, e, p, t, y".

The problem occur if I decided not to print the "p" at the end and instead do "t, y, e, b, c" all I get print out is "b, c" instead of doing "b, c, e, t, y". If I add an "a" instead of a "p" or "c" at the end of the list, everything seem to be fine printing "a, b, e, t, y". So it seem like it work with everything that is not "c, d, e". Seem like I need to code a method to add a newNode that will go between them which I'm at lost as how to do it now.

Another problem occurs if I decided to add string "t, y, e, v, p". It seems like this just prints "e, p". Which seems like it added "t, y, e, v" but when "p" comes in, it dropped "t, y, v" and left "e, p".

It seems like I can't add anything between "f-t", but anything before or after that is fine. I have a feeling it has something to do with my index "curr" that maybe it's stuck with my node header.

Can you show us some code? Edit:I didn't see the link at the top — Scott
– Scott, Commented Nov 28, 2012 at 17:47
In the method addOrder, inside the while loop, delete all assignments starting with newNode - they will be overwritten anyway. Why at all modify the list when you have not find the place to insert yet? Probably this is a bug. In the method toString() use StringBuilder instead of str+=.... — Alexei Kaigorodov
– Alexei Kaigorodov, Commented Nov 28, 2012 at 18:04

Patricia Shanahan · Accepted Answer · 2012-11-28 18:10:09Z

1

Some of your code seems a bit confused. You have what looks like a loop for skipping through the list until you find the insertion point, but it changes both the new node's pointers and the existing. I would just have curr = curr.next in that loop, and make no changes at all in the new node's pointers or the existing list until after you have found where to insert, and then remember you need to change a total of four pointers: the next and previous in the new node, the next pointer in its predecessor, and the previous pointer in its successor.

            while (curr != header &&
                    curr.nodeValue.compareTo(newNode.nodeValue) < 0 ) {

                    curr = curr.next;
                    newNode.prev = curr;
                    newNode.next = curr.next;
                    newNode.next.prev = curr;
                    count++;
            }

I have a web page on how to debug that you may find helpful.

answered Nov 28, 2012 at 18:10

Patricia Shanahan

26.2k4 gold badges42 silver badges75 bronze badges

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

3 Comments

Vishal Over a year ago

Yeah, Person must understand debug... +1 for debugging tip

JavaStudent Over a year ago

I am very lost and confuse as I have been wrecking this for a day. I want to like you say keep advancing curr until I find the location on where to add the newNode into the list. It just seem like if I entered those code into the while-loop, it was able to add string "e, b" to the list. If I were to remove it, it would only print "p, t, y".

Patricia Shanahan Over a year ago

@JavaStudent Fix problems one at a time. First make sure you can find the correct insertion point, without changing anything. Add System.out.println calls to check that works. Then, and only then, work on inserting the new node as a separate problem. Just throwing in code that appears to fix one test case rarely, if ever, results in a working program.

Ivonne · Accepted Answer · 2012-11-28 18:41:15Z

1

I agree with the code being a bit confusing and that you should remove the assignments from the while loop but the fix seems simple.

in the section after the loop you need to switch your assignments w/o the count check:

newNode.prev = curr.prev;
newNode.next = curr;
curr.prev.next = newNode;
curr.prev = newNode;

in the example of using "t, y, e, v, p" when inserting "p" the current cursor is on the letter "t". At this point, you want "p" to point to "t" and the previous to be "t" previous, in this case "e".

I haven't tested your other scenarios yet but this looks like what you were missing.

edited Nov 28, 2012 at 18:41

answered Nov 28, 2012 at 18:26

Ivonne

336 bronze badges

4 Comments

Patricia Shanahan Over a year ago

Insert in a doubly linked list requires four pointer assignments, to the two pointers in the new node, to the previous pointer in its successor, and to the successor pointer in its predecessor.

Ivonne Over a year ago

you're right, i adjusted it. it shouldn't even need the if count==1 etc check either.

JavaStudent Over a year ago

Wow Thanks alot! I was on that path at first, but for some reason the final curr.prev = newNode didn't run into my head, and I started going down a long path of confusion that lead to more confusion. I just can't believe it was there at the start and it just didn't click in my head. Ahyiyi THANK YOU!

Ivonne Over a year ago

yeah linked lists can be confusing sometimes. something that could help is actually visualizing it by cutting out squares of paper, labeling them with your letters, and simulating what your code is doing each step of the way.

Collectives™ on Stack Overflow

Double Linked List with String Java

2 Answers 2

3 Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related