preface

This paper sorts out the relevant knowledge of List and Queue, introduces the relevant implementation classes, with relevant source code and some understanding. If there is any mistake, please correct it.

List

For List, a common comparison is Vector
Differences among LinkedList, ArrayList and Vector

ArrayList

It adopts the form of array and uses a continuous linear storage space, which is more suitable for random search and traversal than insertion and deletion.

Code implementation and construction method

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 */
private int size;

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
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);
    }
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
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;
    }
}

Common methods

• add(E e)
• add(int index, E element)
• addAll(Collection<? extends E> c)
• set(int index, E element)
• get(int index)
• remove(int index)
• indexOf(Object o)
• lastIndexOf(Object o) gets the index of the last occurrence of the element:

supplement

• Subscript out of bounds check: for index related methods, rangeCheck(index) will be called to check whether it is out of bounds.
• Container checking mechanism: when adding, it will first call ensureCapacityInternal(size + 1). When the array subscript is not enough, it will be expanded to 1.5 times of the original newcapacity = oldcapacity + (oldcapacity > > 1);
• Fail fast mechanism: ArrayList also adopts the mechanism of fast failure, which is realized by recording the modCount parameter. In the face of concurrent modifications, the iterator will soon fail completely, rather than risking arbitrary uncertain behavior at an uncertain time in the future.

Comparison with Vector

1. Thread safety

ArrayList thread is not safe and synchronized. Vector thread is safe and synchronized, but it is discarded because of the large lock granularity.

1. Capacity expansion mechanism

The Vector is doubled and the ArrayList is only increased by half.

LinkedList

The List interface and Deque interface are implemented at the same time, which can be regarded as a sequential container or a stack or queue.

For stacks or queues, the first choice now is_ ArrayDeque_， It has more advantages than_ LinkedList_ (when used as a stack or queue) has better performance.

The implementation of LinkedList determines that all operations related to subscripts are linear time, while deleting elements at the first or end only requires constant time. In order to pursue efficiency, LinkedList does not realize synchronization. If multiple threads need concurrent access, collections can be used first The synchronizedlist () method wraps it.

Code implementation and construction method

transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

