List

The List collection has the following characteristics:The orderly(The order of storage is the same as the order of extraction),Repeatable.Several important implementations:

ArrayList

The underlying implementation of ArrayList is an array that can be automatically expanded. Question:

  1. Expansion mechanism
    1. When will the capacity be expanded? By how much? Expansion mechanism? How does it work? Initial capacity?
  2. Common methods and implementation?

Expansion mechanism

Initial capacity?

When created, if no capacity is passed in, the default capacity is an empty array with capacity 0. If there is an passed capacity or array, the passed capacity is used.

// Default empty array, 0 capacity
public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// Incoming capacity
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); }}If the element type is not Object, the element type is converted to Object.
// From this point of view, ArrayList supports variable element types
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if((size = elementData.length) ! =0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

When will the capacity be expanded?

When an element is added, the system checks its capacity. If the capacity is insufficient, the system expands the capacity.

public boolean add(E e) {
    // Check and expand the capacity
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
Copy the code

How much will the expansion be and how will it be implemented?

Capacity Expansion process:

  1. Calculate the minimum capacity requiredminCapacity
  2. If the actual capacity of the current array is less thanminCapacity, expand the capacity
  3. Expansion rule: Increase the array length1.5 times, if greater thanminCapacity, the value is taken, otherwise the value is takenminCapacity
  4. Expansion implementation: copy array, callArrays.copyOf()Method by calling system methodsSystem.arraycopy()The implementation.

Calculate the minimum capacity required:

  1. If it is the first time an element is added to the collection and the collection is empty, the default size is usedDEFAULT_CAPACITY = 10; Otherwise, take the number of added elements.
  2. If the current set is not empty, take the capacity of the added set,The current size + 1
// Calculate the minimum size required for the array of elements
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

// If the actual capacity of the current array is smaller than the minimum required capacity, expand the array
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 code

Capacity Expansion process:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // bit operation, shift one bit to the right, expand 1.5 times
    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 the code

Common methods and implementation?

  1. modCount: This field records the number of structural changes to the list.

This field is used by the iterator and list iterator implementation returned by the iterator and listIterator methods.

This field is used by iterators and list iterators returned by the iterator and listIterator methods

If the value of this field changes unexpectedly, the iterator (or list iterator) will throw a ConcurrentModificationException in response to the next, remove, previous, set or add operations.

If this field is the value of the unexpected changes, the iterator (or list iterator) will throw ConcurrentModificationException in response to the next add, delete, a, set, or operation.

This provides fail-fast behavior, rather than non-deterministic behavior in the face of concurrent modification during iteration. This provides quick failure behavior rather than uncertain behavior in the face of concurrent changes during iterations.

final void checkForComodification(a) {
    if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
}
Copy the code
  1. Add elements
  • add(E e)Check capacity before adding elements
  • add(int index, E element)First check subscript, then check capacity, then add (System.arraycopy()Copy implementation)
// Expand the capacity before adding it
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// Check whether execute subscript exists, then check the capacity, then add (directly copy array)
public void add(int index, E element) {
    rangeCheckForAdd(index);
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;
    size++;
}
Copy the code
  1. Replace the elementset(int index, E element), first check the subscript, then directly replace
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
Copy the code
  1. Access to elementsget(int index)
  • First check if the subscript exists, then get the element
  • Forces an element to the specified type
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}

E elementData(int index) {
    return (E) elementData[index];
}

Copy the code
  1. Remove elements
  • remove(int index)First check the subscript, then move all elements of the array after the specified subscript forward one bit, and then change the value of the last bitnull. This operation clears only the values of the specified subscript and does not change the current capacity of the collection.
  • remove(Object o), convenient array, find the value of the first element is equal to remove. Again, this operation does not change the current capacity of the collection.
public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,  numMoved);
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true; }}else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; }}return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

Copy the code
  1. Empty the collectionclear(), sets all elements in the array tonull.
public void clear(a) {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}
Copy the code
  1. Streamline collectiontrimToSize()To reduce the capacity of the collection array to the current capacity

Trims the capacity of this ArrayList instance to be the list’s current size. An application can use this operation to minimize the storage of an ArrayList instance. Trim the capacity of this ArrayList instance to the current size of the list. Applications can use this action to minimize the storage of an ArrayList instance.

