Java common collection source analysis I

@ Version: JDK 1.8

@ IDE: IntellJ IDEA 2021.1

@Date: 2021/8/7

@Author: Hypocrite30

A collection,

  • Collections fall into two main categories:Collection & Map

ⅰ. Collection interface

  • Some implementation classes are ordered “List”, some are unordered “Set”
  • Some can duplicate elements, some can’t
  • Collection interface does not directly implement the subclass, through the subinterface “Set” “List” implementation

ⅱ. Iterator interface

  • becauseCollection<E> extends Iterable<E>, so all subclasses can pass the fetchIteratorTraverse the collection

Common methods:

boolean hashNext() Returns: true if the iteration has more elements
E next() Returns: the next element in the iteration
void remove() Removes from the underlying collection the last element returned by this iterator

📌 : Iterator.hasnext () must be called before iterator.next() is called to see if there is an element behind it. If not, calling next() throws a NoSuchElementException on the last element

ⅲ. List interface

  • Elements and orderly
  • repeatable
  • Support the index
  • Each element has an integer number that records its position in the container and can be accessed

Second, the ArrayList

  • ArrayListCan store any data, includingnull
  • ArrayListBasically equivalent toVectorThe difference is that the former isThread insecurity“High execution efficiency” of
  • ArrayListThe internal storage data structure isAn array of

Ⅰ, Field

/** * Default initialization capacity */
private static final int DEFAULT_CAPACITY = 10;

/** * The empty array has a capacity of 0, with arguments to construct the default storage data structure */
private static final Object[] EMPTY_ELEMENTDATA = {};

/** * The empty array has a capacity of 0, the default storage data structure used when constructing without arguments */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** * The array used by the underlying ArrayList to access data is non-private, to simplify nested class access * transient does not allow serialization */
transient Object[] elementData;

/** * Actual ArrayList collection size */
private int size;

/** * Maximum capacity that can be allocated */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Copy the code

📌 Several notes:

  • The array default initialization capacity is 10
  • Two empty arrays are created beforehand and assigned directly to the storage array during construction
  • The actual array that stores data isObject[] elementDataAnd has beentransientModifier, so serialization does not write it to the stream, but such deserialization loses data and requires analysiswriteObject(ObjectOutputStream s) 和 readObject(ObjectInputStream s)Get how to serialize (#ArrayList serialization and deserialization)
  • Pay attention to theMAX_ARRAY_SIZEThe maximum length of the array isInteger.MAX_VALUE - 8, [description below](#MAX_ARRAY_SIZE)

ArrayList serialization and deserialization

  • private void writeObject(java.io.ObjectOutputStream s)serialization
    • Serialization writes to the stream:size & Element element value
    • elementData[]We’re just going to cache the array, and we’re going to reserve capacity for it, so we’re going to serialize only the elements that we need in the array,Save space and time.
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Expected number of changes, used to determine problems with concurrent changes
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write ArrayList size
    s.writeInt(size);

    // Write each element value
    for (int i = 0; i < size; i++) {
        s.writeObject(elementData[i]);
    }
	// Determine serialization concurrency issues
    if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}Copy the code
  • private void readObject(java.io.ObjectInputStream s)deserialization
    • Because the construction of thisArrayListThere are already templates and data “serialized save size&Element” so use itEMPTY_ELEMENTDATAAs an empty array instead ofDEFAULTCAPACITY_EMPTY_ELEMENTDATA
    • According to thesizeRead in element data
    • Into the storage array in the correct order of serialization
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // EMPTY_ELEMENTDATA is the empty array in the field used for parameter constructs
    elementData = EMPTY_ELEMENTDATA;

    // Read data according to size
    s.defaultReadObject();

    // Read the capacity
    s.readInt(); // ignored

    if (size > 0) {
        // Like clone(), arrays are allocated based on size rather than capacity
        int capacity = calculateCapacity(elementData, size);
        SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read all elements in the correct order
        for (int i = 0; i < size; i++) { a[i] = s.readObject(); }}}Copy the code

MAX_ARRAY_SIZE Value description

/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Copy the code

Some virtual machines reserve some field space. If Integer.MAX_VALUE is used up, it may be OOM.

Part of the explanation on StackOverflow refers to “the composition of object headers in the memory model” 1

Hence the anatomy of Java array objects 2

