In what sense can a LinkedList be said to not support random access?

Question

This article states that there's "No random access" in LinkedList. Can anybody explain this to me?

Given

LinkedList<String> l = new LinkedList<>();

Then I can use,

l.get(n);

Given this, why does the article say "No random access"?

Solution 1

Random access here means, that you cannot directly access any element in a linked list similar to an array. In linked list you have to traverse each element (link) starting from the head and then you can access that element.

l.get(n);

This method also works the same way in the background. It traverse from the head and then retrieves the nth element

Solution 2

Random Access means that you can find in constant time the i-th element. More specifically, it doesn´t depend on the size of your list, or if you're accessing the first element, the last, or one in the middle.

With Linked Lists

You have to traverse all the elements from the first one to the i-th one to find the i-th one. Hence, it takes much more time to get the last element than the first one. Hence, this is not random access.

With Arrays

The elements in your array are stored contiguously in memory. Hence, if you know the address A of the first element, and the elements have each a size S, you know directly the address of the i-th element: A + i*S. This operation takes the same time for any element in your array, and is enough to retrieve it. Hence, arrays are random access.

Solution 3

You will start from head and traverse to n and it's not random access!!! And here is the method of traversing from head to N

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;
    }
}

Solution 4

When we say that about a java collection it means it doesn't implements RandomAccess interface

You can read further about it here RandomAccess

Solution 5

The javadoc writes:

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

That is, even though a LinkedList offers a method to access the i-th element, that method will internally walk along the list until it reaches that element, and is therefore inefficient.

That's probably what your tutorial calls "no random access".

An ArrayList, in constrast, is based on arrays, where the i-th element can be accessed directly, or as its javadoc puts it:

The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation.

Generally speaking, java.util.LinkedList are rarely ever used, as an ArrayList requires less memory, can be iterated over more quickly, and supports efficient access by index. That doesn't mean that linked lists (the data structure) are useless, it's just that their main advantage (the ability to keep a reference to a list element, to possibly remove that element or add new elements near it) is not permitted by java.util.LinkedList, as iterators are invalidated by concurrent modification.

To cut a long story short: You can probably forget about LinkedList, and simply use an ArrayList whenever you need a List.

View more solutions

Comments

[JOHND]

then this article says that"Random access possible " in Arraylist. Does it mean it actually directly access n th element without traversing from head.

[dejavu]

Yeah, array works differently. Arrays are index based data structures, linked list are link based. In array you can directly access the nth element in O(1) time whereas in linked list it takes O(n) time