Daily question: the difference between ArrayList and LinkedList

---

ArrayList

• ArrayList It's an array queue , It's like a dynamic array . And Java The array in , Its capacity can grow dynamically . It is inherited from AbstractList, Realized List,RandomAccess,Cloneable,java.io.Serializable These interfaces .

• ArrayList Inherited AbstractList, Realized List. It's an array queue , Provides related additions 、 Delete 、 modify 、 Ergodic function .

• ArrayList Realized RandmoAccess Interface , Random access .RandmoAccess yes java Used in List Realization , by List Provides quick access to . stay ArrayList in , We can quickly get the element object through the element's ordinal number ; This is fast random access .

• ArrayList Realized Cloneable Interface , That overrides the function clone(), Can be cloned .

• ArrayList Realized java.io.Serializable Interface , It means ArrayList Support serialization , Can be transmitted by serialization .

• Be careful ：ArrayList Operations in are not thread safe ！ therefore , It is recommended to use... In a single thread , In case of multithreading, you can choose CopyOnWriteArrayList Or use Collections Medium synchronizedList Method to wrap it as a thread safe List.

• ArrayList I realized serialization and deserialization , Because it does writeObject and readObject Method .

• ArrayList Based on the array implementation , It will automatically expand .

• When adding elements, you will determine whether you need to expand the capacity , It is best to specify an approximate size , Prevent memory consumption caused by multiple capacity expansions ; There is no loss of capacity when deleting elements , When deleting elements , Set the deleted location element to null, The next time gc It will automatically reclaim the space occupied by these elements .

• ArrayList It's not thread safe .

• Use iterator Traversal can throw multithreaded exceptions .

LinkedList

LinkedList It is a linear list realized by linked list （ Double linked list ）.
LinkedList characteristic ：

• Two way linked list
• Elements are ordered , The output sequence is consistent with the input sequence
• The allowed element is null
• To find a node , You must traverse from the beginning .（ Slow query , Additions and deletions quickly ）
  and ArrayList equally , Not a synchronization container

Linked list ： Linked list is an important data structure , There are single linked lists and double linked lists

• Single chain list （ One way linked list ）： It's made up of two parts Data fields （Data） And node domain (Node), A single linked list is like a rope with many knots , Each knot is equivalent to a knot , Each node is connected by a rope , This principle is realized through Node The header pointer of the node area head Realized , Each node has a pointer , Each node pointer points to the next node of its own node , Of the last node head Pointing to null, In this way, it becomes a chain like the rope mentioned above , The operation of single linked list can only start from one end , If you need to find a node in the linked list , You need to traverse from the beginning .

• Double linked list （ Double linked list ）： Double linked list and single linked list , One more pointer to the tail （tail）, Each node of the double linked list has a header pointer head And tail pointer tail, Double linked list is easier to operate than single linked list , The first node of the double linked list node head Pointing to null,tail Pointing to the next node tail; At the end head Point to the previous node head,tail Pointing to null, It's a two-way relationship ;
  If you need to find an element in a single linked list , Must start with the first element , The two-way linked list stores two pointers in each node except the first node and the last node , These two pointers point to the address of the previous node and the address of the next node respectively , In this way, no matter which node you pass through, you can find other nodes .

• Insert delete does not need to move elements outside , You can insert or delete in place

• You can insert data before and after the structure

• It can traverse in two directions

ArrayList and LinkedList difference

• Underlying data structure ：ArrayList Array is used at the bottom ;LinkedList The bottom layer uses a double linked list ;

• Insert and delete elements ：ArrayList Using array storage , Therefore, the insertion and deletion of elements are related to the position of elements .LinkedList It uses linked list storage , Deleting an element is not affected by its position ; If it is in the specified location i Insert and delete words （（add(int index,E element）） The time complexity is approximately O(n), Because it needs to be moved before inserting .

• Random access ：ArrayList The efficiency of random element access is significantly higher than LinkedList high . Random access is to get elements through their indexes （ That is to say set and get(int index) Method ）.

• Thread unsafe ：ArrayList and LinkedList It's all out of sync , That is to say, they are thread unsafe .

• Interface implementation ：ArrayList Realized RandomAccess Can support random element access , and LinkedList Realized Deque It can be used as a queue

• Memory usage ：ArrayList The occupation of space is mainly reflected in list There will be some capacity space at the end of the list , Its advantage is memory continuity ,CPU The internal cache structure of caches contiguous memory segments , It can greatly reduce the performance overhead of memory , Increase of efficiency ;LinkedList The use of space is reflected in the fact that each element needs to consume space and memory , It is necessary to store data such as predecessor and successor .

• When the operation is to add data after a column of data rather than before or in the middle , And when you need to access elements randomly , Use ArrayList Will provide better performance ;

• When the operation is to add or delete data before or in the middle of a column of data , And access the elements in order , Use LinkedList Will be better .