Are LinkedLists an unintuitive solution since most of the time I don't need to know the physical location of an element in a Collection?

Question

Recently a coworker showed me some code he had written with a LinkedList and I couldn't get my head around it.

a -> b -> c -> d -> e -> f

If I want to get d from the LinkedList, don't I have to traverse the list starting with a and iterating up to d or starting with f and iterating back to d?

Why would I care WHERE d is stored physically in the Collection?

Answer 1

Linked lists typically have better performance characteristics than arrays for adding and removing elements.

And yes, if you're operating on sorted data, you do normally care what order elements are stored in.

Answer 2

Not every linked list is linked in both directions but, normally, yes. This type of collection features sequential access in the forward or forward and reverse directions.

The advantages are:

• least amount of memory overhead except for a flat array
• very fast insert and delete
• memory can be allocated and released one element at a time
• easy to implement (not so important with modern languages but it was important in C89 and C99)
• LIFO or FIFO ordering is possible

Answer 3

I think that the right question is not WHERE, but HOW it stored your collection. According to this, your time of adding, searching, deleting and keeping your collection consistent is different. So, when you choose your type collection you should keep in mind, what will be the most frequent operation and pick the best solution for your case.

Answer 4

You probably don't care, regardless of whether you're using a LinkedList or an ArrayList. LinkedLists offer the advantage of being able to easily add elements to the beginning of a list, which you can't do with an ArrayList.

Answer 5

Lists are not about "physical locations" (whatever you mean by that), lists are a certain data structure that can grow and shrink and provide decent complexity across the various operations.

Answer 6

You don't have to explicitly traverse the linked list, as LinkedList offers indexOf(Object) and get(int). These will still traverse the list, but will do it implicitly.

You'll care about how a collection orders items because this affects efficiency of operations on the collection, particularly insert, fetch & removal. Any ordering on the items in a collection also affect timing of algorithms that use the data structure.