Introducing the LinkedList collection

1. History of LinkedList

Java has another collection class Java inherited from the C++ language. This is the LinkedList class, which implements a "linked list".

Outwardly, a LinkedList appears to be the same as an ArrayList. The LinkedList class has all the same methods as the ArrayList class. In principle, you can always use a LinkedList instead of an ArrayList and everything will work.

So why do we need another list class?

The answer has everything to do with the internal structure of the LinkedList class. Instead of an array, it uses a doubly linked list. We'll explain what that is a little later.

The LinkedList class's different internal structure makes it fastest at inserting elements in the middle of the list.

On the Internet, you can often find comparisons of the ArrayList and LinkedList classes:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Everything seems clear enough: if you need to insert elements into the list often, use LinkedList; if rarely, then use ArrayList. But reality is a little different.

2. Nobody uses LinkedList

Nobody uses LinkedList.

Even the author of the LinkedList class recently tweeted: "Does anyone actually use LinkedList? I wrote it, and I never use it."

So what's the deal?

First, the ArrayList class began to be able to insert elements into the middle of the list very quickly. When inserting an element in the middle of the list, you have to shift all the elements after the insertion point by 1 towards the end of the list. This used to take time.

But now everything has changed. All the elements of an array are near one another in the same block of memory, so the operation to shift the elements is performed by a very fast low-level command: System.arraycopy().

In addition, today's processors have a large cache that can usually hold the entire array, which allows the array elements to be shifted inside the cache rather than in memory. A million elements are easily shifted in a single millisecond.

Second, the LinkedList class can insert elements quickly if you insert them using an iterator. If you use an iterator to go through a LinkedList and constantly insert new elements (or remove existing ones), the operation is super fast.

If you simply add elements to a LinkedList object inside a loop, then each fast insert operation is accompanied by a slow "get element" operation.

The reality is much closer to this:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Why is getting an element from a LinkedList such a slow operation?

You can answer that question after getting a little acquainted with how LinkedList is structured.

3. How LinkedList is structured

LinkedList has a different internal structure than ArrayList. It does not have an internal array for storing elements. Instead, it uses a data structure called a doubly inked list.

Each element of a doubly linked list stores a reference to the previous element and the next element. This is somewhat like a line at a store, where each person remembers the person standing in front of them as well as the person standing behind them.

This is what such a list looks like in memory:

The head and tail (cells with a gray background) are the first and last variables, which store references to Node objects.

In the middle, you have a chain of Node objects (objects, not variables). Each of them consists of three fields:

• prev — stores a reference (link) to the previous Node object (cells with a yellow background).
• value — stores the value of this element of the list (cells with a green background).
• next — stores a reference (link) to the next Node object (cells with a blue background)

The second object (address F24) is the next (next) for the first object and the previous (prev) for the third object. The yellow field of the third object contains the address F24 and the blue field of the first object contains the address F24.

The arrows from the first and third objects point to the same second object. So it would be more correct to draw the arrows like this.

4. Insert an element to a linked list

To add someone to line like this, you just need to get the permission of two people standing next to one another. The first person remembers the newcomer as "the person behind me", and the second person remembers them as "the person in front of me".

All you need to do is change the references of the two neighboring objects:

We added a new item to our list by changing the references of the second and third objects. The new object is the next for the old second object and the previous for the old third object. And, of course, the new object itself needs to store the correct references: its previous object is the old second object, and its next object is the old third object.

Removing an element is even easier: If we want to remove, let's say, the 100th object from the list, we just need to change the next field for the 99th object so that it points to the 101st object, and change the prev field for the 101st object so that it points to the 99th. That's it.

But getting the 100th object is not so easy.

5. Remove an element from a list

To get the 100th element of a linked list, you need to:

Get the 1st object: You do this using the first variable in the LinkedList object. The next field of the 1st object stores a reference to the 2nd object. That's how we get the second object. The 2nd object has a reference to the third, and so on.

If we need to get a reference to the 100th object, we need to sequentially move through all the objects from the 1st to the 100th. And if we need the millionth element in a list, we need to iterate over a million objects one after another!

And if these objects were added to the list at different times, they will be located in different parts of memory and are unlikely to end up in the processor's cache at the same time. This means that iterating over the elements of a linked list is not just slow, but very slow.

That's what we're dealing with.

So why are we teaching you how this slow LinkedList works?

Well, during job interviews you will be asked how LinkedList differs from ArrayList. Definitely.