Add element source

void linkLast(E e) 
{
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        Nulltail Pointers all point to the first element
        first = newNode;
    else
        // Next of the last element points to the new element
        l.next = newNode;
    size++;
    modCount++;
}
Copy the code

Node data structure


private static class Node<E> {
    // Store the data
    E item;
    Node<E> next; // The previous element
    Node<E> prev; // Next element New element is always the last element
	// Next =null, prev =last

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

Look for the element

 Node<E> node(int index) 
 {
        // assert isElementIndex(index);

        if (index < (size >> 1)) 
		{
		    // Binary search
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } 
		else 
		{
		    // From back to front
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            returnx; }}Copy the code

Data structure diagram

As a queue property

private void linkFirst(E e) 
{
        // 1
        final Node<E> f = first;
		// create new node next -->f new element before null
        final Node<E> newNode = new Node<>(null, e, f);
		// 3, the header pointer points to a new node
        first = newNode;
        if (f == null)
		    // Both the tail pointer and the header pointer point to the first element
            last = newNode;
        else
		    // When the second element is added, the previous element of the header pointer points to the new element
            f.prev = newNode;
		// Number of elements +1
        size++;
        modCount++;
}
Copy the code

Queue offer source code

Queue<String> q1 = new LinkedList<>(); // Add (); Methods q1. Offer (" aa "); q1.offer("bb"); q1.offer("cc"); While (q1.peek()! = null) { System.out.println(q1.poll()); } // stack Deque<String> list = new LinkedList(); List.push ("1111"); list.push("1111"); list.push("2222"); list.push("3333"); while (list.peek() ! =null) { String fd = list.poll(); System.out.println(fd); }Copy the code

Peek source

Public E peek() {final Node<E> f = first; return (f == null) ? null : f.item; }Copy the code

Poll source

public E poll() 
{
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
Copy the code

UnlinkFirst source

Private E unlinkFirst(Node<E> f) {// Assert f == first && f! = null; final E element = f.item; final Node<E> next = f.next; f.item = null; f.next = null; // help GC // first = next; if (next == null) last = null; Prev =null Help GC next. Prev =null; // quantity --1 size--; +1 modCount++; return element; }Copy the code

There are 2 ways to determine whether there are elements in a team or not. What is the difference between methods?

Adding elements to the end (add, offer) : add() throws an exception if the length is insufficient: IllegalStateException; Offer () does not, only returning false

Look at the header element(Element, peek), return the header element but not change the queue element() throws an exception if there are no elements: NoSuchElementException; Peek () returns null.

Removing the header element (remove, poll) returns the header element, and removing remove() from the queue throws an exception if there is no element: NoSuchElementException; Poll () returns null.