What qualifies as a (slow) access to an internal element of a LinkedList

A post on LinkedList says:

LinkedList allows for constant-time insertions or removals, but o开发者_运维问答nly sequential access of elements. In other words, you can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list.

I'm not understanding what will qualify for grabbing the element in the middle?

In below piece of code, assuming arrL is a LinkedList that holds 50 elemnets, when counter j reaches 20, and program executes arrL.get(20).. Does that mean program is grabbing the element in middle? Also in below program I'm just walking the list forward, isn't?

    for(int j=0;j<arrL.size();++j){
        arrL.get(j);
    }

Yes, in each iteration you are traversing the list from the beginning to the j-th element, so the overall loop performance is n^2 (very poor). That's because in each iteration you have independent get() call which has linear performance.

If you use iterator on the other hand, you will be traversing the list one element at a time, going forward by one element in each iteration, which is much faster:

for(Iterator<E> iter = arrL.iterator(); iter.hasNext();) {
  E e = iter.next();
}

or better:

for(E k: arrL) {
}

BTW this is a very basic data-structure question, Java has nothing to do here...

For LinkedList, get(N) takes time proportional to N. So - get(19) takes about 20 times as long as get(0). Your for loop above operates in O(n^2) time - n passes, with O(n) time for each pass. If you want to access the members in order, use an iterator:

Iterator it = arrL.iterator();
while(it.hasNext()) {
   it.next();
}

or implicity, like so:

for(Obj o : arrL) {
  // do something with o
}

In a linked list, each list entry only knows its predecessor and its successor: They simply link to one another. The good thing about this is, that it is easy to make this list to grow by just adding and linking to new elements. But reaching an element that is not an endpoint in the list requires a walk from either end to the specific element. Therefore, each call to get(j) requires j element visits from an endpoint in the chain/list. get(j) is, in other words, quite expensive in terms of time. As an example, if the list has 1000 elements, getting to element number 500 requires 500 visits from either end. If the list were 2000 elements long, getting to the middle element (element 1000) would similarly require 1000 visits because we follow the node links (the chain).

In contrast, accessing any element in an array takes constant time.

@Vicky, what it means is that every time you call arraL.get(j) this operation takes linear time to perform. That means that when you're getting the 20th element, it will start at the beginning (or end, I'm not sure about the implementation) and transverse the entire list to the 20th element. The other implementation ArrayList will do that in constant time (internally it keeps an array, so you can think about arrL.get(20)as array[20]), but every time you delete an item in the middle, it will have to shift the elements in the array. So basically, ArrayList is a better choice, performance wise,for random reads, and LinkedList is a better choice when you will be performing a lot of deletes.