Automatic bug maker 2022-05-14 15:00:05 阅读数:902
List Interface inherited from Collection , Except for inheritance Collection Ability in , It has expanded several default methods ：
// Batch modification
default void replaceAll(UnaryOperator<E> operator)
// Sort , It uses Arrays.sort
default void sort(Comparator<? super E> c)
// Location access operations
E get(int index);
E set(int index, E element);
void add(int index, E element); // Collection Yes add , This extends the designation index .
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
// iterator
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
// Containers
List<E> subList(int fromIndex, int toIndex);
Copy code Here is a brief introduction ,List Compare with Collection Expanded functions ：
List Is ordered .List It can be used for location indexing .List , It can be done to List Intercept .List The implementation of the interface includes ：Vector 、ArrayList 、LinkedList .
Based on dynamic array , Support random access . Allow storage to include null The elements of , In addition to the implementation List Outside the interface , It also provides some methods to deal with array expansion . It is associated with Vector The difference is that ,Vector It's synchronous , All operation methods are added synchronized modification . and ArrayList No, .
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable Copy code ArrayList Inherited from AbstractList , And implemented List 、RandomAccess. Cloneable and Serializable .
AbstractList
Yes List Some methods of the interface provide a default implementation , The simplest example is ,List There are polymorphic interfaces add Method , It was packaged ：
public boolean add(E e) {
add(size(), e);
return true;
}
public void clear() {
removeRange(0, size());
}
Copy code Some index operations are also implemented by default ：
public int indexOf(Object o) {
ListIterator<E> it = listIterator();
if (o==null) {
while (it.hasNext())
if (it.next()==null)
return it.previousIndex();
} else {
while (it.hasNext())
if (o.equals(it.next()))
return it.previousIndex();
}
return -1;
}
Copy code in addition , It also implements an internal private iterator Itr And sublist types SubList .
RandomAccess
Used to mark data structures that support random access . The main functions are , In some algorithms , For random access and sequential access , There will be different performance . The algorithm can recognize that the data structure marked by the interface is accessed randomly .
Cloneable
The ability to reproduce , The class that implements the interface can use Object.clone() Copy the instances of this class field by field .
Serializable
Serialization capability .
transient Object[] elementData;
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);
}
}
Copy code ArrayList The internal real data storage structure is an array .
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Copy code Adding data is sequential, adding new elements at the end of the array , When you add elements to a container , If the capacity is insufficient , The container will automatically increase the size of the underlying array .
Add In the method , The first call is ensureCapacityInternal(int) :
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
Copy code calculateCapacity The method is used to calculate the expansion quantity ：
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
Copy code When elementData When empty array , The first expansion is to return 10 and minCapacity The value of the larger party . Otherwise, it returns zero minCapacity. and add In the method size + 1 in other words , One at a time . This always keeps the number of elements = Array capacity , No waste of memory space .
The real expansion method is ensureExplicitCapacity in ：
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // The number of array modifications increases
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity); // The real expansion method
}
Copy code The internal logic is also very simple , When the minimum capacity required by the array minCapacity Greater than elementData when , super-popular , Through the real expansion method grow(int) To carry out ：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
Copy code ArrayList It also provides an automatic capacity adjustment method to save memory space ：
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA // EMPTY_ELEMENTDATA = {}
: Arrays.copyOf(elementData, size);
}
}
Copy code ArrayList It also uses a fast failure mechanism , Pass record modCount Parameter to implement . In the face of concurrent changes , The iterator will soon fail completely , Instead of risking arbitrary uncertainty at some uncertain time in the future .
Because the underlying implementation is an array , So it's size、isEmpty、get、set The time complexity of O (1) Class .
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable Copy code Inheritance relationship and ArrayList As like as two peas .
protected Object[] elementData;
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
// ...
Copy code The underlying implementation is also similar to ArrayList identical .
Expansion is also logical add Start , One difference here is ,add added synchronized Keyword modification ：
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
// and ArrayList Same logic
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy code The underlying implementations are basically the same , The only difference is Vector It's thread safe .
Vector There is a subclass Stack, That is, stack structure type . Represents the last in first out stack of objects .Stack Inherited from Vector , The structure of the stack is considered as an expansion of the five containers . Including common pop and push operation 、 And how to view the top element of the stack 、 The method of checking whether the stack is empty and searching for an element from the top of the stack , And get the depth of the element in the stack .
Deque The interface and its implementation provide a more complete set of LIFO Stack operation capability , Use should be a priority Deque And its implementation . for example ：
Deque<Integer> stack = new ArrayDeque<Integer>(); Copy code
Based on two-way linked list , Only sequential access , But you can quickly insert and delete elements in the middle of the list . More Than This ,LinkedList It can also be used as a stack 、 Queues and two-way queues .
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable Copy code transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}
Copy code adopt first and last Represents the head node in both directions of the bidirectional linked list .Node The data structure is ：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Copy code Add operation ：
public boolean add(E e) {
linkLast(e);
return true;
}
Copy code Real add operation ：
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
Copy code Delete operation ：
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x); // x Of next and prev Set as null
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Copy code Search operation ：
Node<E> node(int index) {
// assert isElementIndex(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;
return x;
}
}
Copy code The implementation of the lookup operation is optimized ,size >> 1 Value size / 2 , If it is on the left side of the linked list , Then look for , Otherwise, look forward from the tail .
It is equivalent to the time complexity of linked list structure operation , O(n) .
because LinkedList Realized Deque, So it can be seen as a two-way queue , It can also be used as a stack structure .（Java It has been declared that... Is not recommended Stack class ）. Stack or queue , Now the first choice is ArrayDeque, It has a ratio of LinkedList ( When used as a stack or queue ) Better performance .
On the other hand , Its operation method is not synchronized , So it's not thread safe .
LinkedList Capability based on bidirectional queue , It provides some methods to obtain the head node and tail node , These methods are followed in Queue Explain in detail in the interface . Here's the basics ：
boolean offer(E e); // Insert the element at the end of the queue , Return the insertion result
E peek(); // Retrieve queue header elements without deleting , If the queue is empty , return null
void push(E e); // Insert the element into the queue header Equivalent to addFirst
E pop(); // Delete the first element of the queue , Equivalent to removeFirst
Copy code 版权声明：本文为[Automatic bug maker]所创，转载请带上原文链接，感谢。 https://javamana.com/2022/134/202205141446337594.html