/**
 * Constructs an empty list.
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}


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;
    }
}
  

Common methods

• getFirst()
• getLast()
• removeFirest()，removeLast()
• remove(Object o)
• remove(index))
• add(E e)
• add(int index, E element)
• clear()

Supplement:

• Subscript out of bounds check: when calling index, the subscript out of bounds check checkPositionIndex(index) will be performed
• Search start judgment: the linked list is bidirectional, with next and prev pointers. The search direction depends on the condition index < (size > > 1) to judge which end is close.
• Unlink method: when deleting, the unlink method will be called. In the unlink method, the element to be deleted and the next element will be set to null to help with JVM garbage collection.

The difference between ArrayList and LinkedList

ArrayList and LinkedList both implement the List interface, with the following differences:

1. Bottom implementation

ArrayList stores data in the form of index (subscript), and the bottom layer is implemented by array, which is convenient for index based search. The time complexity is O(1). Because space debris may occur in the addition and deletion operations, and it is necessary to recalculate the size and update the index, it is unfavorable to the addition and deletion operations. LinkedList stores data in the form of mutual links between elements. The bottom layer is realized by linked list, which is easy to insert and delete, which is not conducive to the search of involved locations. The time complexity is O(N).

1. Space occupation

LinkedList takes more memory than ArrayList because LinkedList stores two references for each node, one to the previous element and one to the next element.

Queue

PriorityQueue

PriorityQueue is the priority queue. The priority queue actually maintains a heap structure. By default, the small top heap is implemented in the Java priority queue, that is, the elements taken out each time are the smallest (placed at the head of the queue). The sorting rules can be through the natural order of the elements themselves or the comparator passed in during construction_ Comparator**. **_

Mapping of array subscripts
The bottom layer of priority queue is array implementation, and the maintenance of heap characteristics mainly depends on the mapping rules of array subscripts.

• Left node: leftNo = parentno * 2 + 1 -- > child = (k < < 1) + 1;
• Right node: rightNo = parentno * 2 + 2 -- > right = child + 1;
• Parent node: parentno = (nodeno - 1) / 2 -- > parent = (k - 1) > > 1;

Common methods

	Return exception	Return false
insert	add()	offer()
Gets but does not delete the team leader element	element()	peek()
Get and delete the team leader element	remove()	poll()

Maintenance of small top pile

It mainly depends on the implementation of siftUp() and siftDown(), both of which are the implementation of maintaining heap. The former is used to insert elements and the latter is used to delete elements.

• Add the element and put the element x at the end of the queue. Call siftup (int, k, e, x). k indicates the end of the queue subscript, and X is the element to be inserted. The default comparison logic is to compare with the previous parent node. If it is smaller than the parent node, exchange it. You can also customize the comparison logic with the comparator.
• Deleting an element can be divided into two cases: deleting the end of the queue or other locations. The specific implementation is to find the coordinates of the node to be deleted and judge the situation. The former directly makes the deleted node empty, and the latter calls siftDown(int index, E x). Here, index is the location of the deleted node, and X is the tail element.

siftUp

siftDown

Related source code

// offer(E e)
public boolean offer(E e) {
    if (e == null)//null elements are not allowed
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);//Automatic capacity expansion
    size = i + 1;
    if (i == 0)//The queue was empty. This is the first element inserted
        queue[0] = e;
    else
        siftUp(i, e);//adjustment
    return true;
}

// siftUp() is used to insert element x and maintain the characteristics of the heap.
private void siftUp(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;//parentNo = (nodeNo-1)/2
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)//Call the comparison method of the comparator
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}

// siftDown()
private void siftDown(int k, E x) {
    int half = size >>> 1;
    while (k < half) {
    	// First, find the smaller of the left and right children, record it in c, and record its subscript with child
        int child = (k << 1) + 1; //leftNo = parentNo*2+1
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            comparator.compare((E) c, (E) queue[right]) > 0)
            c = queue[child = right];
        if (comparator.compare(x, (E) c) <= 0)
            break;
        queue[k] = c; //Then replace the original value with c
        k = child;
    }
    queue[k] = x;
}

// remove(Object o)
public boolean remove(Object o) {
	//Find the first subscript satisfying the o.equals(queue[i]) element by traversing the array
    int i = indexOf(o);
    if (i == -1)
        return false;
    int s = --size;
    if (s == i) //Case 1
        queue[i] = null;
    else {
        E moved = (E) queue[s];
        queue[s] = null;
        siftDown(i, moved);//Situation 2
        ......
    }
    return true;
}

Deque

Deque is "double ended queue", indicating a two-way Queue. It inherits the Queue interface and supports insert, remove and examine operations. It is a two-way Queue, so you can operate on both ends of the Queue. Common methods may return false or throw exceptions.

Common methods

	First Element - Head		Last Element - Tail
	Throws exception	Special value	Throws exception	Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFirst()	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

ArrayDeque

For the implementation of stack and queue, the official recommends ArrayDeque. The bottom layer of ArrayQueue is based on an array that can be expanded. In order to improve performance, the implementation of circular array is adopted, that is, the data is logically continuous, but physically divided into two sections. For the space length of the array, in order to facilitate the and operation, the integer multiple of 2 is used, and the default is 16.

Most ArrayDeque operations run in flat constant time. Exceptions include remove, removeFirstOccurrence, removeLastOccurrence, contains, and iterator Remove () and bulk operations, all of which run in linear time.

Basic elements

    //The length of the array storing elements is always a power of 2. If the array is full, it will be expanded immediately
    transient Object[] elements; // non-private to simplify nested class access

    //Index of the head node
    transient int head;

    //The index of the location where the element is added
    transient int tail;

    //Minimum capacity, a power of 2
    private static final int MIN_INITIAL_CAPACITY = 8;

Common methods

• addFirst(E e)
• addLast(E e)
• pollFirst()
• pollLast()
• peekFirst()
• peekLast()

Capacity expansion mechanism

1. Capacity expansion time: when the head and tail pointers meet, call doubleCapacity(). When adding, assign values first, and then check the capacity.
2. Capacity expansion mechanism: the logic is to apply for a larger array (twice the original array) and then copy the original array. When the array length is known, you can directly new a fixed length array, so there is no need for array The copyofrange function can be used uniformly arrayCopy. When copying, copy the right side first and then the left side.

//doubleCapacity()
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // Number of elements on the right side of head
    int newCapacity = n << 1;//Twice the original space
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);//Copy the right half, corresponding to the green part in the above figure
    System.arraycopy(elements, 0, a, r, p);//Copy the left half, corresponding to the gray part in the above figure
    elements = (E[])a;
    head = 0;
    tail = n;
}

supplement

1. In a circular array, the data may be divided into two pieces. Therefore, when adding, you need to judge whether the subscript of the adding position is on the left or right.

   • For the head of the queue, the pointer subscript keeps retreating. When it retreats to index 0, it returns to the right end of the spatial array.

     elements[head = (head - 1) & (elements.length - 1)] = e;

   • For the tail of the queue, the pointer subscript continues to expand forward. After reaching the spatial array subscript, it returns to the 0 pointer again.

2. Calculate the queue length. If it is physically discontinuous, it is necessary to specially calculate the real data. ArrayDeque uses bit and operation: return (tail - head) & (elements. Length - 1);

3. When deleting a data in the middle, delete it on the left or right, and then move the head or tail. When deleting an intermediate element, first judge whether the head in the intermediate element is close to or close to the tail, and then move the closer end. At this time, move the logically closer end, but you still need to move the array elements in batches twice.

4. When head = -1, in the computer, the binary of - 1 is 11111111, so the final and operation result is elements length - 1.

Related code

//addFirst(E e)
public void addFirst(E e) {
    if (e == null)//Nulls are not allowed
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//2. Whether the subscript is out of bounds
    if (head == tail)//1. Is there enough space
        doubleCapacity();//Capacity expansion
}

//addLast(E e)
public void addLast(E e) {
    if (e == null)//Nulls are not allowed
        throw new NullPointerException();
    elements[tail] = e;//assignment
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)//Subscript out of bounds processing
        doubleCapacity();//Capacity expansion
}

Reference articles

pdai Java full stack knowledge system
In depth understanding of the design and implementation of ArrayDeque