public void trimToSize(a) {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the code

List collection as simple as that

Vector

Question:

  1. What is the difference between Vector and Arraylist?

The internal implementation of Vector is basically the same as ArrayList. Vector is thread-safe. ArrayList is not thread-safe. Synchronized 2 is added to the method, ArrayList is extended 0.5 times when the underlying array is not enough, and Vector is extended 1 times.

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

public boolean remove(Object o) {
    return removeElement(o);
}

public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

// Implement capacity expansion
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0)? capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Copy the code

Reference: Difference between Arraylist and Vector

LinkedList

Because LinkedList is implemented as a two-way LinkedList, it is a chained storage structure, so there is no capacity limit. Question:

  1. What is the internal implementation like?
  2. What are the pros and cons of ArrayList?

Common methods and implementation

  1. The constructor
public LinkedList(a) {}public LinkedList(Collection<? extends E> c) {
    this(a); addAll(c); }Copy the code
  1. Add elements

When adding an element, if no subscript is specified, the element is added at the end. If a subscript is specified, add at the specified subscript. Element addition is achieved by changing the front and back Pointers of elements.

public boolean add(E e) {
    linkLast(e);
    return true;
}

// Add the element at the end
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++;
}

// This property records the last element
transient Node<E> last;

// Add elements at the specified location
public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

// Add before the specified element
void linkBefore(E e, Node<E> succ) {
    // assert succ ! = null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
Copy the code
  1. Access to elements

Retrieves the element with the specified subscript by traversing. If the subscript value is less than half the length, it traverses from front to back, otherwise it traverses from back to front.

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// By convenience, get the element with the specified subscript
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;
        returnx; }}Copy the code
  1. Remove elements

The basic idea is to change the Pointers to the nodes before and after the element, remove the element from the list, and then empty the element for recycling.

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

// Removes the specified element from the list
unlink(Node<E> x) {
    // assert x ! = null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}
Copy the code

What are the pros and cons of ArrayList?

  • The underlying layer of an ArrayList is an array, and the underlying layer of a LinkedList is a bidirectional list.
  • Arraylists can index the corresponding element by corner position (random access), whereas linkedLists need to iterate back to retrieve the element. So arrayLists are generally faster than LinkedLists
  • To add and delete elements, ArrayList requires array copy; LinkedList only needs to modify the pointer. As a result, linkedLists are generally added and deleted faster than arrayLists.

Arraylists are not necessarily slower to add or delete than linkedLists.

  • If additions and deletions are done at the end (remove() and add() are called each time), the ArrayList does not need to move and copy the array to operate. If the data volume is in the millions, it is faster than LinkedList. (I’ve tested it)
  • If the location of the delete operation is in the middle. Since the consumption of LinkedList is mainly traversal, the consumption of ArrayList is mainly movement and copy(the underlying call is arrayCopy (), which is a native method).
    • LinkedList traversal is slower than ArrayList copy movement
    • If the data is in the millions, ArrayList is still faster. (I’ve tested it)

ArrayList expands by copying arrays, so arrays are copied even when elements are always added to the end, but much less often.

Queue operations

Because LinkedList implements the Deque interface, LinkedList can also be used as a queue. What a versatile little hotshot!!

Stack

Not recommended

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, The Deque interface and its implementation provide a more complete and consistent set of LIFO stack operations and should be used in preference to this class

Inherit Vector with several new interfaces

public class Stack<E> extends Vector<E>{... }// addElement to top of stack, same as addElement(item)
public E push(E item);
// Returns and removes the top element of the real stack
public synchronized E pop(a);
// Return the top element of the stack without removing it
public synchronized E peek(a);
// Check whether the stack is empty
public boolean empty(a);
// Returns the position of the object in the stack
public synchronized int search(Object o);

Copy the code

conclusion

  • ArrayList
    • The underlying data structure is an array. Thread insecurity
    • The initial capacity is 10, and the expansion check is performed when adding elements, and the expansion is 0.5 times.
    • When adding or deleting elements, you need to copy the array and call local methods
  • LinkedList
    • The underlying data structure is a linked list. Threads are not safe.
  • Vector
    • The underlying data structure is an array. Thread safety. But seldom used
      • When all methods are synchronous, there is a performance penalty.
      • Each time the capacity is doubled, there is memory loss
  • Stack: a subclass of Vector that implements a standard StackLast in, first outThe stack
    • Java has officially stated that the _Stack_ class is not recommended

Query uses ArrayList, add and delete uses LinkedList. If thread synchronization is required, useCollections.synchronizedList()Method instead.