❤ Write in front
❤ Blog home page: Hard working Naruto
❤ Series column: JavaSE super detailed summary 😋
❤ Welcome, friends, praise 👍 follow 🔎 Collection 🍔 Learning together!
❤ If there are mistakes, please correct them! 🌹

about [Chapter 10 Java collection] several brain maps take you into the brainstorming of Java collection 🔥 Extended analysis of

1, Basic knowledge

1. Features: ordered, allowing repeated elements. The order can be natural or the order in which objects are added to the set
2. Traversal:
   ① Iterator iterator mode
   ② Enhanced for loop
   ③ Ordinary cycle
3. Common interface List method
   
4. The implementation classes of List interface in JDK API are ArrayList, LinkedList and Vector

2, ArrayList

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

ArrayList inherits AbstractList and implements list, randomaccess, Cloneable and serializable interfaces
ArrayList is a variable size array

🔥 non-parameter constructor

By default, the array is an empty array

//non-parameter constructor 
public ArrayList() {
    super();//Because it inherits AbstractList, the constructor of AbstractList is called
    //Here is to set the array as an empty array object
    this.elementData = EMPTY_ELEMENTDATA;
}

🔥 Source code analysis

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    //The default array size is 10
    private static final int DEFAULT_CAPACITY = 10;
    //Empty array object
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //The bottom layer of ArrayList is implemented based on this array
    private transient Object[] elementData;
    //Size of actual data in ArrayList
    private int size;

    //Constructor with initialization capacity size
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        //Initializes the array to the specified capacity size
        this.elementData = new Object[initialCapacity];
    }

    //non-parameter constructor 
    public ArrayList() {
        super();
        //Here is to set the array as an empty array object
        this.elementData = EMPTY_ELEMENTDATA;
    }

    //Create an ArrayList containing the Collection
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

    //Set the current capacity value to the actual number of elements
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

    //Ensure ArrayList capacity, if    
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != EMPTY_ELEMENTDATA)
                // any size if real element table
                ? 0
                // larger than default for empty table. It's already supposed to be
                // at default size.
                  : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    private void ensureCapacityInternal(int minCapacity) {
        //During initialization, elementData is empty array object EMPTY_ELEMENTDATA, so the value of minCapacity will be set
        if (elementData == EMPTY_ELEMENTDATA) {
            //Set minCapacity value and compare minCapacity with default capacity (DEFAULT_CAPACITY=10)
            //Assign the maximum value to minCapacity
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //Determine clear capacity size
        ensureExplicitCapacity(minCapacity);
    }

    //Determine clear capacity size
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

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

    //Maximum array size = integer MAX_ VALUE - 8
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //Capacity expansion method
    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);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

3, LinkedList

A two-way linked list does not declare an array inside, but defines the first and last of Node types, which are used to record the first and last elements

1. definition

public class LinkedList<E> extends AbstractSequentialList<E> 
		implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList inherits AbstractSequentialList and implements list, deque, Cloneable and serializable interfaces
The underlying layer of LinkedList is based on linked list

1. LnkedList defines a private static internal class Node
   Node has three member variables, item, next and prev Literally, it means itself, the next element, the previous element

private static class Node<E> {
        //itself
        E item;
        //Next element
        Node<E> next;
        //Previous element
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

🔥 principle

● LinkedList is implemented through a two-way linked list. An internal class: Entry: entry is the data structure corresponding to the two-way linked list node. It includes the following attributes: the value contained in the current node, the previous node and the next node
● the cloning function of LinkedList is to clone all elements into a new LinkedList object.
● LinkedList implements Java io. Serializable: when writing to the output stream, write the "capacity" first, and then write the "value protected by each node" successively; When reading the input stream, read "capacity" first, and then "each element" in turn
● because LinkedList implements Deque, the Deque interface defines the methods of accessing elements at both ends of the double ended queue: it provides methods of inserting, removing and checking elements. Each method has two forms: one is to throw an exception when the operation fails, and the other is to return a special value (null or false, etc.)

🔥 Traversal mode

LinkedList supports multiple traversal modes

package ListTest;
 
import java.util.ArrayList;
import java.util.Iterator;
 
public class Test {
	public static void main(String[] args) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(7);
		list.add(6);
		list.add(5);
		list.add(8);
		list.add(9);
		list.add(11);
		//Traversal through iterators
		Iterator<Integer> iterator = list.iterator();
		while(iterator.hasNext()) {
			System.out.print(iterator.next()+" ");
		}
		System.out.println("\n--------------------------");
		//for loop traversal
		for (Integer integer : list) {
			System.out.print(integer+" ");
		}
		System.out.println("\n--------------------------");
		//Random access through list Get (I) get the index value to traverse. It is not recommended
		for(int i=0;i<list.size();i++) {
			System.out.print(list.get(i)+" ");
		}
		
	}
	
}

