Présentation de la collection LinkedList

1. Histoire deLinkedList

Java a une autre classe de collection Java héritée du langage C++. C'est la LinkedListclasse qui implémente une "liste chaînée".

Extérieurement, a LinkedListsemble être le même qu'un ArrayList. La LinkedListclasse a toutes les mêmes méthodes que la ArrayListclasse. En principe, vous pouvez toujours utiliser a LinkedListau lieu de a ArrayListet tout fonctionnera.

Alors pourquoi avons-nous besoin d'une autre classe de liste ?

La réponse a tout à voir avec la structure interne de la LinkedListclasse. Au lieu d'un tableau, il utilise une liste doublement liée . Nous expliquerons ce que c'est un peu plus tard.

La LinkedListstructure interne différente de la classe permet d'insérer plus rapidement des éléments au milieu de la liste.

Sur Internet, vous pouvez souvent trouver des comparaisons des classes ArrayListet LinkedList:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Tout semble assez clair : si vous avez besoin d'insérer souvent des éléments dans la liste, utilisez LinkedList; si rarement, utilisez ArrayList. Mais la réalité est un peu différente.

2. Personne n'utiliseLinkedList

Personne n'utilise LinkedList.

Même l'auteur de la LinkedListclasse a récemment tweeté : "Quelqu'un utilise-t-il réellement LinkedList? Je l'ai écrit, et je ne l'utilise jamais."

Alors, quel est le problème ?

Tout d'abord, la ArrayListclasse a commencé à pouvoir insérer très rapidement des éléments au milieu de la liste. Lors de l'insertion d'un élément au milieu de la liste, vous devez décaler tous les éléments après le point d'insertion de 1 vers la fin de la liste. Cela prenait du temps.

Mais maintenant tout a changé. Tous les éléments d'un tableau sont proches les uns des autres dans le même bloc de mémoire, donc l'opération de décalage des éléments s'effectue par une commande de bas niveau très rapide : .System.arraycopy()

De plus, les processeurs d'aujourd'hui ont un grand cache qui peut généralement contenir l'ensemble du tableau, ce qui permet aux éléments du tableau d'être déplacés à l'intérieur du cache plutôt qu'en mémoire. Un million d'éléments sont facilement décalés en une seule milliseconde.

Deuxièmement, la LinkedListclasse peut insérer rapidement des éléments si vous les insérez à l'aide d'un itérateur. Si vous utilisez un itérateur pour parcourir un LinkedListet insérez constamment de nouveaux éléments (ou supprimez des éléments existants), l'opération est super rapide.

Si vous ajoutez simplement des éléments à un LinkedListobjet à l'intérieur d'une boucle, chaque opération d'insertion rapide s'accompagne d'une opération lente "obtenir l'élément".

La réalité est beaucoup plus proche de ceci :

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Pourquoi obtenir un élément d'une LinkedListopération si lente ?

Vous pouvez répondre à cette question après vous être un peu familiarisé avec la façon dont LinkedListil est structuré.

3. Comment LinkedListest structuré

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.