IBM says, “The difference between an array object and a Java object is that an array object has an additional metadata that represents the size of the array.”

Profile Java object 3

Different JVM vendors have different designs for the amount of metadata, but typically include:

  • Class: A pointer to Class information, that is, a type pointer. Points to class meta information in the method area.
  • Flags: Collection of Flags that describe the state of an object, including hashCode and shape.
  • Lock: synchronization information of an object.

Java array objects have an additional Size, the Size of the array.

“Object header size cannot exceed 8 bytes”

The Mark Word “hash value, GC generation age, lock status flag, thread held lock, bias thread ID, bias timestamp” accounted for 4 bytes in 32-bit schema and 8 bytes in 64-bit schema. The type pointer Klass Pointer has a word length on a 32 byte schema, but can still be 4 bytes if the heap address can be encoded in 4 bytes.

📌 : So to be safe against OOM, the maximum array length is set to integer.max_value – 8

Ⅱ, Constructor

No arguments structure

/** * construct an empty list with an initial capacity of 10 */
public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code
  • The initial capacity here is 10, in the fieldDEFAULT_CAPACITY = 10embodied

Have the cords structure

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 the code
  • Constructs an empty list with the specified initial capacity
  • If the input parameter is negative, an exception is thrown
public ArrayList(Collection<? extends E> c) {
    // An array containing all the elements of this list in the correct order
    Object[] a = c.toArray();
    // Update the value of size. If it is an empty array, use the default empty array
    if((size = a.length) ! =0) {
        // Check if c is an ArrayList
        if (c.getClass() == ArrayList.class) {
            elementData = a;
        } else { // Make a copy of Object[]elementData = Arrays.copyOf(a, size, Object[].class); }}else {
        // replace with empty array.elementData = EMPTY_ELEMENTDATA; }}Copy the code
  • Constructs the list containing the specified collection elements in the order returned by the collection iterator. That is, passing in a collection class
  • If null is passed, it is thrownNullPointerException

Ⅲ, Method,

Add element add(E E)

  • Add element e
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
Copy the code

  • EnsureCapacityInternal (int minCapacity) Checks for capacity expansion to ensure that the capacity is at least size + 1. During this process, modCount is increased because capacity expansion is a modification operation.

  • Once you have enough capacity, store the value into the array “elementData” at the same time as size ++

Add (int index, E element)

  • Inserts an element at the specified index position, and all subsequent elements move to the right
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
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code
  • Check the validity of index first
  • Check whether the capacity is expanded.Ensure capacityAt least,To achievesize + 1, during which modCount increases
  • The element of [index, size] is moved one unit back
  • Insert the element and update the size value

Delete the remove (int index)

  • Deletes the element subscript index
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; Easy / / GC

    return oldValue;
}
Copy the code
// Implement the method used above
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
    return (E) elementData[index];
}
Copy the code
  • Check index validity and modify counter modCount ++
  • Gets the old element as the method return value
  • Calculate the number of subsequent elements to be restored assize - index - 1
  • All subsequent elements move forward one unit, overwriting the old element
  • The last position of the array is empty for GC before the delete operation

Delete the remove (Object o)

  • Removes the specified element o
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;
}
Copy the code
// remove(int index) without return value
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; Easy / / GC
}
Copy the code
  • Simple for-loop to find values, and also find stored null values “non-expanded null” condition isindex < size

Remove the clear ()

  • Clears all element values
public void clear(a) {
    modCount++;
    Easy / / GC
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}
Copy the code
  • Modify counter increment; Element is empty for GC; Finally modify the size

Alter set(int index, E element)

  • Change the element value at the index position to Element
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
Copy the code
  • Check the validity of index first
  • Get the old value; Modify the
  • Returns the old value

Look for the get (int index)

  • Find and return the value of the index position
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}
Copy the code

