Question about iteration speed linked list

Hi!

Could you please explain in more detail why "LinkedList has faster iteration speed than other List classes, because it has double links between its elements"?

Thank you!

In brief, each element in a LinkeList is connected with two references to the element before it and element after if. In an old-school way, think of it as below:

class Node {  
    Node before;
    Node after;
}

This gives you a much faster speed when you iterate back and forth through an Iterator, which makes its iterator operations, including removal of an object, much faster! The only thing the JVM has to do to iterate back and forth is just use the two references found in each node, which takes only O(1) of operation cost.

Got it!

Thank you!