Java collection framework [2] list system

Automatic bug maker 2022-05-14 15:00:05 阅读数:902

javacollectionframeworklist

List Interface

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 :

  • Batch operation adds sorting , explain List Is ordered .
  • Location access operations , explain List It can be used for location indexing .
  • The container supports sub List , It can be done to List Intercept .

Realization

List The implementation of the interface includes :VectorArrayListLinkedList .

ArrayList

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, .

Inheritance relationships

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable  Copy code 

ArrayList Inherited from AbstractList , And implemented ListRandomAccess. 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 .

Underlying implementation

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 .

Expansion logic

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 

Fail-Fast Mechanism

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 .

Time complexity

Because the underlying implementation is an array , So it's sizeisEmptygetset The time complexity of O (1) Class .

Vector

Inheritance relationships

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 .

Underlying implementation

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 logic

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 

And ArrayList The difference between

The underlying implementations are basically the same , The only difference is Vector It's thread safe .

Implementation of stack structure

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 

LinkedList

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 .

Inheritance relationships

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable  Copy code 
  • AbstractSequentialList: This is a List Skeleton implementation of the interface , Data processing logic is based on Sequential access Data structure of ( Such as the list ) To achieve .
  • Deque: The bidirectional queue , Support the insertion and removal of elements from both ends .
  • Cloneable: Object replication .
  • Serializable: Serialization capability .

Underlying implementation

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 .

Time complexity

It is equivalent to the time complexity of linked list structure operation , O(n) .

Other abilities

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 

summary

  1. Vector and ArrayList The implementation of is basically the same , The underlying data structures are arrays , The big difference Vector It's thread safe .
  2. LinkedList Not thread safe , Its underlying implementation is a two-way linked list .
  3. LinkedList It can not only be used as a two-way queue , It can also be used as a stack .
版权声明:本文为[Automatic bug maker]所创,转载请带上原文链接,感谢。 https://javamana.com/2022/134/202205141446337594.html