[introduction to Java] day27 detailed explanation of Java container class (IX) detailed explanation of LinkedList

This time, let's introduce LinkedList, another practitioner of the list interface. It is a list interface practitioner integrating many skills. It can be described as 18 kinds of martial arts and proficient in everything. It can be used to simulate stack, queue, double ended queue, linked list and two-way linked list. Don't say much. Come and have a look.

This article will analyze LinkedList from the following aspects:

　　1. LinkedList overall structure.

　　2. The LinkedList basic operation uses chestnuts.

　　3. Comparative analysis of LinkedList and ArrayList.

　　4. LinkedList overall source code analysis.

LinkedList overall structure

Let's take a look at the structure in LinkedList. LinkedList is different from ArrayList. ArrayList dynamically maintains an array, and all operations are performed on the data. In fact, LinkedList is node by node, and each node is connected end to end. If you still remember the previous articles, you should remember that there are nodes in HashMap, but there are still many differences between the two. Let's take a look at the nodes in LinkedList first. 　

Well, it's actually very simple. There are only three member variables. Item is used to store specific element information. Next points to the next node, prev points to the previous node, and node nodes are connected through next and prev to form a two-way linked list.

LinkedList basic operations use chestnuts

Next, let's take a look at some basic operations in LinkedList. Here is a small Chestnut:

Here we only demonstrate the linked list operation of LinkedList, mainly including add, addall, remove, set, etc. almost every common method has overloaded methods. For example, the add method with only one parameter will directly insert the element into the tail of the list, while the add method with two parameters will insert the element into the specified position.

Comparative analysis of LinkedList and ArrayList

You may ask, isn't ArrayList also very useful? ArrayList can also be used for those operations. Why use LinkedList?

This is a good problem. The biggest feature of ArrayList is that it can be accessed randomly. Because elements are stored continuously physically, when accessing, you can directly locate the specified location through a simple algorithm. Therefore, no matter how many elements in the queue, you can always locate the specified location in O (1) time, but continuous storage is also its disadvantage, When an element is inserted in the middle, all subsequent elements must move back. The insertion of LinkedList only needs to adjust the references of the front and rear elements.

Then let's actually compare the efficiency gap:

First, abstract the timing into a template. For each operation that needs time-consuming statistics, you only need to inherit this class, and then override the dosomething method.

When it is inserted at the head end every time, ArrayList needs to move elements every time, and the more elements in the list, the more times it needs to move. In this case, LinkedList is obviously better than ArrayList.

Therefore, in fact, the two have their own strengths and weaknesses. In general, it is good to select ArrayList, unless the number of circular operations reaches the order of ten thousand. You may say that since the efficiency difference between the two is not big under normal circumstances, it's better to use ArrayList directly. Why do you say so much. Ha ha, if you think so, you are very wrong. First of all, we need to know not only why, but also why. It is not enough to know that LinkedList is more efficient than ArrayList, but we don't know why or how high it is. Secondly, we can not only consider the normal situation, but also need preventive measures for extreme situations. Thinking about extreme situations is the biggest difference between experts and novices.

Let's look at the comparison of finding elements:

ArrayList wins completely. It can be seen that finding elements in the LinkedList is a very time-consuming operation, even longer than inserting elements, because each time you get, you search one by one from both ends of the linked list until you find the specified location. If you want to know the specific details, take a patient look at the source code analysis below.

LinkedList overall source code analysis

Let's take a look at the overall structure of LinkedList:

You can see that LinkedList has four internal classes: node, listitr, descendingiterator and llsplitter. Node class is mainly used to store elements. Let's take a look at node:

This is the simplest class, and also constitutes the basis of LinkedList, which is composed of node connections. Let's look at the listitr class:

This class is the iterator class of LinkedList, which is mainly used to traverse LinkedList in sequence. In the previous chestnut, there are hasnext and next methods using iterators. In fact, their implementation is very simple. Hasnext simply compares whether the sequence number of the next element to be accessed is greater than the number of elements in the list. The next method assigns the reference of next to the lastreturned variable, Then point next to its next node and add 1 to the index. However, unlike ordinary iterators, this iterator can not only traverse in positive order, but also use the previous method to traverse in reverse order. The descendingiterator uses the previous method of the iterator for convenience.

This iterator is relatively simple. It just wraps a listitr instance and overloads several methods of the iterator. Llsplitter is a separable iterator for parallel streams, which will not be introduced here.

Let's look at the implementation of several common methods:

When inserting an element, a new node object will be created, and the value will be placed in the node node, and then hung at the end of the linked list.

For the overloaded version of add, you can specify the sequence number for insertion and insert the elements into the middle of the linked list. The operation process can be understood in connection with the previous figure.

It can be seen that the get method actually traverses and locates from the head or tail, moving the reference of X backward / forward one bit at a time. When the amount of linked list data is relatively large, this process is actually time-consuming, which should also be found in the previous comparison.

The remove method also has two overloaded versions. The remove method without parameters only removes and returns the last node, while the remove method with specified sequence number parameters will remove and return the node at the specified position in the linked list.

In addition, the linked list has many methods that can be used for queues:

That is, the operation of one-way queue can be realized through the above methods, or the operation of two-way queue can be realized by using addfirst, addlast, removefirst and removelast methods. The following is an implementation of a simple queue:

Well, it's actually about laying eggs with chickens, ha ha.

Let's take a look at the simple stack implementation of LinkedList:

You see, it's actually very simple. LinkedList provides a large number of methods that can easily implement data structures such as linked list, two-way linked list, queue, double ended queue and stack. It can be said to be very easy to use.

The following is all the source code of LinkedList. If you have spare power, you can choose the part you want to understand for reading. If you don't understand anything, you can leave a message at the back of this article. Of course, you can skip it directly. It's not too late to read when you want to know more about it in the future.

Finally, make a simple summary of LinkedList:

LinkedList is a structure composed of nodes connected end to end. Compared with ArrayList, there is no need to move a large number of elements during insertion and deletion, which saves the cost of element replication and capacity expansion. However, each time a node is added, a new node object needs to be created. Therefore, when there are a large number of nodes, this part of the object will occupy a lot of overhead, It includes time cost and space cost, so it needs to be reasonably selected according to the actual situation. LinkedList provides a large number of convenient methods to obtain, insert and remove elements, so it can easily implement data structures such as queue and stack.