java - iterating a linked list

Question

if I use a for-each loop on a linked list in java, is it guaranteed that I will iterate on the elements in the order in which they appear in the list?

• user85421: since it implements SequencedCollection: "the iterator method provides elements starting from the first element, proceeding through successive elements, until the last element"

Answer 1

I found 5 main ways to iterate over a Linked List in Java (including the Java 8 way):

1. For Loop
2. Enhanced For Loop
3. While Loop
4. Iterator
5. Collections’s stream() util (Java8)

For loop

LinkedList<String> linkedList = new LinkedList<>();
System.out.println("==> For Loop Example.");
for (int i = 0; i < linkedList.size(); i++) {
 System.out.println(linkedList.get(i));
}

Enhanced for loop

for (String temp : linkedList) {
 System.out.println(temp);
}

While loop

int i = 0;
while (i < linkedList.size()) {
 System.out.println(linkedList.get(i));
 i++;
}

Iterator

Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
 System.out.println(iterator.next()); 
}

collection stream() util (Java 8)

linkedList.forEach((temp) -> {
 System.out.println(temp);
});

One thing should be pointed out is that the running time of For Loop or While Loop is O(n square) because get(i) operation takes O(n) time(see this for details). The other 3 ways take linear time and performs better.

• roottraveller: Great. I didn't know about LinkedList.size() . +1.
• Tarun: For iteration just using linkedList.forEach(e -> System.out.println(e)); would also work.
• pooria: Linear time and O(n) are the same, aren't they?
• sjkm: @pooria yes, they are the same.
• Brad Davis: Question about the Iterator solution. Is this creating a new memory structure which copies all the elements of the LinkedList, or does it create a new memory structure that contains references (pointers?) to the value for each element in the LinkedList? Why is this faster than using the get(i) solution? Is it because the get(i) has to traverse the tree, at least partially, linkedList.size() times to get the address for the next element?" (it'd be linkedList.size()*(linkedList.size()+1)/2 times, right?)

Answer 2

Linked list is guaranteed to act in sequential order.

From the documentation

An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.

iterator() Returns an iterator over the elements in this list in proper sequence.

Answer 3

As the definition of Linkedlist says, it is a sequence and you are guaranteed to get the elements in order.

eg:

import java.util.LinkedList;
public class ForEachDemonstrater {
 public static void main(String args[]) {
 LinkedList<Character> pl = new LinkedList<Character>();
 pl.add('j');
 pl.add('a');
 pl.add('v');
 pl.add('a');
 for (char s : pl)
 System.out.print(s+"->");
 }
}

Answer 4

Linked list does guarantee sequential order.

Don't use linkedList.get(i), especially inside a sequential loop since it defeats the purpose of having a linked list and will be inefficient code.

Use ListIterator

 ListIterator<Object> iterator = myLinkedList.listIterator();
 while( iterator.hasNext()) {
 System.out.println(iterator.next());
 }

Answer 5

Each java.util.List implementation is required to preserve the order so either you are using ArrayList, LinkedList, Vector, etc. each of them are ordered collections and each of them preserve the order of insertion (see http://download.oracle.com/javase/1.4.2/docs/api/java/util/List.html)

Answer 6

Adding my inputs for future visitors.

First things first: as per $jls-14.14.2, for-each internally use Iterator.

Now, when you iterate over LinkedList using a for-each or an iterator then the looping is always sequential.

But this is prone to thread safety issues. So, two things can happen:

1. If you use a non-threadsafe List implementation then you will run into ConcurrentModificationException
2. You can use a threadsafe List implementation like CopyOnWriteArrayList. And if you must use a LinkedList only then use Collections.synchronizedList() to convert your non-threadsafe LL into a threadsafe LL, but again you need to watch out for using iterator in a threadsafe manner.

Answer 7

Yes, Linked list is guaranteed to act in sequential order.

I have benchmarked different types of iteration over Java's LinkedList heres the result

Allocated LinkedList of size 500000 in 17ms
Classic For Loop time: 146452ms
Classic While Loop time: 146153ms
Iterator time: 22ms
Enhanced For loop time: 9ms
Stream API time: 17ms
List Foreach time: 14ms

Don't use Classic for or while loop (index based) for Linked List iteration.