Arraylist and LinkedList
Data structure implementation: ArrayList is a data structure implementation of dynamic arrays, while LinkedList is a data structure implementation of bidirectional linked lists.
Random access efficiency: ArrayList is more efficient than LinkedList at random access, because LinkedList is linear data storage, so you need to move the pointer back and forth.
Add and delete efficiency: LinkedList is more efficient at adding and deleting non-beginning and end than ArrayList, because ArrayList adds and deletes affect the subscripts of other data in the array.
In general, ArrayList is recommended for frequent reads of elements in a collection, and LinkedList is recommended for heavy inserts and deletions.
ArrayList and LinkedList both implement the List interface, and they differ in the following ways: ArrayList is an index-based data interface, and its underlying layer is arrays. It can randomly access elements in order of O(1) time. In contrast, LinkedList stores its data as a list of elements, each linked to its preceding and following element, in which case the time to find an element is O(n). Compared to ArrayList, LinkedList inserts, adds, and deletes are much faster because there is no need to recalculate or update the index as an array does when an element is added anywhere in the collection. LinkedList takes up more memory than ArrayList because LinkedList stores two references for each node, one to the previous element and one to the next.
What is the difference between ArrayList and Vector? Why replace Vector with Arraylist?
Thread-safe: Vector uses Synchronized for thread synchronization and is thread-safe, whereas ArrayList is non-thread-safe.
Performance: ArrayList outperforms Vector in terms of performance.
Capacity expansion: ArrayList and Vector both dynamically adjust their capacity based on actual needs, except that Vector doubles its capacity each time it expands, whereas ArrayList only increases its capacity by 50%.
What is the capacity expansion mechanism of ArrayList?
ArrayList is an implementation class of the List interface that supports dynamically growing arrays on demand. Standard arrays in Java are fixed-length, and they cannot be lengthened or shortened after they are created. This means that we need to know the required length of the array when we create it, but sometimes we need to get the array length in a dynamic program. Arraylists are made for this purpose.
Therefore, it is important to understand its expansion mechanism to use it. \
ArrayList expansion occurs when the add() method is called. Here is the source of the add() method: \
public boolean add(E e) {
/ / capacity
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Copy the codeEnsureCapacityInternal () is used for capacity expansion. The parameter is minimum capacity expansion.
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
Copy the codeObtain from method calculateCapacity(elementData, minCapacity) :
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// If an empty array is passed in, the minimum capacity is the maximum between the default capacity and minCapacity
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
Copy the codeYou can use the ensureExplicitCapacity method to determine whether expansion is required:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// If the minimum required space is larger than elementData's memory space, it needs to be expanded
if (minCapacity - elementData.length > 0)
/ / capacity
grow(minCapacity);
}
Copy the codeArrayList grows ()
private void grow(int minCapacity) {
// Get the memory size of the elementData array in ArrayList
int oldCapacity = elementData.length;
// Expand by 1.5 times
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the size of the new array is large enough, use this size to create a new array.
// If not, set the array length to the desired length
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the default value is greater than the default value, check for overflow
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Invoke the arrays. copyOf method to point the elementData array to the contiguable space of newCapacity when the new memory space is used
// Copy elementData's data to the new memory space
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeFrom this method, we can clearly see that the essence of ArrayList expansion is to calculate the size of the new expanded array, instantiate it, and copy the contents of the original array into the new array.
At this point, expansion is basically complete.
Array and ArrayList?
Array can store basic data types and objects, and ArrayList can store only objects.
Array is assigned a fixed size, whereas ArrayList is automatically expanded.
There are not as many built-in Array methods as ArrayList. For example, addAll, removeAll, iteration, and other methods are available only in ArrayList.
The difference between fail-fast and fail-safe?
Iterator’s security failure is based on making a copy of the underlying collection, so it is not affected by changes made on the source collection. All collection classes under the java.util package fail quickly, while all classes under the java.util. Concurrent package fail safely. Rapid failure of the iterator will throw ConcurrentModificationException, iterators and safety failure never throw this exception.
What is the difference between Iterater and ListIterator?
(1) We can use Iterator to iterate over sets and lists, whereas ListIterator can only iterate over lists.
(2) Iterator can traverse only forward, whereas LIstIterator can traverse both ways.
(3) ListIterator inherits from the Iterator interface and then adds some additional functionality, such as adding an element, replacing an element, and getting the index position of the preceding or following element.
The underlying structure of LinkedList
LinkedList is implemented based on a bidirectional circular LinkedList and can be used as a stack, queue, and double-ended queue in addition to being a LinkedList operation. LinkedList is also non-thread-safe and is only suitable for use in a single thread.
ArrayList data structure
The underlying data structure of an ArrayList is an array whose elements are of type Object. All operations on an ArrayList are based on arrays. The default capacity is 10
