Let's take a look at the Collection. List is a sub interface of the Collection, mainly to see several classes under it.
1,AbstractList
2,ArrayList
3,Collections.synchronizedList
4,Vector
5,LinkedList
6,CopyOnWriteArrayList
1, AbstractList
This is an abstract class, which is the basic class for implementing the List interface. ArrayList, LinkedList and Vector all inherit this abstract class.
1> If you want to implement an immutable list, you must implement the get(int) and size() methods
2> If you want to implement a modifiable list, you must implement set(int,E). If the size of the list is variable, you must also implement the add(int,E) and remove(int) methods
It has two built-in iterators, Itr and ListItr. The inheritance relationship is as follows
(1)Itr
private class Itr implements Iterator<E> {
//cursor
int cursor = 0;
//The current index value of the subscript when the next method is called
//, reset to - 1 if the remove method is called
int lastRet = -1;
//The number of times the list has been modified, such as adding, deleting, modifying, and expanding
int expectedModCount = modCount;
//Are there any elements
public boolean hasNext() {
return cursor != size();
}
//Returns the next element
public E next() {
checkForComodification();
try {
int i = cursor;
//The get method calls the concrete implementation class
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
//Delete current element
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
//Check whether the list structure has been modified by other threads during iteration
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
(2)ListItr
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
//Returns the previous element
public E previous() {
checkForComodification();
try {
int i = cursor - 1;
E previous = get(i);
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
//Set value
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//Add element
public void add(E e) {
checkForComodification();
try {
int i = cursor;
AbstractList.this.add(i, e);
lastRet = -1;
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
These two iterators are called in the indexOf, lastIndexOf, and removarange methods
For example, the removehange method
protected void removeRange(int fromIndex, int toIndex) { //Get iterator, fromIndex namely Itr Inside cursor ListIterator<E> it = listIterator(fromIndex); for (int i=0, n=toIndex-fromIndex; i<n; i++) { it.next(); it.remove(); } } public ListIterator<E> listIterator(final int index) { rangeCheckForAdd(index); return new ListItr(index); } private class ListItr extends Itr implements ListIterator<E> { ListItr(int index) { cursor = index; } }
2, ArrayList
This list is the most commonly used. It inherits from AbstractList. It is non thread safe. Concurrent modificationexception will be thrown under multithreading
(1) The default capacity is 10
private static final int DEFAULT_CAPACITY = 10;
(2) The underlying data structure is an Object array
transient Object[] elementData;
(3) The capacity expansion mechanism is that the capacity expansion is 1.5 times of the current capacity. See the add method
public boolean add(E e) {
//The key is the method
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
Look at the ensureCapacityInternal method for capacity expansion
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(
calculateCapacity(elementData, minCapacity)
);
}
Let's first look at the calculateCapacity method
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
If no size is specified when creating the list, the maximum is taken from minCapacity and default capacity. Otherwise, minCapacity is returned directly
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//If minCapacity is greater than the current array length, the capacity will be expanded
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
The core method of capacity expansion is the growth (mincapacity) method.
private void grow(int minCapacity) {
//Current capacity
int oldCapacity = elementData.length;
//New capacity, 1.5 times the current capacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
It can be seen that the capacity after expansion is 1.5 times of the current capacity
3, Collections synchronizedList
The List obtained with Collections is thread safe, and it is locked on the code block with the synchronized keyword. The specific initial capacity and expansion depends on what kind of List is passed in
The returned list is synchronized randomaccesslist or synchronized list, and synchronized randomaccesslist is a subclass of synchronized list
Therefore, we mainly look at the Synchronized list. We can see that all methods of this class are locked with Synchronized.
4, Vector
Vector is rarely used. It is also a subclass of AbstractList.
(1) The default capacity is 10
public Vector() {
//Call another constructor
this(10);
}
The above default empty construction calls the following construction method, which sets capacityIncrement to 0, which is useful in capacity expansion
You can also initialize capacity and capacityIncrement with the following structure
(2) The underlying data structure is an Object array
protected Object[] elementData;
(3) The capacity expansion mechanism is 2 times by default. You can also manually set capacityIncrement capacity expansion
(4) Thread safe, lock the method with Synchronized
5, LinkedList
The linked list structure is as follows. In addition to inheriting AbstractList, it also implements Queue.
(1) The underlying implementation is a Node by Node. There are references of front and rear nodes in the Node, which can be connected into a chain
6, CopyOnWriteArrayList
This is more awesome. Its Chinese name is copy when writing. Belonging to JUC and contracting, thread safety is a variant of ArrayList.
(1) Initialization is an Object array with a capacity of 0
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
This array uses volatile to ensure variable memory visibility.
private transient volatile Object[] array;
(2) Use ReentrantLock (recursive lock, also known as reentrant lock) to lock, expand the capacity to add 1 to the capacity once, and then use arrays Copyof copies the old array into the new array, which consumes more memory.
=======================================================
I'm Liusy, a programmer who likes fitness.
Welcome to follow the wechat official account [Liusy01], exchange Java technology and fitness together, and get more dry goods.