Collections framework

  1. The collection implements dynamic saving
  2. Collections provide a convenient way to operate

Collection: a single column

List single-column set Ordered set repeatable set

ArrayList

  1. An ArrayList can add NULL values, and multiple values can be added

  2. An ArrayList is stored by an array implementation

  3. ArrayList is thread-unsafe

Source:

  1. An elementData of type Object[] is maintained in ArrayList

  2. Capacity expansion mechanism:

    1. When using the no-parameter constructor, the initial length is 0. After inserting data, the elementData length is expanded to 10. When expanding again, it is expanded to 1.5 times the original length

    2. With the parameter constructor, the length of elementData is the initial specified size, and is expanded to 1.5 times the length of elementData if needed

  3. Reasons for expansion mechanism:

    
	// Take the expansion of an ArrayList without parameters as an example


	// After calling the add method, the method ensureCapacityInternal is called
	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
	// Call calculateCapacity first and then ensureExplicitCapacity
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
	// In the method, calculateCapacity is judged whether the initialized elementData is empty or not. If it is empty, the size is returned as DEFAULT_CAPACITY, the maximum value in minCapacity, and minCapacity = 0. The default value of DEFAULT_CAPACITY is 10
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
	// Check whether the minimum required space is larger than the current size of the space. If so, expand the space
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
	OldCapacity = 0; oldCapacity = 0; oldCapacity = 0; NewCapacity =0 +0/2=0, minCapacity = 10; If is used to determine that newCapacity = 10, that is, if the length is not initialized, the length will be expanded to 10 during the first expansion.
	// Note: oldCapacity >> 1 is oldCapacity/2
	// newCapacity = oldCapacity + oldCapacity/2, that is, capacity expansion by 1.5 times
    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 the code

LinkedList

  1. The underlying data structures are bidirectional linked lists and double-endian queues

  2. Any element can be added, can be repeated, can be null

  3. Threads are not safe. They are not synchronized or mutually exclusive

Source:

  1. LinkedList maintains size (number of elements) first (pointing to the first node) last (pointing to the last node)

  2. Each Node (Node object) maintains prev (pointing to the previous Node) next (pointing to the next Node) item (data)

  3. When adding or deleting data, it is realized by changing the pointing relationship between the nodes before and after the node. It does not involve the array and does not expand, which is relatively more efficient

// The add method calls linkLast
void linkLast(E e) {
    	// Create a Node object l where l=last is null
        final Node<E> l = last;
    	Prev: null item: e next: null
        final Node<E> newNode = new Node<>(l, e, null);
    	// Last points to the newNode node
        last = newNode;
    	// this is true
        if (l == null)
            // First points to newNode
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
// At this point, the data has been inserted into the overall structure
// List: first points to newNode, last points to newNode, size=1
// Node: prev: null item: e next: null
Copy the code

To be continued