Expansion mechanism

  • Make sure to store the array’s capacityAt least,To achieveminCapacityThe size of the
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
Copy the code
  • To calculateexpectedArray capacity
    • elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATACheck whether the current array isNo arguments structurecreatedCapacity of 0An array of
    • If so, the calculated array capacity issize + 1, i.e.,0 + 1, because the default empty array size == 0
    • [size + 1](# add element (E E))
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
Copy the code

📌Q: The if statement always returns minCapacity “because positive minCapacity > DEFAULT_CAPACITY (0)”, and minCapacity is also returned outside the if statement. What is the significance of design?

A: If minCapacity is negative, then DEFAULT_CAPACITY AKA 10 will be returned. If minCapacity is negative, then DEFAULT_CAPACITY AKA 10 is returned.

Q: Why do I need to determine if “elementData” is the default empty array DEFAULTCAPACITY_EMPTY_ELEMENTDATA

A: Grow () creates a new array to override elementData at each expansion. [size + 1](# add element add(E E))))

  • Make sure that the capacity is clear and do the last confirmation before expansion
    • Modify the counter increment
    • Determines whether the expected array size you just calculated is greater than the current array size
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
Copy the code

📌 Overflow-conscious (a < b, a-b < 0, a-b < 0, a-b < 0)

  • Scale operation
    • Obtain the old capacity, according to 1.5 times the size of the old capacity as the new capacity, using bit operation to improve efficiency.
    • After two special judgments, the capacity is expandedArrays.copyOfExpand, this will createThe new arrayOverwrite the original array
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // AKA 1.5x capacity expansion
    // Only the first time will true change the new capacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // If the new capacity is too large, it is treated as large capacity
    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

📌Q: newCapacity < minCapacity the newCapacity is smaller than the predicted capacity. The predicted capacity is size + 1, that is, all data length + 1. The new capacity is 1.5 times larger than the original capacity, which is definitely larger than minCapacity.

A: When creating an empty array with no arguments, oldCapacity is 0, and is still 0 when multiplied by 1.5. In this case, the newCapacity is naturally smaller than the predicted capacity. Update newCapacity (0) to the predicted capacity. After that, the update operation will not be performed, because the capacity must be larger than the predicted capacity “(x1.5) > (+ 1)”.

  • Large capacity processing mode
    • Int accumulates to a negative value, indicating that the maximum value of int storage has been exceeded
    • Predicted capacity > maximum allowed capacity, let the new capacity be int maximum, otherwiseMAX_ARRAY_SIZE, i.e.,Integer.MAX_VALUE - 8, equivalent to giving a safe value, [not OOM](#MAX_ARRAY_SIZE numerical description).
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
Copy the code
  • Arrays tool class capacity expansion
    • Local methods will eventually be calledarraycopy()super-popular
    • As you can see, the returnedcopyArrays are all new, so expanding the storage arrays will make them different objects
public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);
Copy the code

Application of A < B and A – b < 0

Q: Many of the conditions mentioned above are judged in the form of A-b < 0 instead of direct comparison. What are the advantages of this design?

In mathematics, these two inequalities are completely equivalent. But in the computer, need to consider the storage problem, possible variables, a | b

Overflow situation.

🌰 Demo 4:

int a = Integer.MAX_VALUE;
int b = Integer.MIN_VALUE;
if (a < b) System.out.println("a < b");
if (a - b < 0) System.out.println("a - b < 0");
Copy the code

Result: A – B < 0

  • Normally, a is definitely less than B
  • But it turns outa - b < 0Is true, i.e. a < b

Analysis: A-b exceeds the maximum range of int storage, so it overflows and becomes negative

ArrayList

// overflow-conscious code
if (minCapacity - elementData.length > 0)
    grow(minCapacity);
Copy the code

Officials also warned of spillovers

  • Use the form A < b

    • ifminCapacityIf the overflow is too large, the overflow becomes negative. In this case, the capacity will not be expanded. However, there is a need for expansion in this case

  • Use the form A – b < 0

    • ifminCapacityIf the overflow is too large, the overflow will be negative, and subtracting a positive number will return to a positive number, and the expansion will be smoothly entered

grow() :

// 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);
Copy the code

There are also overflow warnings

  • usea < bIn the form of
    • newCapacityIf too large overflow is negative after 1.5 times expansion, it will be less thanminCapacityAnd will updatenewCapacity = minCapacity;
    • The next condition,newCapacityNegative is going to be less thanMAX_ARRAY_SIZE, so there will be no super-capacity processing, then there will be problems
  • usea - b < 0In the form of
    • The first condition is that the overflow is negativenewCapacityMinus a positive numberminCapacityThe result is greater than 0 and is not updatednewCapacity, that is, only the first expansion “empty array” will be updated
    • The second condition is that, again, super-capacity processing is performed, which is logical.

Third, the Vector

  • Because the method is addedsynchronizedIs a method-level lock, so it is thread-safe.
  • Most of the logic and design work withArrayListThe same

Ⅰ, Field

// Store arrays
protected Object[] elementData;
// The number of real elements
protected int elementCount;
// Expansion factor, see expansion function for details
protected int capacityIncrement;
Copy the code

Ⅱ, Constructor

No arguments structure

  • The default array length for a no-parameter construct is 10
public Vector(a) {
    this(10);
}
Copy the code

Have the cords structure

  • The default capacity expansion factor is 0, that is, the capacity expansion is twice
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}
Copy the code
  • Custom array length & expansion factor
public Vector(int initialCapacity, int capacityIncrement) {
    super(a);if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
}
Copy the code
  • Class according to the incoming collection
public Vector(Collection<? extends E> c) {
    Object[] a = c.toArray();
    elementCount = a.length;
    if (c.getClass() == ArrayList.class) {
        elementData = a;
    } else{ elementData = Arrays.copyOf(a, elementCount, Object[].class); }}Copy the code

Ⅲ, Method,

  • Most methods are similar toArrayListThe same

Expansion mechanism

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
Copy the code
  • Check before capacity expansion
private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
Copy the code
  • 📌 capacity
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0)? capacityIncrement : oldCapacity);// Capacity expansion mechanism
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code

