Does LinkedList start searching from the end if you want element that is nearly its tail?

Question

I am interested how LinkedList is searching data when I want to get it. For example: We have a LinkedList with 1000 elements in it. And I want to take element by index 950 so I write "list.get (950)". Will java starts to look for that element from the beginning? Or it has a pointer to the last element too? I have written small programm to test it. But it works incorrectly(showing bigest time for the first get, whatever it is.

long time;
time = System.nanoTime();
list.get(1);
time = System.nanoTime() - time;
System.out.println("For element at the beginning " + time);
time = System.nanoTime();
list.get(999);
time = System.nanoTime() - time;
System.out.println("For element at the end " + time);

GBlodgett · Accepted Answer · 2019-03-18T15:47:05.273

4

According to the source code for LinkedList it does have a pointer to the last Node:

 /**
  * Pointer to last node.
  * Invariant: (first == null && last == null) ||
  *            (last.next == null && last.item != null)
  */
transient Node<E> last;

Which is used in with one of the internal methods called with get:

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

edited Mar 18 '19 at 15:47

answered Mar 18 '19 at 15:43

GBlodgett

12,704
4
31
45

Doesn't mean it starts from the tail when doing a `get` (although it does). – Michael Mar 18 '19 at 15:44
Thank you for your explanation! And examples! It helps! – cplusplus Mar 19 '19 at 18:50

score 2 · Answer 2 · answered Mar 18 '19 at 15:44

2

Can you please show the observed timings, I suspect they are so close that you cannot make any conclusions based on them!?
See How do I write a correct micro-benchmark in Java? to write proper benchmarks
You can simply inspect the source code of linkedlist to see how it "searches".
LinkedList does in fact have a first and last reference and yes, it has logic to "search" from the back if your index is reasonable close (if (index >= (size >> 1)))

answered Mar 18 '19 at 15:44

luk2302

55,258
23
97
137

Timings are too different. And the first time is always bigger than second. For example: For element at the beginning 11605 ns For element at the end 3755 ns and when I change the order of calls: For element at the end 11605 For element at the beginning 2048 It makes no sense for me. Can you please explain why so? – cplusplus Mar 19 '19 at 18:53

score 2 · Answer 3 · answered Mar 18 '19 at 15:44

Yes, it starts from the back if the element is over half way along:

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

score 0 · Answer 4 · answered Mar 18 '19 at 16:01

0

In addition to other answers.

Your test is correct. Check LinkedList#node source in other answers. Index 999 is the last one in your list, so node() method returns last element immediately. Index 1 is the second in the list (first is 0), so when you call get(1) there is additional for loop iteration to get element next after the first one.

answered Mar 18 '19 at 16:01

devmind

344
2
10

Yeah. You are right. I have changed it to get(0) but it still gets strange results.Timings are too different. And the first time is always bigger than second. For example: For element at the beginning 11605 ns For element at the end 3755 ns and when I change the order of calls: For element at the end 11605 For element at the beginning 2048 It makes no sense for me. Can you please explain why so? – cplusplus Mar 19 '19 at 18:58
It's definitely some JVM optimization. E.g. there is no need to calculate ```size >> 1``` twice for consecutive get calls if list size is not changed. – devmind Mar 19 '19 at 20:05
Hm maybe I understand it now. Thanks! – cplusplus Mar 20 '19 at 10:57

Does LinkedList start searching from the end if you want element that is nearly its tail?

4 Answers4