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