Java - Doubly Linked List adding values

Question

I'm trying to merge two (pre-sorted) doubly linked lists together and it keeps getting infinite loops or a one element list when trying to add.

The expected outcome of the code below should be the list:

[0,1,2,3,4,5,6,7,8,9]

So I Have :

public static void main(String[] args) {
    TheLinkedList<Integer> oddList = new TheLinkedList<Integer>();
    TheLinkedList<Integer> evenList = new TheLinkedList<Integer>();

    // Test lists 
    oddList.add(new Integer(9));
    oddList.add(new Integer(7));
    oddList.add(new Integer(5));
    oddList.add(new Integer(3));
    oddList.add(new Integer(2));
    oddList.add(new Integer(1));

    evenList.add(new Integer(8));
    evenList.add(new Integer(6));
    evenList.add(new Integer(4));
    evenList.add(new Integer(2));
    evenList.add(new Integer(0));

    //System.out.println(oddList.toString());
    //System.out.println(evenList.toString());
    oddList.merge(evenList);
    //System.out.println(theList.toString());
}

Note this is in a different Class and you CANNOT accesss oddList or evenList directly

// Self explanatory getter and setter methods
public void add(T newValue) {
    head = new Node<T>(newValue, head, null);
    if (head.getNext() != null)
        head.getNext().setPrevious(head);
    else
        tail = head;
    count++;
}

public void merge(TheLinkedList<T> two) {
    do {

        if (head.getValue().compareTo(two.head.getValue()) <= 0) {
            head = head.getNext();
            continue;
        }
        if (head.getValue().compareTo(two.head.getValue()) >= 0){
            two.head = two.head.getNext();
        }
    } while (head != null && two.head != null);
}

TTT · Accepted Answer · 2014-03-25 20:23:07Z

1

I don't see any actual merging going on here? Assuming the lists are in descending order you should be comparing the head of one list with the head of the other, and if the value of the other list is less than the value of your main list, you should insert that value to your main list to the next node of your head node and move on to the next value. You will need to be careful because the node you add to your main list will need references to the next and previous items if it is to fit properly.

If the order is not guaranteed then to my knowledge you need to sort the list first, and then merge them to prevent having to walk through the entire referenced linked list multiple times in worst case scenarios.

Edit: here's a code example. You could probably also do it with recursion, but recursion makes my head hurt so...

public void merge(TheLinkedList<T> two) {
Node workingNodeOnOne = this.head;
Node workingNodeOnTwo = two.head;

while (workingNodeOnTwo != null)
        if (workingNodeOnOne.getValue().compareTo(workingNodeOnTwo.getValue()) < 0) {
            //this is if the value of your second working node is greater than the value of your first working node.
            //add the two.head.getValue() value of your current list here before the first working node...
            this.addBefore(workingNodeOnTwo.getValue(), workingNodeOnOne) 
            //note that this does change the value of this.head, but it doesn't matter as we are sorted desc anyways

            //given the constraints of what you have presented, you should never even hit this code block
            workingNodeOnTwo = workingNodeOnTwo.next();
        }
        else { //this is if the head value of second list is less than or equal to current head value, so just insert it after the current value here

            this.add(workingNodeOnTwo.getValue(), workingNodeOnOne); //insert the value of the second working node after our current working node
            workingNodeOnOne = workingNodeOnOne.next();
            workingNodeOnTwo = workingNodeOnTwo.next(); //go on to the next nodes
            }

}

This is definitely gonna need some tweaking depending on your implementation but the logic is sound, I believe.

edited Mar 25, 2014 at 20:23

answered Mar 25, 2014 at 19:13

TTT

2,0301 gold badge20 silver badges35 bronze badges

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

6 Comments

user3362954 Over a year ago

That's the issue I'm having - I've tried using the provided 'add' method to add the value at that spot to the original and it provided an infinite loop. The current code up there is just the proper way it's walking between the two lists - say if the lists were [1,3,4] and [0,2,4,7] it would traverse through them in ascending order. And these lists are in ascending order. The values are added at the beginning of the list ;)

TTT Over a year ago

I think your life would be a lot easier if you overloaded your add method to take a "previous node" value so that you can insert a value after a node and properly link the references. You should not be reassigning the value of head, that is probably what is causing your code to behave unexpectedly

user3362954 Over a year ago

regarding your edited code, what are the properties of the "addBefore" method so I can understand what you're trying to do? Or is that what you mean by the "previous node"?

TTT Over a year ago

I think you would see benefit from looking at the javadoc for java.util.LinkedList. I used standard methods on that api. The addBefore method adds a value before the reference to the node that you pass to the addBefore() function.

user3362954 Over a year ago

I'm looking to do this without the use of the java.util.LinkedList ... trying to get it as raw as possible, to understand what's happening. But thanks!

|

Collectives™ on Stack Overflow

Java - Doubly Linked List adding values

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related