The difference between ArrayList and LinkedList and the principle of using scene locality

It depends on the difference between the two classes , We need to see how they are implemented first . Here I will briefly describe their implementation principle .

First , They all inherit list（ surface ） This interface , Table is one of the three abstract data types , Both of these classes operate on tables . Then the table defines the methods they must implement in this interface , such as add(E),get(int),remove(int),set(E) And other basic table operations , Then the two classes implement the basic operations of these tables according to their own methods .

ArrayList The implementation principle and the points for attention ： First , It is the most basic structure composed of an array , then , The difference between it and an array is that it can change the size of the array . for instance , When we create an array, we size it , Only get and set Other methods , No, add Method , Then if you want to add Method , Create a large array , Then there is a method to copy short arrays into long arrays , Put the original array into the new array . As for how large an array to create , I haven't studied it carefully , When I write, I just take 1.5 Times the size of the original array capacity （ But in fact, this is not very scientific , Because if the number increases a lot , You may need to expand the capacity several times , This affects the efficiency of the program , If you add an element here , Then there may be too much capacity expansion , Waste space ）, Then other methods are basic operations .

LinkedList The implementation principle and the points for attention ： It is actually a two-way linked list , Write node class , Understand the meaning of the linked list .

ArrayList The advantage of this is that get and set Method calls take constant time （ This is for index ）, The disadvantage is that the insertion of new items and the deletion of existing items are time-consuming and space consuming , Because essentially it moves data . and LinkedList On the contrary , Its advantage is that the cost of inserting new items and deleting existing items is very small , We can know from the principle of linked list , For example, deleting an existing item , Put the previous node . Of . Attributes that point to the next node . Change to the next node pointing to it . See the online simple basic tutorial for specific operation . But it's get It takes a lot of time , Because it has to find that position from beginning to end , Is to move the pointer , You can't jump to that position like an array .

therefore , According to their advantages and disadvantages , You can know ,ArrayList It is suitable for frequent query and data acquisition , For example, the data storage of a library database , Its daily life is to see where the book is , Or other attributes such as the author of the book , Instead of adding new books or throwing away old ones every day .LinkedList It is suitable for adding or deleting data frequently , For example, if you want to do the storage of popular mobile phones in the last decade , Then it will be updated very quickly , Mobile phones will be eliminated soon , The emergence of new popular mobile phones is also very fast . You need to LinkedList 了 .

It is suggested that you can take a look at the implementation of these two classes written by yourself on the Internet , Than jdk The source code is much simpler , But the idea is similar .

Inspired by a netizen , Decided to share some basic things again .

Let me add that here , Because it (arraylist) Is the basic structure of array , So its search is faster , For example, in an array, we want to get a[5], So we use a[0] Add 4 Multiply by the byte length of each array element . So the time required here is a constant time . So it is faster to search by index . And what we usually say is to find elements directly , For example, in an array, the search value is 9 The number of , Looking for a number in an unordered array can only be traversed from beginning to end , In this way, it is the same time efficiency as the traversal of the linked list . however , because The locality principle of operating system The existence of （ Unfamiliar students can refer to ： He Bingrong ： double for Different ways to iterate through a two-dimensional array Locality principle Cache line cpu jdk Solution and He Bingrong ： operating system Virtual memory technology These two articles have a deeper understanding ）, The continuous storage space of array makes full use of the principle of locality , in other words Hardware cache acceleration Access to arrays , The discrete storage of linked list is doomed to be not faster . Insert and delete are as I said , Insert the length of the array to be increased , So create a new array to store the original array and the newly inserted elements , That is, move data . Deleting an element is similar .

And about the linkedlist, Its insertion and deletion are faster because of the basic characteristics of linked lists , Such as the 1,2,3 Three nodes , If you want to delete the second node , Only the attributes of the first node are required : Attributes that point to the next node , Point to the third node （ It turned out to point to the second node ） that will do , Then the second node is automatically jvm As garbage , wait until cpu The garbage collection thread will clean up the second node as garbage at the corresponding time . This is the linked list deletion node . Insertion is a similar principle , I'll stop talking . And about finding , According to the composition principle of the linked list , To get an element of a one-way linked list , You must start from the beginning , Do a walk , Judge whether it is equal to the value of the element you want to find . Until we find it . So the search here can be said to be O(n) Time for ( On the complexity of time space , I'll start with what I've been in touch with ). So the search efficiency is low .

Some netizens asked why linkedlist Use a two-way linked list instead of a single linked list , Here's another word : Look at the source code directly , Located its get(int) function , And finally see node(int) function . Then I will popularize the basic knowledge first , I don't know if you understand , A two-way linked list is better than a single linked list , structurally , That is, the node class of a two-way linked list needs one more attribute , It refers to the attributes of the previous node , stay c Middle is called pointer . In this way, two-way traversal can be realized efficiently . Then go back to what I said before node(int) function , It determines the position of the index in the whole linked list , Then choose to traverse backwards from the first node , Or traverse forward from the last node , such , its Traversal time is reduced by half , The single linked list can only traverse from the beginning to the end . In this way, the time efficiency of the two-way linked list is high . then , On the whole , Because its node class adds an attribute pointing to the previous node , It is more flexible to manipulate data , I suggest you take a look at the source code . Then it is due to the addition of this attribute , So its addition and deletion are a little more complicated , After all, you should specify where the attribute pointing to the previous node points to , But it doesn't matter , The impact is not big .

in addition , If you don't understand anything, please ask questions in the comment area , As long as there are questions, I will certainly try my best to answer them . I don't know how your foundation is , So some things may be thoughtless . therefore , Communication is the best way to solve problems . thank you

------ Small update ----

1. Be careful , because arraylist Deleting an element in the will change its length , So pay attention when traversing and comparing , When you delete an element , All subsequent elements move forward , therefore , If you want to compare, you need to compare again from the original position , Otherwise, the backward movement of your pointer will cause you to ignore the element just moved forward . You can try deleting duplicate elements in an object , Then think about it and you will know what happened .

2.vector It's synchronous , Everything else goes with arraylist almost , When we open its source code, we can see that the methods that basically operate the array structure are added synchronized modification , It is necessary to obtain the lock before surface operation this, Then we can operate . So the efficiency is relatively low . and arraylist and linkedlist It's all out of sync , To synchronize it, you can create it in other ways when you create it , concrete API file . Then in the actual development , We usually save data for query , So we usually use arraylist. Then pay attention to linkedlist Used to construct queues , The stack is convenient , Because it is convenient to manipulate the front and back pointers and elements , So building FIFO or LIFO is so easy Of . You can try it .