NewCapacity is the old capacity plus a value. The ternary operator determines the capacity expansion factor. If the default value is 0 or less than 0, the capacity is doubled.

Otherwise, expand capacity by 1 + capacityIncrement

Four, LinkedList

  • The data structure used is a bidirectional linked list
  • inheritedList 和 Deque, so it can be used as a list set and a double-endian queue
  • Non-thread-safe; The way to make it thread-safe is to callCollectionsThe utility classsynchronizedList(List<T> list)Method to a thread-safe collection
List list = Collections.synchronizedList(newLinkedList(...) );Copy the code

Ⅰ, Field

// Number of nodes
transient int size = 0;
// A pointer to the first node.
transient Node<E> first;
// point to the end node
transient Node<E> last;
Copy the code

According to bidirectional linked list storage characteristics

Invariants at run:

(first == null && last == null) || (first.prev == null&& first.item ! =null)
(first == null && last == null) || (last.next == null&& last.item ! =null)
Copy the code

Static inner class

! [](C: Users\10270\Desktop\Java common set source analysis i. assets\1628515716530-screenshot.png)

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 the code
  • This shows that the underlying data structure is a bidirectional linked list

Ⅱ, Constructor

No arguments structure

// Constructs an empty list.
public LinkedList(a) {}Copy the code

Have the cords structure

  • Adds the incoming parameter set element to a new oneLinkedListA collection of
public LinkedList(Collection<? extends E> c) {
    this(a); addAll(c); }Copy the code

Ⅲ, Method,

Add the add (E, E)

  • # linkLast(E E) # linkLast(E E)
public boolean add(E e) {
    linkLast(e);
    return true;
}
Copy the code

