Traversing a Doubly Linked List backwards

Question

I am trying to move backwards to an index in a Doubly Linked List if the desired index is in the latter half of the list. What I have now compiles but does not work properly. Can anyone diagnose the issue here? I am guessing it is somewhere in the loop logic.

    private Node<E> goToNode(int index) {
    Node<E> temp;
    double whichHalf = size / 2;
    
    if(index > whichHalf) {
        temp = tail.prev;
        for(int i = size; i > index; i--)
            temp = temp.prev;
        return temp;
        }
        
    else {
        temp = head.next;
        for(int i = 0; i < index; i++)
            temp = temp.next;
        return temp;
        }
}

Thanks!

You do know that the index of the first element, i.e. `head.next`, is `0`, and that the index of the last element, i.e. `tail.prev`, is `size - 1`, right? *Hint, hint: Minus one!* — Andreas, Sep 11 '20 at 18:06
*"I am **guessing** it is somewhere in the loop logic"*. Stop guessing: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) — Andreas, Sep 11 '20 at 18:08
[I downvoted because "it's not working" is not a helpful problem statement.](http://idownvotedbecau.se/itsnotworking/) — EJoshuaS - Stand with Ukraine, Sep 11 '20 at 18:12

EJoshuaS - Stand with Ukraine · Answer 1 · 2020-09-11T18:23:36.740

You're not starting at the beginning or end of the list - you start on either the second item or the second-to-last item (depending on which direction you're iterating). That means that you'll always pass the index.

Also, what if the index that they're looking for is either the head or tail? There's no way to return that.

Suppose that you have the list A B C D E F G. Let's break this down:

0    1         2    3      4   5          6
A    B         C    D      E   F          G
HEAD HEAD.NEXT      CENTER     TAIL.PREV  TAIL

Suppose that you have an index of 4. That means that you iterate from i = 7 to i > 4 (i.e. i = 5) - 3 times total. That means that you complete the following steps:

5 (start)
4 (iteration 1)
3 (iteration 2)
2 (iteration 2)

which is wrong.

Traversing a Doubly Linked List backwards

1 Answers1