Jump to content
  • Advertisement
Sign in to follow this  
JonBonazza

[java] Lists, Vectors, and Iteration

This topic is 2610 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I suppose the question I have is two-fold, so I will number them for clarity:

1) Am I correct in assuming that the LinkedList class is more efficient than the Vector class?

2) When working with a List (whether it be ArrayList, LinkedList, etc...) is it better to use an Iterator object to traverse the list, or to use a loop and accessor methods?

The reason I ask is because I am working on a game that the GameObject class contains a list of Component objects. when the GameObject is updated, it traverses the list, calling the update method of each component. At the moment, I am using a LinkedList and traversing it by means of an Iterator object, but I am scared that bottlenecks can arise due to the nature of Iterators.

Share this post


Link to post
Share on other sites
Advertisement

1) Am I correct in assuming that the LinkedList class is more efficient than the Vector class?

A Vector is essentially just a synchronized ArrayList. Within a single thread you could consider it less efficient.

In theory, a LinkedList is faster to add/remove elements, but slower to iterate over the full list.
An ArrayList is slower to add/remove, but faster to iterate.



2) When working with a List (whether it be ArrayList, LinkedList, etc...) is it better to use an Iterator object to traverse the list, or to use a loop and accessor methods?

To just iterate over a list, either can be used.
Iterators become useful when you want to modify the underlying list whilst iterating.

Share this post


Link to post
Share on other sites
1) Am I correct in assuming that the LinkedList class is more efficient than the Vector class?

No, not at all, they're both efficient but for different kinds of operation. A LinkedList is more efficient as insertion and removal in the middle, for example, but not as efficient memory-wise or for sequential iteration (which is kind of a consequence of its memory layout) and are very inefficient at random-access lookup. A Vector is also synchronized (for multi-threading) by default, whereas a LinkedList isn't.

In general you ought to 'know' when a LinkedList is appropriate and when a Vector is appropriate. If you don't know then a good rule of thumb is to default to using an ArrayList (like a Vector but not synchronized).

2) When working with a List (whether it be ArrayList, LinkedList, etc...) is it better to use an Iterator object to traverse the list, or to use a loop and accessor methods?[/quote]
Neither and both - It depends on what it is you're doing. If you just want to iterate over the contents of a collection then use the special for loop:

for (Component c : myListOfComponents) {
doSomethingTo(c);
}


The reason I ask is because I am working on a game that the GameObject class contains a list of Component objects. when the GameObject is updated, it traverses the list, calling the update method of each component. At the moment, I am using a LinkedList and traversing it by means of an Iterator object, but I am scared that bottlenecks can arise due to the nature of Iterators.[/quote]
If you're mainly traversing you may prefer to use an ArrayList instead, they support rapid traversal more efficiently than a LinkedList.

Share this post


Link to post
Share on other sites

[quote name='jonbonazza' timestamp='1319316797' post='4875434']1) Am I correct in assuming that the LinkedList class is more efficient than the Vector class?

No, not at all, they're both efficient but for different kinds of operation. A LinkedList is more efficient as insertion and removal in the middle, for example, but not as efficient memory-wise or for sequential iteration (which is kind of a consequence of its memory layout) and are very inefficient at random-access lookup. A Vector is also synchronized (for multi-threading) by default, whereas a LinkedList isn't.

In general you ought to 'know' when a LinkedList is appropriate and when a Vector is appropriate. If you don't know then a good rule of thumb is to default to using an ArrayList (like a Vector but not synchronized).

2) When working with a List (whether it be ArrayList, LinkedList, etc...) is it better to use an Iterator object to traverse the list, or to use a loop and accessor methods?[/quote]
Neither and both - It depends on what it is you're doing. If you just want to iterate over the contents of a collection then use the special for loop:

for (Component c : myListOfComponents) {
doSomethingTo(c);
}


The reason I ask is because I am working on a game that the GameObject class contains a list of Component objects. when the GameObject is updated, it traverses the list, calling the update method of each component. At the moment, I am using a LinkedList and traversing it by means of an Iterator object, but I am scared that bottlenecks can arise due to the nature of Iterators.[/quote]
If you're mainly traversing you may prefer to use an ArrayList instead, they support rapid traversal more efficiently than a LinkedList.

[/quote]

I hadn't considered the special for loop. I have more experience in C/C++ than java, so I sometimes forget that that is an option.

Thanks for the input, both of you.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!