Add (int index, E element)

  • Adds an element to the specified subscript position
    • Check subscript validity
    • LinkLast (E E)) or linkBefore(E E, Node succ)
    • “Before inserting a non-empty node” uses [node(int index)](# retrieve the index position of the node in the linked list node(int index)) to calculate the index position of the node
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
Copy the code
private void checkPositionIndex(int index) {
    if(! isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Index ∈ [0, size]
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}
Copy the code

Add addFirst (E, E)

  • LinkFirst (E E)
public void addFirst(E e) {
    linkFirst(e);
}
Copy the code

Add addLast (E, E)

  • LinkLast (E E)
public void addLast(E e) {
    linkLast(e);
}
Copy the code

Delete the remove (Object o)

  • Deletes the first match of the specified element

    • ifThe element to be deleted isnull
      • Look at the first one from the beginningnullUnlink (Node x) unlink(Node x)
    • elseThe element to be deleted is not empty

      • Unlink (Node x) unlink(Node x)

public boolean remove(Object o) {
    if (o == null) {
        for(Node<E> x = first; x ! =null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                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 the code

LinkLast (E E)

  • lPointer to the end of the list for markingThe original list
  • According to theNode(Node<E> prev, E element, Node<E> next)Create value fore, precursor forl 即 lastAnd for the followingnull, so the construction conforms toEnd nodeThe characteristics of
  • The list tail pointer moves to the new list tail
  • ifThe end of the original list isnull
    • Note If the linked list is empty, the first node is inserted, so the head pointer also points to the new node
  • elseThe original linked list is notnull
    • Note “The list is not empty”, insert the tail to the list
  • size & modCountSince the increase
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 the code

LinkBefore (E E, Node succ)

  • assertionsindexThe node is not empty
  • To obtainindexNode precursorpred
  • Create a node. The value ise, precursor forpredAnd for the followingsucc
  • The successor connects to the new node
  • ifPrecursor is empty
    • The insert position is in the head of the list, and the head pointer points to the new node
  • elseSubsequent to an empty
    • Note Insert position is in the middle, and the precursor points to the new node
  • size & modCountSince the increase
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

Insert element into linkFirst(E E)

  • Get the head node
  • Create a node. The value ise, precursor fornullAnd for the followingf, the old header
  • The head pointer moves to the new node
  • ifThe old head node is empty
    • Note If the linked list is empty, the last pointer points to a new node
  • elseThe old head node is not empty
    • Note Linked list is not empty, connecting the new node and the old header
  • size & modCountSince the increase
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
Copy the code

Deleting a Node Unlink (Node X)

  • The assertion node is not empty
  • Get the nodeelementPrecursor,prevAnd the subsequentnext
  • ifPrecursor is empty
    • Note If this node is the head node, the head pointer directly points to the successor
  • elsePrecursor is not empty
    • Note “This node is not the head node”, the precursor points to the successor, and then breaks “X points to the precursor”.
  • Bidirectional linked list, same thing going in the other direction
  • sizeSince the reduction,modCountIncrement, element is empty, return the deleted node
E 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

Retrieve the subscript position of the node in the linked list node(int index)

  • assertionsThe index ∈ [0, size)
  • ifThe subscript is on the left half
    • Retrieve from the beginning to the middle
  • elseThe subscript is on the right half
    • Retrieve from back to center

📌 dichotomy idea, make good use of bidirectional linked lists, while the head and tail nodes are fixed.

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

The differences between the four methods of getting elements

getFirst() & getLast() & peekFirst() & peekLast()

public E peekFirst(a) {
    final Node<E> f = first;
    return (f == null)?null : f.item;
}
public E getFirst(a) {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
Copy the code
  • Obviously,peekA method of type is returned in an empty linked listnull.getThe type,An exception is thrown NoSuchElementException

LinkedList as a double – ended queue and stack detail

Because the LinkedList also implements a Deque interface, it can be used as a two-ended queue, and of course as a stack “one open, one closed”.

  • The stack
public class Solution {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        stack.push(1);
        stack.push(2);
        stack.push(3); System.out.println(stack); }}Copy the code

[3, 2, 1)

  • The queue
public class Solution {
    public static void main(String[] args) {
        Deque<Integer> queue = new ArrayDeque<Integer>();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3); System.out.println(queue); }}Copy the code

[1, 2, 3]

Since can also be a queue and stack, cause thinking, as peek () to obtain “stack” | “team” element, then guess queue first opening and the stack is the same direction.

  • To viewDeque 的 peek()The official comments
/**
 * Retrieves, but does not remove, the head of the queue represented by
 * this deque (in other words, the first element of this deque), or
 * returns {@code null} if this deque is empty.
 *
 * <p>This method is equivalent to {@link #peekFirst()}.
 *
 * @return the head of the queue represented by this deque, or
 *         {@code null} if this deque is empty
 */
E peek(a);
Copy the code

Peek () returns the deque queue header, or null if the two-endian queue is empty

  • To viewLinkedListImplementation of thepeek()
public E peek(a) {
    final Node<E> f = first;
    return (f == null)?null : f.item;
}
Copy the code

Gets the left list head

  • To viewArrayDequeImplementation of thepeek()
public E peek(a) {
    return peekFirst();
}
Copy the code

Get queue head

📌 Conclusion: The left side of the official definition (First) is the head of the stack, the head of the queue. Thus a method can be implemented to achieve the same peek effect.

🔗Reference:

  1. Why the maximum array size of ArrayList is Integer.MAX_VALUE – 8?↩
  2. Anatomy of a Java array object↩
  3. Anatomy of a Java object↩
  4. [Difference between if (a – b < 0) and if (a < b)]↩