ArrayList, and LinkedList, these three classes implement the Java Vestor. Util. List interface, but they have different features, mainly as follows:
One, thread safety
Vector, Stack: thread-safe
ArrayList, LinkedList: not thread-safe
Second, the implementation method
LinkedList: a two-way LinkedList
ArrayList, Vector, Stack: Object array
Third, capacity expansion
Since ArrayList and Vector (Stack inherits from Vector and adds a few stack-related methods, so we won’t talk about Stack in particular) are implemented using arrays, they create a larger array when the array length is insufficient. Then copy the data from the original array to the new array.
Array length expansion policy: If the array length needs to be expanded, it must be at least (original length x 3)/2 + 1 each time
If the capacityIncrement is not specified when creating the Vector, the capacityIncrement must be at least twice the original length each time
Fourth, efficiency
The efficiency difference between ArrayList and LinkedList is only compared here
1, the query
An ArrayList is located directly by subscript
LinkedList is traversed, with an average number of traversals of n/4
Arraylists are much faster than LinkedLists for location-specific queries because they can be located directly by subscript
However, if all the queries are at the beginning and end, the situation will be very different, because the LinkedList can also be directly located at the beginning and end, and the efficiency of ArrayList and LinkedList is the same
2, insert
In the case of an ArrayList, the insertion of a specified location may require an expansion of the array’s capacity first, and then may cause the data in the array to be moved sequentially (this code is implemented by copying the array to avoid moving the data one by one). In extreme cases, the insertion of a single data will require two copies of the array.
If the insertion location is not specified, the array is inserted to the end of the array. In this case, you only need to consider the impact of possible array capacity expansion on performance
Overall, LinkedList is more efficient than ArrayList, which needs to consider the performance impact of possible capacity expansion even when inserted at the end
3, modify
This is the same case as a query
4, delete
Delete and insert at the specified location are in the same case
In addition to deleting location-specific data, arrayLists and LinkedLists both contain a clear() method to clear all data