1.List interface features
The java.util.List interface inherits from the Collection interface. The biggest difference from Map is that it is a single-column Collection, equivalent to a List, with the following features:
- It’s sequential, it’s stored in the order it’s added, it’s a linear structure.
- Elements can be queried by index.
- Elements can be repeated.
An ordered collection(also known as a sequence ).The user of this interface has precise control over where in the list each element is inserted.The user can access elements by their integer index(position in the list), and search for elements in the list.
Unlike sets, lists typically allow duplicate elements. More formally,lists typically allow pairs of elements e1 and e2 such that e1.equals(e2), and they typically allow multiple null elements if they allow null elements at all. It is not inconceivable that someone might wish to implement a list that prohibits duplicates, by throwing runtime exceptions when the user attempts to insert them, but we expect this usage to be rare.
The following is the inheritance of the List interface:
2. Source code analysis of the List interface
Inheriting from the Collection interface, it has the order, the order of fetching is the same as the order of storing, it has the index, it can get data according to the index, it can store duplicate elements, it can put elements as null. The three most common implementation classes are ArrayList, Vector,LinkedList, ArrayList, and Vector, which encapsulate operations on arrays. The only difference is that Vector is thread-safe, whereas ArrayList is not. In theory, ArrayList operations should be more efficient than Vector operations.
Inside is the interface definition method:
int size(a); // Get the size
boolean isEmpty(a); // Check whether it is null
boolean contains(Object o); // Whether to contain an element
Iterator<E> iterator(a); // Get the iterator
Object[] toArray(); // Convert to array (object)
<T> T[] toArray(T[] a); // Convert to array (specific bits of a class)
boolean add(E e); / / add
boolean remove(Object o); // Remove the element
boolean containsAll(Collection
c); // Whether to include all elements
boolean addAll(Collection<? extends E> c); // Batch add
boolean addAll(int index, Collection<? extends E> c); // Batch add, specify the starting index
boolean removeAll(Collection
c); // Batch remove
boolean retainAll(Collection
c); // Remove elements not contained in c
default void replaceAll(UnaryOperator<E> operator) {}/ / replace
default void sort(Comparator<? super E> c) {}/ / sorting
void clear(a);// Clear all elements
boolean equals(Object o);// Whether it is equal
int hashCode(a); // Compute to get the hash value
E get(int index); // Get the element by index
E set(int index, E element);// Modify the element
void add(int index, E element);// Inserts the element at the specified position
E remove(int index);// Remove an element based on the index
int indexOf(Object o); // Get index by object
int lastIndexOf(Object o); // Gets the last element of the object element
ListIterator<E> listIterator(a); // Get the List iterator
ListIterator<E> listIterator(int index); // Retrieves the current position iterator based on the index
List<E> subList(int fromIndex, int toIndex); // Intercepts a piece of data
default Spliterator<E> spliterator(a){} // Get the sharable iterator
Copy the codeMore commonly used methods are nothing more than add, delete, change and check:
E get(int index); // Get the element by index
E set(int index, E element);// Modify the element
void add(int index, E element);// Inserts the element at the specified position
E remove(int index);// Remove an element based on the index
Copy the codeListIterator (ListIterator) is a more powerful Iterator that inherits from Iterator and can only be used for List access. ListIterator () is called to get a listIterator that points to the beginning of a List, or listIterator(n) is called to get a listIterator that specifies an element with index N, which is an iterator that can move in both directions. Operation when the array index need to pay attention to, as many implementation class for the bottom of the List is an array, so the index cross-border complains IndexOutOfBoundsException.
3. Introduction of related subclasses
When it comes to implementing subclasses of List, the most important implementation classes are as follows:
ArrayList: The underlying storage structure is an array structure, which is slow to add and delete and fast to search. It is the most commonly used List collection. Threads are not safe.LinkedList: The bottom is the linked list structure, increase and delete faster, but the search is slower. Threads are not safe.Vector: Similar to ArrayList, but thread-safe, i.e. synchronous.
3.1 ArrayList
class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess.Cloneable.java.io.Serializable
Copy the codeArrayList inherits AbstractList interface and implements List, as well as random access, clonable, serialized interfaces. Is not thread safe, if you need thread safety, you need to choose other kind or use Collections. SynchronizedList (arrayList) allows the null elements, also allows the same element exists.
The bottom layer is actually an array implementation, so why do we just store things in it and don’t care about the size? Because ArrayList encapsulates such functionality, the capacity can change dynamically without requiring the consumer to care.
3.1.1 Member Variables
Transient means that the attribute does not need automatic serialization, because Element stores not the object of the real element, but the address to the object, so serialization of the attribute does not make much sense. After the address is serialized, the original object cannot be found during deserialization, so you need to implement the object serialization manually.
// Actually access the data array
transient Object[] elementData;
// The actual number of elements (not the size of elementData, but the number of elements stored)
private int size;
Copy the codeSo where do you serialize and deserialize that? This requires looking at the readOject() and writeOject() methods in the source code. In addition to the default serialization of other fields, the elementData field needs to be manually serialized and deserialized.
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// The number of times the original changes need to be saved before the sequence. New changes are not allowed during serialization
int expectedModCount = modCount;
// Write non-static and non-transient fields of the current class to the stream, which is the default serialization
s.defaultWriteObject();
// Add case to the output stream
s.writeInt(size);
// Serialize each element sequentially, using 'writeOject()'
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// If there are changes during serialization, an exception will be thrown
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}// deserialize
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read the default deserialized data
s.defaultReadObject();
// Read the size
s.readInt(); // ignored
if (size > 0) {
// Like clone(), space is allocated based on size, not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Loop through each element
for (int i=0; i<size; i++) { a[i] = s.readObject(); }}}Copy the codeMany of you may wonder, why isn’t this function called? Where is it called? In fact, is in the object flow, through the reflection of the way to call, here will not expand, next time certain!! Have a look if you are interested.
If we create without specifying a size, a default size of 10 will be initialized.
private static final int DEFAULT_CAPACITY = 10;
Copy the codeIt defines two empty arrays, EMPTY_ELEMENTDATA is called an empty array,DEFAULTCAPACITY_EMPTY_ELEMENTDATA is called an empty array of default size, which is used to distinguish between an empty constructor and an arrayList constructed with an argument constructor. The first time an element is added, a different expansion is used. It’s an empty array, not null, because we need to specify the type of the argument when we use it.
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the codeThere is also a special member variable modCount, which is required by the fast fail mechanism, which records the number of modification operations, mainly during iteration, to prevent elements from being modified. If the number of changes before and after an operation does not match, then some operations are illegal. Transient indicates that the attribute does not need automatic serialization.
protected transient int modCount = 0;
Copy the codeThe serialization ID is as follows: Why do I need this field? This is because if the field is not displayed, the serialization process automatically generates a serialized ID. In this case, if a field is added to the original class after the serialization, the deserialization will fail because the default serialization ID has been changed. If we give it a serialization ID, we can avoid this problem, but the added field will be empty when deserialized.
private static final long serialVersionUID = 8683452581122892189L;
Copy the code3.1.2 Construction method
There are three constructors, you can specify the capacity, you can specify the initial set of elements, and you can specify nothing.
// Specify the size of the initialization
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}// Specify nothing, default is empty element set
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// Pass in a set, convert it to an array, and copy it as a display dataset
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if((size = a.length) ! =0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else{ elementData = Arrays.copyOf(a, size, Object[].class); }}else {
// replace with empty array.elementData = EMPTY_ELEMENTDATA; }}Copy the code3.1.3 Commonly used methods of adding, deleting, modifying and checking
Add elements
There are two add() methods:
add(E e): Adds an element, at the end by defaultadd(int index, E element): Adds (inserts) an element at the specified index position
public boolean add(E e) {
// Determine whether the capacity is sufficient, sufficient will not increase
ensureCapacityInternal(size + 1);
// where size+1, assign the current e
elementData[size++] = e;
return true;
}
// Inserts an element at the specified position
public void add(int index, E element) {
// Check whether the insertion position is valid
rangeCheckForAdd(index);
// Check whether the capacity needs to be expanded and whether the capacity is sufficient
ensureCapacityInternal(size + 1); // Increments modCount!!
// copy the elements after index, moving them one bit behind (this is the underlying native method of c++ implementation)
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// Insert the element at index
elementData[index] = element;
// The actual number of stored elements increases
size++;
}
Copy the codeQuery element
The get() method is relatively simple, and returns elements by checking that the arguments are valid before fetching.
public E get(int index) {
// check the subscript
rangeCheck(index);
return elementData(index);
}
// check the subscript
private void rangeCheck(int index) {
if (index >= size)
// The array is out of bounds
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeUpdate the element
Set () is a bit like get(), but you must specify the element subscript to change, check the subscript, modify it, and return the old value.
public E set(int index, E element) {
// check the subscript
rangeCheck(index);
// Get the old value
E oldValue = elementData(index);
// Modify the element
elementData[index] = element;
// Return the old value
return oldValue;
}
Copy the codeRemove elements
Remove by element, or remove by subscript
public E remove(int index) {
// check the subscript
rangeCheck(index);
// The number of changes is changed
modCount++;
// Get the old element
E oldValue = elementData(index);
// Calculate the subscript to move (move one bit ahead)
int numMoved = size - index - 1;
if (numMoved > 0)
// Call the native method to copy the following element and move it forward
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Leave the previous element empty to facilitate garbage collection
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
// is an empty element
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true; }}else {
// traverse, if equals, then call delete
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
// Quick delete method
private void fastRemove(int index) {
// The number of changes increases by 1
modCount++;
// Calculate the position of the move
int numMoved = size - index - 1;
if (numMoved > 0)
// Move the front one bit
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
/ / empty
elementData[--size] = null; // clear to let GC do its work
}
Copy the codeArrayList is dynamically scalable based on arrays, so when was it scalable? The add() method is called when the collection is initialized or when an element is added to the collection. Grow () is called when the minimum call capacity is insufficient. Grow () is the real expansion function, which is not expanded here.
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the code3.1.4 Summary
- ArrayList is based on a dynamic array, and adding elements can trigger expansion operations. After capacity expansion, array copy is triggered. The remove operation also triggers replication, with the following elements moved one bit ahead, leaving the previous last element empty to facilitate garbage collection.
- The default initial capacity is 10. If the capacity is insufficient, the capacity is increased to 1.5 times the original capacity.
- It’s not thread-safe, but elements can be repeated, and they can be null, and it’s important to note that every time you fetch it, you need to check if it’s null.
3.2 LinkedList
LinkedList bottom is two-way linked list implementation, this is the biggest difference between and ArrayList, besides it also implements the Deque interface, inherit AbstractSequentialList AbstractSequentialList inherited AbstractList. It is also thread-unsafe.
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable.java.io.Serializable
Copy the codeThe underlying data structure of the bidirectional list is as follows:
private static class Node<E> {
// Data of the current node
E item;
// Next node
Node<E> next;
// Last node
Node<E> prev;
// constructor
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the code3.2.1 Member Variables
There are three main member variables. The reason why the record records both the head node and the tail node is mainly for faster insertion and data search.
// 元素个数
transient int size = 0;
// 链表的首节点
transient Node<E> first;
// 俩表的尾节点
transient Node<E> last;
Copy the code3.2.2 Constructors
There are two main constructors, one is a no-argument reach, and the other is a function that needs to initialize the set of elements by calling the batch-adding function addAll().
public LinkedList(a) {}public LinkedList(Collection<? extends E> c) {
this(a);// call the function to add elements in batches
addAll(c);
}
Copy the code3.2.3 Common Functions
Add elements
linkFirst()Add an element to the queue headerLinkLast ()Add an element at the end of the queue
// Add elements to the header
public void addFirst(E e) {
linkFirst(e);
}
// Add elements to the tail
public void addLast(E e) {
linkLast(e);
}
private void linkFirst(E e) {
/ / the first node
final Node<E> f = first;
// Create a new node. Next of the new node is the first node
final Node<E> newNode = new Node<>(null, e, f);
// make the new node as the first node
first = newNode;
/** * Determine if the newly added node is the first element */
if (f == null)
// If this is the first time a node is added to the list, then last needs to be set to the new node
last = newNode;
else
// If this is not the first time a node has been added to the list, then the first element (pointer) before the original node points to the new node
f.prev = newNode;
// Number of elements +1
size++;
// Number of changes +1
modCount++;
}
void linkLast(E e) {
/ / end nodes
final Node<E> l = last;
// Create a new node where the preceding element is the previous element (the pre pointer of the new node points to the previous element)
final Node<E> newNode = new Node<>(l, e, null);
// Make the current newly inserted node become the tail node
last = newNode;
// Check whether the last node before is empty
if (l == null)
// If it is empty, it means that the node was not inserted and the current node is the first node.
first = newNode;
else
// If it is not empty, the next element (pointer) of the last node points to the new node.
l.next = newNode;
// The number increases
size++;
// The number of changes increases
modCount++;
}
Copy the codeCall the add() method, which adds elements to the tail by default.
public boolean add(E e) {
linkLast(e);
return true;
}
Copy the codeOf course, in addition to adding an element at the end, you can also add an element at a specified position in the middle, using the following method.
public void add(int index, E element) {
// Check if index is in a valid range
checkPositionIndex(index);
// If index is equal to size, we should just add the element at the end
if (index == size)
linkLast(element);
else
// Otherwise you need to call linkBefore to insert before
linkBefore(element, node(index));
}
Copy the codeThere is a function called node(index), which gets the node based on the index. The interesting thing is that if the index is in the first half, it traverses from the front, and if the index is in the second half, it traverses from the back. Determine what part of it is using binary.
Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}Copy the codeIf index is equal to size, insert the element at the end. If index is equal to size, insert the element at the end. If index is equal to size, insert the element at the end.
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
Copy the codeInsert node linkLast() at the end:
void linkLast(E e) {
// Save the last element
final Node<E> l = last;
// Create a new node with the last element before it
final Node<E> newNode = new Node<>(l, e, null);
// Make the new node the last node
last = newNode;
// If the last node is empty
if (l == null)
// The original list is empty, so the first element is now the inserted element
first = newNode;
else
Otherwise, the next element of the original element is specified as the new element
l.next = newNode;
// The size changes
size++;
// The number of changes is changed
modCount++;
}
Copy the codeInsert before a node, calling linkBefore
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
// Get the preceding node of the current node
final Node<E> pred = succ.prev;
// Create a new node with a pointer to pred and a pointer to succ
final Node<E> newNode = new Node<>(pred, e, succ);
// Succ starts with a pointer to newNodesucc.prev = newNode; If pred is emptyif (pred == null)
// This indicates that the previous list is empty and the newly inserted node is the first node
first = newNode;
else
// Otherwise, the next node pointer to the previous node points to the new node
pred.next = newNode;
// Increase the size by 1
size++;
// The number of changes increases
modCount++;
}
Copy the codeQuery element
Get (int index)
public E get(int index) {
// check whether the subscript is valid
checkElementIndex(index);
// Call the node(index) method above directly, and return the item after retrieving the node
return node(index).item;
}
Copy the codeModify the element
To modify an element, the set(index,element) method is called. The set(index,element) method is used to find the node and then modify its item attribute.
public E set(int index, E element) {
// Verify the validity of index
checkElementIndex(index);
// Find the node
Node<E> x = node(index);
// Save the original node
E oldVal = x.item;
// Change item to a new element
x.item = element;
// Return the old element
return oldVal;
}
Copy the codeRemove elements
removeFirst(): Removes the first elementremoveLast(): Removes the last elementremove(Object object): remove the objectpop(): Removes the first elementremove(): Removes the first elementremove(int index): Removes the element whose index is indexclear(): Removes all elements
Delete the first element
public E removeFirst(a) {
// Fetch the first element
final Node<E> f = first;
// If it is empty, it is illegal
if (f == null)
throw new NoSuchElementException();
// Actually remove the first element from the list
return unlinkFirst(f);
}
Copy the code private E unlinkFirst(Node<E> f) {
// assert f == first && f ! = null;
// Save the item of the current element
final E element = f.item;
// Fetch the next node next
finalNode<E> next = f.next; Set the item of the first element to zeronullTo facilitate garbage collection f.tem =null;
// The next pointer is set to null
f.next = null; // help GC
// Set first to the next element
first = next;
// If the next node is null, the list is empty after the first element is deleted
if (next == null)
last = null;
else
// Otherwise, the next front node needs to be empty
next.prev = null;
// The size is reduced
size--;
// The number of changes increases
modCount++;
return element;
}
Copy the codeRemove the last element:
public E removeLast(a) {
// Fetch the last node
final Node<E> l = last;
// If the last node is null, it is illegal
if (l == null)
throw new NoSuchElementException();
// Actually remove the last element from the list
return unlinkLast(l);
}
Copy the code private E unlinkLast(Node<E> l) {
// assert l == last && l ! = null;
/ / save the item
final E element = l.item;
// Retrieve the previous node
final Node<E> prev = l.prev;
// Empty the item of the current node
l.item = null;
// The front node is empty
l.prev = null; // help GC
// Set the last node to the preceding node that was just saved
last = prev;
// If the previous node is empty, then the list has only one element.
if (prev == null)
first = null;
else
// Otherwise, null is required for next
prev.next = null;
// The size is reduced
size--;
// The number of changes is increased
modCount++;
return element;
}
Copy the codeRemove the specified object, here refers to the node inside the item, from the source, only remove the first element that meets the condition, return true, otherwise return false.
public boolean remove(Object o) {
// If o is null
if (o == null) {
for(Node<E> x = first; x ! =null; x = x.next) {
// Check whether item is null
if (x.item == null) {
// Remove node X if the conditions are met
unlink(x);
return true; }}}else {
for(Node<E> x = first; x ! =null; x = x.next) {
// We use the equal method to determine whether or not we are equal
if (o.equals(x.item)) {
// 满足条件则移除x
unlink(x);
return true; }}}return false;
}
Copy the codeThe first element is removed by default, and since LinkedList is a two-way list, pop() and reomve() are both removed by default.
public E pop(a) {
return removeFirst();
}
public E remove(a) {
return removeFirst();
}
Copy the codeTo remove an element whose index subscript is index, find the node first and call unlink(node) to remove the node.
public E remove(int index) {
// Check the validity
checkElementIndex(index);
return unlink(node(index));
}
Copy the codeRemove all nodes:
public void clear(a) {
// Loop to empty the element
for(Node<E> x = first; x ! =null;) { Node<E> next = x.next; x.item =null;
x.next = null;
x.prev = null;
x = next;
}
// The first element and the last element are null
first = last = null;
// set the size to 0
size = 0;
// The number of changes increases
modCount++;
}
Copy the code3.2.4 Summary
The underlying LinkedList is a bidirectional LinkedList that implements the List and Queue interfaces, allowing all elements to be contained, and elements to be null. How to save data when LinkedList is null? A null node does not hold data, but the data is stored in the item below the node, so item can be null.
Each node holds a reference to the previous node and the reference to the next node, as well as data for the current node.
Because of the underlying bidirectional list and the implementation of the Queue interface, it can also be used as a bidirectional Queue.
Thread is not safe, multithreaded environment is easy to operate the bottom linked list error operation.
3.3 the Vector
Vector is similar to ArrayList except that Vector is thread-safe. AbstractList inherits AbstractList, implements List, RandomAccess, Cloneable interface, can be randomly accessed, can also be cloned.
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
Copy the code3.3.1 Member Variables
The bottom layer is the array, add elements, when the array space is insufficient, need to expand.
- ElementData: An array that actually holds data
- ElementCount: The actual number of elements
- CapacityIncrement: capacityIncrement coefficient
- SerialVersionUID: serialized ID
// An array of real data
protected Object[] elementData;
// Number of elements
protected int elementCount;
// Capacity increase coefficient
protected int capacityIncrement;
// serialize the ID
private static final long serialVersionUID = -2767605614048989439L;
Copy the code3.3.2 Constructors
Specifies the capacity and growth factor constructors
public Vector(int initialCapacity, int capacityIncrement) {
super(a);// Invalid judgment
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// Initialize the array
this.elementData = new Object[initialCapacity];
// Specify the growth coefficient
this.capacityIncrement = capacityIncrement;
}
Copy the codeSpecifies the initial capacity. The growth factor defaults to 0
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
Copy the codeThe default size given is 10:
public Vector(a) {
this(10);
}
Copy the codeSpecify collection initialization:
public Vector(Collection<? extends E> c) {
// Convert to an array
Object[] a = c.toArray();
// Size is the size of the array
elementCount = a.length;
// If it is ArrayList, copy it directly
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
// Otherwise, copy itelementData = Arrays.copyOf(a, elementCount, Object[].class); }}Copy the code3.3.3 Common methods
increase
Add elements, by default, at the end
public synchronized void addElement(E obj) {
// The number of changes increases
modCount++;
// Ensure that the capacity is sufficient (if necessary, there will be expansion, copy operations)
ensureCapacityHelper(elementCount + 1);
// Add the new element to the last element
elementData[elementCount++] = obj;
}
Copy the codeSo how does it ensure capacity? As you can see from ensureCapacityHelper(), check whether the number of elements added is greater than the current array length. If not, expand the array. Call the grow() function for expansion.
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// Capacity expansion, passing in the minimum required capacity
private void grow(int minCapacity) {
// overflow-conscious code
// The previous capacity
int oldCapacity = elementData.length;
// The current capacity is the old capacity plus the expansion factor, if the expansion factor is less than or equal to zero, then it is twice the old capacity
int newCapacity = oldCapacity + ((capacityIncrement > 0)? capacityIncrement : oldCapacity);// If the new capacity is greater than the minimum required capacity, it is sufficient
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the new capacity is larger than the maximum capacity
if (newCapacity - MAX_ARRAY_SIZE > 0)
// The maximum capacity needs to be reduced
newCapacity = hugeCapacity(minCapacity);
// Copy data
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeAt the specified index index, insert data, actually call insertElementAt(Element, index).
public void add(int index, E element) {
insertElementAt(element, index);
}
// Call the function that inserts the element
public synchronized void insertElementAt(E obj, int index) {
// The number of changes increases
modCount++;
// Determine whether the index is illegal
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ ">" + elementCount);
}
// Make sure the capacity is sufficient
ensureCapacityHelper(elementCount + 1);
// Copy the data and move the following element one bit back
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
// Insert the actual data
elementData[index] = obj;
// The number increases
elementCount++;
}
Copy the codeTo add all the elements of a collection:
public synchronized boolean addAll(Collection<? extends E> c) {
// The number of changes increases
modCount++;
// convert to array
Object[] a = c.toArray();
// The length of the array
int numNew = a.length;
// Make sure the capacity is sufficient
ensureCapacityHelper(elementCount + numNew);
/ / copy
System.arraycopy(a, 0, elementData, elementCount, numNew);
// Update the number
elementCount += numNew;
// Returns whether the added array has data
returnnumNew ! =0;
}
Copy the codeSpecify index, insert a set, and the difference is that before you copy it, you have to calculate how many bits to move to the back, so instead of using a for loop to insert, you move and write all at once.
public synchronized boolean addAll(int index, Collection<? extends E> c) {
// The number of changes increases
modCount++;
// Make a valid judgment
if (index < 0 || index > elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// Convert the array
Object[] a = c.toArray();
// Insert the array length
int numNew = a.length;
// Make sure the array length is legal
ensureCapacityHelper(elementCount + numNew);
// Calculate the step size of the move
int numMoved = elementCount - index;
if (numMoved > 0)
// Move the following element to make room for the inserted element
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// Insert elements
System.arraycopy(a, 0, elementData, index, numNew);
// Update the number
elementCount += numNew;
// Whether the number of inserted elements is 0
returnnumNew ! =0;
}
Copy the codedelete
Delete the specified element
public boolean remove(Object o) {
return removeElement(o);
}
// The actual call to removeElement() is
public synchronized boolean removeElement(Object obj) {
// The number of changes increases
modCount++;
// Get the epitome of the first element that meets the condition
int i = indexOf(obj);
// index if the condition is met
if (i >= 0) {
// Remove the element with index I from the array
removeElementAt(i);
return true;
}
return false;
}
// Operate the array to remove elements
public synchronized void removeElementAt(int index) {
// The number of changes increases
modCount++;
// Is it legal
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + "> =" +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
// The number of elements after index
int j = elementCount - index - 1;
if (j > 0) {
// Move one bit ahead (copy, overwrite)
System.arraycopy(elementData, index + 1, elementData, index, j);
}
// Update the number
elementCount--;
// The last element is left empty
elementData[elementCount] = null; /* to let gc do its work */
}
Copy the codeDelete elements by index:
public synchronized E remove(int index) {
// The number of changes increases
modCount++;
// Check the validity
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// Save the original data
E oldValue = elementData(index);
// The number of moves
int numMoved = elementCount - index - 1;
// If the number of moves is greater than 0
if (numMoved > 0)
// Move the following element one bit ahead, assign, overwrite
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// The last element is null
elementData[--elementCount] = null; // Let gc do its work
// Return the old element
return oldValue;
}
Copy the codeModify the
The following two set functions are used to change the index of an element, the difference is that one will return the old element, the other will not return the old element.
public synchronized E set(int index, E element) {
// Check the validity
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// Fetch the old element
E oldValue = elementData(index);
/ / update
elementData[index] = element;
// Return the old element
return oldValue;
}
public synchronized void setElementAt(E obj, int index) {
// Make a valid judgment
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + "> =" +
elementCount);
}
// Update directly
elementData[index] = obj;
}
Copy the codeThe query
public synchronized E get(int index) {
// Make a valid judgment
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// Returns the element of the array
return elementData(index);
}
Copy the code3.3.4 Summary
Vector has a default capacity of 10 and an incremental coefficient. If specified, it increases the size of the coefficient by one at a time; otherwise, it doubles.
Expansion, in fact, is a copy of the array, in fact, is time-consuming, so we should try to avoid time-consuming expansion operations.
Unlike ArrayList, which is thread-safe and uses the Synchronize keyword for almost every method, it is relatively inefficient.
3.4 AbstractList by the way
AbstractListIs an abstract class that implementsListInterface, inheritedAbstractCollectionClass. Its internal implementation of some add, delete, change and check operations,
I wonder whyAbstractListimplementationListAnd again letArrayListGo to inheritAbstractList. Why do we do this? We inheritListNot line?
The main reason for this is to follow the principle that an interface can only have abstract methods, but an abstract class can also have concrete implementation methods in addition to abstract methods. And the realization of the List of analogy is more, such as ArrayList, LinkedList, Vector, etc., must have in common and general method. If they all implemented the List interface directly, they would generate some redundant and repetitive code. How neat would it be if these common things, generic methods, were abstracted out and implemented in AbstractList? Sweet!!!!!!
In this way, it is equivalent to adding an intermediate layer, the principle of computer design is always to add a buffer layer. (Manual dog head)
AbstractList AbstractList AbstractList AbstractList
3.4.1 Definitions and member variables
AbstractCollection class,AbstractList without arguments to construct protected modifier.
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
protected AbstractList(a) {}}Copy the codeMember variable: number of changes
protected transient int modCount = 0;
Copy the codeThere’s only one abstract method get()
abstract public E get(int index);
Copy the code3.4.2 Common methods
increase
Defines a set of criteria for the implementation of add methods, one at the end by default and one at the specified index location, but considering that different subclasses are implemented differently, this method must be implemented or an exception will be thrown.
public boolean add(E e) {
add(size(), e);
return true;
}
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
Copy the codeSpecify the location of the index to add all the elements in the collection
public boolean addAll(int index, Collection<? extends E> c) {
// Check whether index is valid
rangeCheckForAdd(index);
boolean modified = false;
// loop add
for (E e : c) {
add(index++, e);
modified = true;
}
return modified;
}
Copy the codeModify the
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
Copy the codedelete
Delete index element, do not implement, require subclass implementation
public E remove(int index) {
throw new UnsupportedOperationException();
}
Copy the code// Delete all elements
public void clear(a) {
removeRange(0, size());
}
Copy the codeDeletes elements in the specified range
protected void removeRange(int fromIndex, int toIndex) {
// Get the iterator to the position where deletion begins
ListIterator<E> it = listIterator(fromIndex);
// Loop delete
for (int i=0, n=toIndex-fromIndex; i<n; i++) { it.next(); it.remove(); }}Copy the codeThe query
Abstract methods, no implementation.
abstract public E get(int index);
Copy the codeQuery index location
// Query the index position of object
public int indexOf(Object o) {
// Get the iterator
ListIterator<E> it = listIterator();
if (o==null) {
// If the object is empty
while (it.hasNext())
// Do not use null because cursor+1 requires the previous index value
if (it.next()==null)
return it.previousIndex();
} else {
while (it.hasNext())
// Use equal
if (o.equals(it.next()))
return it.previousIndex();
}
return -1;
}
// Instead of the previous one, walk backwards from behind
public int lastIndexOf(Object o) {
ListIterator<E> it = listIterator(size());
if (o==null) {
while (it.hasPrevious())
if (it.previous()==null)
return it.nextIndex();
} else {
while (it.hasPrevious())
if (o.equals(it.previous()))
return it.nextIndex();
}
return -1;
}
Copy the codeIntercept the list
public List<E> subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList<>(this, fromIndex, toIndex) :
new SubList<>(this, fromIndex, toIndex));
}
Copy the codeRule 3.4.3 iterator
We can actually see thatAbstractListThere are two iterators defined, respectivelyItrandListItr.ItrTo achieve theIteratorInterface,ListItrTo achieve theListIterator, inheritedItr.
If we look closely, we’ll see that there are several methods that are related to manipulating iterators.
public Iterator<E> iterator(a) {
return new Itr();
}
public ListIterator<E> listIterator(a) {
return listIterator(0);
}
// Returns the iterator at the specified index
public ListIterator<E> listIterator(final int index) {
rangeCheckForAdd(index);
return new ListItr(index);
}
Copy the codeWhy does ** need two iterators? ** The question is always on my mind… Take a look at the source code for a moment:
private class Itr implements Iterator<E> {
// The index returned by the next call to next
int cursor = 0;
// Index returned from the last call to Next or previous
int lastRet = -1;
// The expected number of changes
int expectedModCount = modCount;
// As long as the curse is not equal to size, there are elements
public boolean hasNext(a) {
returncursor ! = size(); }// Get the next element
public E next(a) {
// Check whether it has been modified
checkForComodification();
try {
// Save the cursor
int i = cursor;
// Get the element
E next = get(i);
// Change the last returned index to the latest I
lastRet = i;
// Update the cursor index that will be returned next time
cursor = i + 1;
// Return the element
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw newNoSuchElementException(); }}// Delete operation
public void remove(a) {
// Last return
if (lastRet < 0)
throw new IllegalStateException();
// Check the number of changes
checkForComodification();
try {
// Call the external method remove
AbstractList.this.remove(lastRet);
// The element is removed and the cursor needs to be moved backwards
if (lastRet < cursor)
cursor--;
// The element lastRet accessed last time does not exist
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw newConcurrentModificationException(); }}// Check whether the number of changes after the operation is equal to the expected number of changes
final void checkForComodification(a) {
if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the codeThe following code makes me wonder why I need to determine whether the last accessed index is less than the index returned by next to execute -1
if (lastRet < cursor)
cursor--;
Copy the codeThen I found the answer in ListItr code, because ListItr has a method called previous() that rewinds the previous element of the iterator, and if previous() is executed, the element returned last time is the same element returned next time, So it’s possible to have lastRet= cursor at this point.
ListItr
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
// Whether there is an element in front
public boolean hasPrevious(a) {
returncursor ! =0;
}
public E previous(a) {
// Check the number of changes
checkForComodification();
try {
// Get the preceding element index
int i = cursor - 1;
// Get the previous element
E previous = get(i);
// The index of the last element accessed and the index of the next call should be set to I (equivalent to cursor-1).
lastRet = cursor = i;
// Return the previous element
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw newNoSuchElementException(); }}// Next index
public int nextIndex(a) {
return cursor;
}
// Last index
public int previousIndex(a) {
return cursor-1;
}
// Modify the last accessed element
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// Call an external method
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}// Add a new element
public void add(E e) {
checkForComodification();
try {
int i = cursor;
// Add the element to the current position of the iterator
AbstractList.this.add(i, e);
// Do not care about lastRet
lastRet = -1;
// The index of the next element needs +1
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}}Copy the codeWhy do we need two iterators? We find that Itr actually only has two methods, next() and remove(), which are suitable for most ordinary subclasses, while ListItr has an upgraded version of hasPrevious, which backtracks to the previous element, and the set() and add() methods. The Itr is a common iterator, inherited by ListIterator and PrimitiveIterator. The difference between two iterators:
With Iterator you can only move forward, but with ListIterator you can move backward words when reading elements. With ListIterator, you can get the index at any time during traversal, whereas iterators cannot. With Iterator, you can only check whether the next element is available, but in Listiterator, you can check the last and the next element. With Listiterator, you can add new elements at any point in the traversal. Using iterators is not possible. With Listiterator, you can modify elements over time, whereas iterators cannot.
Checked the Stack Overflow, the answer link: stackoverflow.com/questions/1…
This could be the answer:
Since Java 5 it is simply possible to override a method with a more specific return type (called covariant return type). But ListIterator has been introduced with Java 1.2. To avoid casts on usage of iterator() there has to be a new method.
The API could not have been changed from Java 5 on because that would have broken all implementations of List which do not declare iterator() returning ListIterator also if most implementations return a ListIterator instance in real.
A similar dilemma is Enumeration and Iterator. Nowadays Iterator would extend Enumeration and simply add the remove() method. Or better Iterator would have replaced Enumeration and a ModifiableIterator with an additional remove() would have been added.
Because Java 5 can override methods with more specific return types, known as covariant return types. But ListIterator was introduced in Java 1.2. To avoid casting the use of iterator(), a new method is necessary.
The API cannot be changed starting with Java 5, because this would break all List implementations that do not declare iterator() to return ListIterator, if most implementations actually return ListIterator instances.
Similar dilemmas are enums and iterators. Now the iterator extends the enumeration and simply adds the remove() method. Or a better iterator would replace the enumeration and add an extra remove() to add a ModifiableIterator.
Personal opinion: This is done on the basis of compatibility and extensibility during iteration. Some people say it is based on one-way lists and two-way lists to consider, seems to have a little truth.
3.4.4 Summary
AbstractList AbstractList AbstractList AbstractList AbstractList AbstractList AbstractList AbstractList AbstractList AbstractList AbstractList AbstractList AbstractList AbstractList A method that has part abstract method and part implementation and is a layer between a List and a concrete container implementation class such as ArrayList.
4. To summarize
List interface, mainly to achieve the List interface standard, commonly used three subclasses are:
- ArrayList
- The bottom layer is array, expansion is to apply for new array space, copy
- Thread insecurity
- The default initial capacity is 10, and the capacity expansion is 1.5 times the previous capacity
- Queries are faster
- LinkedList
- At the bottom is a bidirectional list that can be traversed backwards and forwards
- There is no expansion, can be used as a two-way queue
- It’s faster to add and delete
- The lookup is optimized so if index is in the front half, you go from the front, index is in the back half, you go from back to front.
- Vector
- At the bottom is an array, with almost all methods Synchronize
- Thread safety
- If this parameter is not set, the default value is double the original length. If this parameter is set, the increment is the same size as the increment factor.
AbstractList AbstractList is an abstract class extended from List, which defines some general methods. It makes up for the fact that List is an interface and cannot implement methods. It is equivalent to adding an intermediate layer. It defines two Iterator classes and provides methods to get them, which can be used by different subclasses.
This article only represents their own (this rookie) learning accumulation record, or learning notes, if there is infringement, please contact the author to delete. No one is perfect, the article is the same, the writing style is immature, I am not talented, do not spray, if there is a mistake, also hope to point out, grateful ~
The road of technology is not at that time, the mountain is high and the water is long, even if it is slow, and not stop.