Shulou(Shulou.com)06/01 Report--

This issue of the content of the editor will bring you about how to achieve LinkedList source code analysis, the article is rich in content and professional analysis and description for you, after reading this article, I hope you can get something.

We focus on the LinkedList collection class. Unlike ArrayList, the underlying layer of LinkedList is implemented through a two-way linked list. Let's introduce the knowledge of two-way linked list. ArrayList underlying array has a big performance problem when dealing with business, that is, if we delete an element from the middle of the array, we have to pay a high price. The reason is that after deleting the element, all the elements after the element will be moved to the front end of the array, so it will cause performance loss. Similarly, there will be the above problems when inserting elements in the middle of the array. So when the designers of Java were trying to solve the performance problems of ArrayList, LinkedList was born. Because the bottom layer is implemented in a two-way linked list, there will be no problems such as the above. Let's take a closer look at the linked list data structure.

The underlying implementation of the array is the information of objects stored in continuous memory, but this is not the case in the linked list. It stores each object in a different independent node, and in addition to the data information to be saved, the reference information of the previous node and the reference information of the next node are also stored in each node. In Java, they can be called precursor nodes and successor nodes. As shown in the following figure:

So when we use the LinkedList collection class, it is convenient to delete an element from the LinkedList, and the performance is very high, because it only needs to delete the references of the precursor and successor nodes in the corresponding node, and there is no need to perform other additional operations. As shown in the following figure:

Therefore, through the characteristics of the above two-way linked list data structure, we know that when using LinkedList collection classes, if there are frequent insert and delete operations, then using LinkedList collection classes will be more efficient. However, the retrieval speed of the LinkedList collection is much lower than that of the ArrayList collection, because the storage mode of the double-linked list is not necessarily continuous memory, so in the retrieval, we must search backward one by one from the first node of the double-linked list, so it will consume a lot of query time and reduce the running performance of the program. Let's take a look at the source code of the LinkedList collection class to see how the underlying layer implements the above functions.

The constructor of LinkedList, here only defines an empty constructor, and there is no other logical implementation. Some people may want to say, then we can not define this empty construction method at all, anyway, the virtual machine will be created automatically for us, so why define an empty one? The virtual machine does automatically create an empty constructor for the class, but there is a condition that there can be no other constructors in the current class. If the virtual machine finds that there are already other constructors in the current class, the virtual machine will not automatically create a new constructor for us when it executes. In fact, there are many parameter construction methods in LinkedList, so the above parameter-free construction method is created just to facilitate us to create parameter-free LinkedList objects and to instantiate them.

The main way to add a method in LinkedList is to call the linkLast () method, which shows that this method is the main method to implement the logic of the whole add () method. Let's take a look at the source code of this method.

We see that a Node class is used in this method, so let's look at the definition of this class first.

Now we know that this Node class is an inner class in the LinkedList collection, and its work is equivalent to a node in a double-linked list, so this class stores not only the current element, but also the precursor node and successor node of the element. So the first two lines of code in the linkLast () method mean to save the current node to a new node, then set the last element in the linked list as the precursor node of the current element, and then set the successor node of the current element to null. This adds the data to the current node. So the add () method in the LinkedList collection adds elements to the back end of the linked list every time, which is the root cause of keeping the order of elements stored in the LinkedList collection. The purpose of setting the successor node to null is that this node is the last node in the double linked list.

Through the above analysis, we know that the LinkedList collection, like the ArrayList collection, is not thread-safe, so it is necessary to add additional synchronization code to ensure the thread safety of the collection.

The above is the editor for you to share how to achieve LinkedList source code parsing, if you happen to have similar doubts, you might as well refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.