Week 2 – Java Containers – A detailed look at ArrayList, Vector, LinkedList

preface

Learning record

• Time: Week 2
• SMART sub-target: Java container

Note in learning Java container knowledge points, the List of important points to note.

Knowledge overview:

• ArrayList versus LinkedList
• What is the RandomAccess interface in ArrayList?
• What is the Deque interface in LinkedList?
• The old ArrayList expansion mechanism
• Compare an ArrayList with a Vector

ArrayList versus LinkedList

1. Underlying data structure:

   • ArrayList The Object array used at the bottom. The default size is 10.

     

     * * * *

   • LinkedList is a bidirectional LinkedList data structure that is used at the base of the LinkedList. Note the difference between a bidirectional list and a bidirectional circular list. LinkedList contains three important members: Size, first, and Last. Size is the number of nodes in a bidirectional list, and first and last refer to the first and last node, respectively.

     

2. Whether insert and delete are affected by element position:

   • Because of the underlying implementation, ArrayLists are stored in arrays, so the time complexity of inserting and deleting elements is affected by the location of the elements. For example, when the add(E E) method is executed, the ArrayList defaults to append the specified element to the end of the list, which is O(1) time. But if you want to insert and delete elements at position I (add(int index, E element)), the time is O(n-i). Because all the (n-i) elements after the ith and ith elements in the set are moved backwards/forwards by one bit. It’s actually approximately O(n).
   • However, LinkedList is stored in a LinkedList, so the time complexity of inserting and deleting elements is not affected by the location of elements and is approximately O (1).

3. Whether fast random access is supported or not: Again, this depends on the underlying implementation. LinkedList does not support efficient random access, whereas ArrayList does. Fast random access is a quick way to get an element object by its ordinal number (corresponding to the get(int index) method).

4. Memory space usage: The space waste of ArrayList is mainly reflected in the amount of space reserved at the end of list, while the space cost of LinkedList is reflected in the amount of space consumed by each element of ArrayList (because of the prev and next Pointers and data).

What is the RandomAccess interface in ArrayList?

As you can see from the previous figure, ArrayList inherits three interfaces, the last two of which are familiar: identifying objects as copiable and serializable.

So what does RandomAccess interface stand for?

One of the things about ArrayList versus LinkedList is,

Whether fast random access is supported or not: Again, this depends on the underlying implementation. LinkedList does not support efficient random access, whereas ArrayList does. Fast random access is a quick way to get an element object by its ordinal number (corresponding to the get(int index) method).

The RandomAccess interface is used to indicate that this class supports fast RandomAccess. Looking at the source code, you can see that there is no internal definition of this interface. It’s just a sign.

For example, in the collections.binarySearch () method,

Lists that implement RandomAccess use indexes, while lists that do not implement RandomAccess use iterators.

A List that implements RandomAccess can iterate over data more efficiently with a for loop than with an iterator. A List that does not implement RandomAccess can iterate over data more efficiently with an Iterator than with a for loop. Of course, the for loop traversal is not much different from Iterator traversal for arrayLists, but the efficiency gap is a bit larger for unimplemented linkedLists. This is mainly because the underlying implementation is different.

What is the Deque interface in LinkedList?

The LinkedList counterpart to ArrayList also has an interface worth studying, the Deque interface.

Deque-double-ended queue, which is called a double-ended queue in Chinese.

We know that a Queue is a Queue that follows the FIFO rule, and we know that a Stack is a Stack structure that follows the FILO rule. In other words, the class that implements this interface can be used as either a stack or a queue.

How do you use it as a queue? A Deque implements a Queue, so all methods of a Queue are available in a Deque.

How to use it as a stack? Let’s take a look at the method mappings for double-ended queues as stacks.

Because space is limited, the specific implementation of the source code will not take you to analyze.

Understand Java LinkedList source code

The old ArrayList expansion mechanism

This is a very frequent interview, so take note.

Here is the source code.

1. fromadd()Get started
2. ensureCapacityInternal(size + 1)Verify that the current array can accommodatesize + 1If there are not enough elements to expand
3. grow(minCapacity)This is the logic of specific expansion
   • The size of the new capacity isoldCapacity + (oldCapacity >> 1)That’s the old capacity1.5times
   • The capacity expansion operation needs to be calledArrays.copyOf()This method, which copies the entire array into the new array,This operation is very expensive, so many places, including The Ali development manual, recommend specifying the approximate size of the collection during initialization to reduce the number of capacity expansion.

Compare an ArrayList with a Vector

The underlying implementations of ArrayList and Vector are both Object arrays, so they are very similar in usage and properties.

The difference is,

• Vector is thread-safe and uses synchronized internally. This results in poor Vector performance. Instead, use an ArrayList and control the synchronization yourself.

• Vector is expanded by 2 times each time instead of 1.5

  

For thread-safe purposes, Vector has other alternatives:

• useCollections.synchronizedList()Get a thread-safe ArrayList (collections.synchronized ***() is a Wrapper)
• You can also use CopyOnWriteArrayList in J.U.C for read and write separation, as described later

reference

1. Understand the Java LinkedList source code
2. Code Efficient
3. Crazy Java Handouts
4. github cs-note
5. java guide