CODEWITHSUNDEEP
javanodesdoubly-linked-list
roughosing
roughosing

Reputation: 71

DoublyLinkedList node operation not working as expected, giving wrong node data for .prev function

I'm currently in the process of writing the deleteAt() function for my DLList program, although for trying to delete a node in the middle of the stack the code is acting unpredictably and I have no idea why?

For a previously created list containing the numbers: 2 , 3 , 9 , 8 , 7 , 4

and an operation to delete the data at node position: 2(the number 9)

My code acts oddly and instead of simply removing the data at position 2, it removes the data at position 2 and 1, so the outcome is: 2,8,7,4

When using the diplayNode() function I figured out that the line of code DLLNode p = posFind.prev; instead of giving me the data for node previous to posFind at that particular iteration, it always gives me the data as if posFind == head.next, so therefore it always return the data for 'head'

And I have no idea why this is happening as when i used the displayNode() function in the nested if() statement it returns to me the correct data for posFind at that particular iteration??

Any idea on why this is happening?

Code:

while (i < count) {
    if (i == pos) {
        DLLNode tmp = posFind.next;
        posFind.next = current;
        current.prev = head;  
        current.next = tmp;
        tmp.prev = current;
    }
    posFind = posFind.next;
    i++;
}

Upvotes: 1

Views: 92

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109547

There are a couple of little errors in the code. In principle a solution boils down to the following:

public void deleteAt(int pos) {
    if (0 > pos || pos >= count) {
        return false;
    }
    DLLNode node = nodeAt(pos);
    if (node.prev != null) {
        node.prev.next = node.next;
    } else {
        head = node.next;
    }
    if (node.next != null) {
        node.next.prev = node.prev;
    } else {
        tail = node.prev;
    }
    --count;
    return true;
}

private DLLNode nodeAt(int pos) {
    if (0 > pos || pos >= count) {
        throw new IndexOutOfBoundsException();
    }
    DLLNode node;
    if (pos <= count/2) {
        node = head;
        for (int i = 0; i < pos; ++i) {
            node = node.next;
        }
    } else {
        ...
    }
    return node;
}

Class Invariants:

As you took the effort making unit tests, I would like to mention the usage of pre- and post-conditions. And especially invariants must be held before and after any operation.

assert (head == null && tail == null && count == 0)
    || (head != null && tail != null && count > 0);

assert (node.prev == null && head == node)
    || (node.prev != null && node.prev.next == node);

assert (node.next == null && tail == node)
    || (node.next != null && node.next.prev == node);

Upvotes: 1

flo
flo

Reputation: 10241

Found Waldo!

The mistake is in insertBefore. You've got

while (i < count) {
    if (i == pos) {
        DLLNode tmp = posFind.next;
        posFind.next = current;
        current.prev = head;  <----- here!!!
        current.next = tmp;
        tmp.prev = current;
    }
    posFind = posFind.next;
    i++;
}

But the marked line should be

current.prev = posFind;

Setting the backpointer to head messed up every not-end insert.

Upvotes: 3

Related Questions