Is Java Iterator a reference to the elements of a linked list?
I need to have a list to store multiple Enemy class items in an application. This will function as a pool of objects for efficiency, since this particular class would otherwise be created and killed frequently.
I am still probably going to use a linked list as it would be very useful to put inactive items at the end of the list. My question is this: in Java, does an Iterator directly access the current element it is accessing while holding a reference to it (for linked lists) or iterate over the next element requires the Iterator to start the loop again from the beginning (i.e. (i.e. doesn't help efficiency like a for loop that will always require backtracking for a linked list)?
From a C point of view, my question will be whether the Iterator contains a pointer to the current element it is accessing, so that it doesn't need to loop from the beginning to access.
I've done some research on this, but I couldn't find an answer to it.
source to share
It is not documented in the Javadoc, but you can check the implementation LinkedList
listIterator
and see that it contains a reference to the current and next list items:
public ListIterator<E> listIterator(int index) {
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Entry<E> lastReturned = header;
private Entry<E> next;
private int nextIndex;
private int expectedModCount = modCount;
....
It only needs to iterate over the LinkedList (from the beginning or from the end) when it is created listIterator
, since you can ask listIterator
to specify a specific index of the list when it is created.
source to share
Yes, the implementation Iterator
used in LinkedList contains links to the following and previous items for efficient iteration.
Java is open source, you can see the code for yourself. Here's the code for an iterator with linked lists
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
...
source to share
This will function as a pool of objects for efficiency, as this particular class would otherwise be created and killed frequently.
I wouldn't use an object pool unless your object was very expensive or was named a lot, like one million times per second, for example. Note. Using a LinkedList will create objects to add to the list so you can't save as much as you think.
I am still probably going to use a linked list as it would be very useful to put inactive items at the end of the list.
A string in LinkedLIst is not good for this, but making your own work might work. Adding to the end of the list is expensive, but adding to the start is relatively cheap. I would do this instead of making the order irrelevant.
My question is this: in Java, an Iterator provides direct access to the current element it is accessing while holding a reference to it (for linked lists).
Yes.
or does repeating the next element require the Iterator to start the loop again from the beginning (i.e. does not help efficiency)?
Also yes.
From a C point of view, my question will be whether the Iterator contains a pointer to the current element it is accessing, so that it doesn't need to loop from the beginning to access.
I wouldn't use Iterator at all. This is more garbage and more overhead. However, if you need to rewind, you can use it with the ListIterator, or you need to create a new Iterator.
source to share
Iterating the next element requires the Iterator to start the loop again from the beginning
You can rest assured that this is not true, because it would be such a self-destructive design decision. The whole point Iterator
allows for an optimal access pattern for sequential access data structures.
I have to add this as well: both from a performance and memory perspective, you will be better served ArrayList
. The extra node elements required LinkedList
cause a lot of overhead, and in addition to that, the pointer-tracking access pattern inherent in linked lists is cache-unfriendly.
source to share