It is inefficient to traverse LinkedList by random access, and it is more efficient to traverse one by one

🔥 common method

4, Vector

Vector is a vector queue, and the bottom layer is an array
The operation in Vector is thread safe and inefficient

🔥 Constructor

 //Like ArrayList, Vector is implemented based on this array
protected Object[] elementData;
//This is equivalent to the size in ArrayList
protected int elementCount;
//When the size of Vector is larger than its capacity, the capacity of Vector will increase automatically. 
protected int capacityIncrement;
//Constructor with parameters of capacity and automatic capacity increase
public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        //Initialize array
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }

    //Constructor for a given capacity
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

    //non-parameter constructor 
    public Vector() {
        //Initializes the array with a size of 10
        this(10);
    }

At the time of new Vector(), the array in the vector has been initialized, and the length of the array is 10

🔥 principle

● Vector actually saves data through an array. If the default constructor is used when constructing Vecotr, the default capacity of Vector is 10
● when the capacity of Vector is insufficient to accommodate all elements, the capacity of Vector will increase. If the capacity increase factor is > 0, increase the capacity value by "capacity increase factor"; Otherwise, double the capacity.
● cloning function of Vector, that is to clone all elements into an array

🔥 Traversal mode

1. Traversal through iterators. That is, traverse through Iterator

Integer value = null;
int size = vec.size();
for (int i=0; i<size; i++) {
    value = (Integer)vec.get(i);        
}

1. Random access, traversing through the index value

Integer value = null;
int size = vec.size();
for (int i=0; i<size; i++) {
    value = (Integer)vec.get(i);        
}

1. for loop

Integer value = null;
for (Integer integ:vec) {
    value = integ;
}

1. Enumeration traversal

Integer value = null;
Enumeration enu = vec.elements();
while (enu.hasMoreElements()) {
    value = (Integer)enu.nextElement();
}

🔥 common method

5, ArrayList LinkedList Vector

The main difference lies in the different implementation methods. All have different efficiency for different operations

1. ArrayList
   ArrayList is an array whose size can be changed and threads are not synchronized (concurrency is not supported). The internal value can be null. When more elements are added to the ArrayList, the size will increase automatically, and the internal elements can be accessed directly through the get/set method, because the ArrayList is essentially an array
2. LinkedList
   LinkedList is based on double linked list, which has better performance than ArrayList when adding and deleting elements. However, in terms of get/set, it is weaker than ArrayList (provided that these comparisons are in the case of large amount of data or cumbersome operation). The internal value of LinkedList can be null, but NullPointerException will appear when we call the element with null value
   LinkedList is more suitable for ① no large number of random access operations ② a large number of add/remove operations.
3. Vector
   It belongs to the array of thread synchronization (supporting concurrency), and the internal value can also be null

🎁 Summary: ArrayList and Vector are implemented as arrays at the bottom, and the value can be null. ArrayList does not support concurrency, and Vector supports concurrency; LinkedList is based on double linked list, so it is faster than ArrayList when adding / removing elements
👌 The author is a Java beginner. If there are errors in the article, please comment and correct them in private letters and learn together~~
😊 If the article is useful to the friends, please praise it 👍 follow 🔎 Collection 🍔 Is my biggest motivation!
🚩 Step by step, nothing to a thousand miles, book next time, welcome to see you again 🌹