When to use LinkedList over ArrayList?

jdchoi_20140225_arrayvslinkedlist11

Yeah, I know, this is an ancient question, but is so common  among beginning developers that I think it deserves a blog post.

The short answer is that almost always an ArrayList is what you want. LinkedList is almost always the wrong choice, performance-wise. There are some very specific algorithms where a LinkedList is called for, but those are very, very rare.

There is one common use case in which LinkedList outperforms ArrayList: that of a Queue. But even then, if your goal is performance, instead of LinkedList you may also consider using an array (if you can determine an upper bound on your queue size ahead of time, and can afford to allocate all the memory up front) or a Circular buffer. For more details you can check my post that explains in more details why the LinkedList is slower.

Conclusion

  • Use LinkedList when you need a Queue, or when all your insert operations are done at specific points and you don’t need to traverse the list repeatedly (often) to find the insert positions.
  • Use ArrayList for anything else.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s