The difference between Arraylist and Linkedlist in java interview

Let’s first introduce the knowledge of Arraylist:

(Learning video sharing: java teaching video)

Arraylist: The bottom layer is based on a dynamic array. According to the following table, random access to array elements is highly efficient, and adding elements to the tail of the array is highly efficient;

However, deleting data in the array and adding data to the middle of the array are inefficient. , because the array needs to be moved. For example, the worst case scenario is to delete the first array element, which requires moving the 2nd to nth array elements forward one bit each. The reason why it is called a dynamic array is because Arraylist can be expanded when the array elements exceed its capacity (for JDK1.8, the capacity of the array after expansion is 1.5 times that before expansion). The largest array capacity in the Arraylist source code is Integer .MAX_VALUE-8, for the vacated 8 bits, the current explanation is:

①Storage Headerwords;

②To avoid some machine memory overflows and reduce the chance of errors, so less allocation;

③The maximum can still be supported is Integer.MAX_VALUE (when Integer.MAX_VALUE-8 still cannot meet the demand).

The following is part of the source code of Arraylist: Arraylist expansion:

(More interview questions to share: java interview questions and answers)

Add data to Arraylist: (Add to the end of the array)

#Add an array to the specified position of the array:

It can be seen that as long as the current capacity of ArrayList is large enough, the add() operation to the end of the array is very efficient. When adding data to the specified position of the array, a large number of array moving and copying operations will be performed. When the array is copied, the System.arraycopy() method will eventually be called, so the efficiency of the add() operation is still quite high. Even so, when adding data to a specified location, it is still slower than Linkedlist, which only needs to change the pointer to add data. Deleting an array in Arraylist also requires moving the array, which is slower.

Linkedlist is a dynamic array based on linked lists. Data addition and deletion are efficient and only need to change the pointer. However, the average efficiency of accessing data is low and the linked list needs to be traversed. Arraylist get data source code: (according to subscript access, high efficiency)

Linkedlist access data source code: (node() function traverses the linked list)

Summary:

1. For random access get and set, ArrayList is better than LinkedList because LinkedList needs to move the pointer.

For the new and deletion operations add and remove, LinedList has the advantage because ArrayList needs to move data.          

2. Respective efficiency issues:

Related recommendations: java introductory tutorial

The above is the detailed content of The difference between Arraylist and Linkedlist in java interview. For more information, please follow other related articles on the PHP Chinese website!