This is the 10th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021!

As you know, the List collection has three common subclasses:

  • ArrayList: The underlying structure is an array. Thread insecurity
  • LinkedList: the underlying structure is a two-way LinkedList. Thread insecurity
  • Vector: The underlying structure is an array. Thread safety

ArrayList parsingFirst, let’s look at the ArrayList propertyIt’s not hard to see that the bottom layer is an array, but isn’t the array fixed length? ArrayList can grow dynamically because it has an automatic expansion mechanism in it and let’s look at the constructorLet’s take a look at our usual methods:When adding elements, we should first check whether the list needs to be expanded before inserting elementsWe then call ensureExplicitCapacity () to specify the capacity, and let’s see what this method says Again, let’s look at the grow methodAfter the expansion, he calls the copyOf method, copies the original data into the new array, and then looks at the copyOf methodSo we know that when we implement add (), we first check to see if the array is large enough, and if not

  • Expand it by 1.5 times
  • If the capacity is still smaller than minCapacity after the first expansion, expand the capacity to minCapacity
  • Enough, add directly
  • If no, add it after capacity expansion

Now let’s look at this methodAnd then we look downThis method is written in C/C++. Look at the get method: Know it without thinking divided into 2 steps:

  • Check if the horn is out of bounds
  • Returns the element

  1. Set method

The default is to insert the end of the array.2. Remove method:The trimToSize () method is called. The thread is not safe. Null values can be stored because the bottom layer is an array, so the query efficiency is high. The efficiency of adding and deleting is lowThe difference between Vector and ArrayList: The biggest difference between vector and ArrayList is that both methods use the synchronized keyword.If you want ArrayList to synchronize, you can do this

List list = (List) Collections.synchronizedList(new ArrayList<Integer>());
Copy the code

Another difference is that vector will be doubled in size.Second, the LinkedList:The Deque interface is implemented, so we can operate on it like queues and stacksThe variable is implemented by a bidirectional list, so it is more efficient than the ArrayList constructor:1. The add: 2. Remove: 3. Get: As you can see, the get element iterates through the list, so its query is inefficient. But in order to speed up, here first judge if the subscript is less than half of the length, traversal from the beginning, and vice versa. (slightly faster) Set method:Just like the GET method, we use subscripts to determine how to traverse. To sum up:

  • ArrayList:
  1. The bottom implementation is array, so its query efficiency is high, the thread is not safe
  2. The default initial capacity of an ArrayList is 10, which increases by half, or 1.5 times, each time it is expanded
  3. The navite method is implemented by C/C++.
  • LinkedList:
  1. The underlying implementation is a bidirectional list [bidirectional lists facilitate implementation of traversal], so it is efficient to add and delete, but also thread unsafe
  2. Vector:
  3. The bottom layer is arrays, which are now used sparingly, replaced by arrayLists, for two reasons:
  4. Vector all methods are synchronous and have a performance penalty.
  5. Vector starts with a length of 10 and grows at a 100% rate beyond length, consuming more memory than ArrayList.

The biggest difference from ArrayList is thread-safety, which doubles when expanded.

He just began to operate the public number, interested can pay attention to my public number, wechat search “Altman chess”, welcome to exchange!