Join @LinkedList (version 1.7)

1. What is LinkedList

AbstractSequentialList bidirectional linked lists can be treated asThe stack,The queueordequeoperate
Ordered, non-thread-safe, bidirectional linked lists that use tail insertion by default
This parameter is applicable to frequently add or delete scenarios. Select frequently access scenariosArrayList
Insert and delete time complexity is O(1), other worst O(n)
Due to the implementation of the Deque interface, there are many methods related to the double-endian queue, which will be specifically discussed and not detailed here
This release is based on JDK1.7

2. Data structure of LinkedList

The class definition

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

AbstractSequentialList can be inherited and operated as a stack, queue, or double-endian queue

List interface, can carry out queue operations

Implement a Deque interface that uses the LinkedList as a double-ended queue

Cloneable interface, rewrite clone() method, can clone

Implement java.io.Serializable interface, support serialization

Important global variable

    
     / * *
     * Number of current list elements
     * /
     transient int size = 0;
     / * *
       * Pointer to first node.
     * Invariant: (first == null && last == null) || (first.prev == null && first.item ! = null)
     * List header node
     * /
     transient Node<E> first;
     / * *
       * Pointer to last node.
     * Invariant: (first == null && last == null) || (last.next == null && last.item ! = null)
     * List tail node
     * /
     transient Node<E> last;

The constructor

    
     / * *
       * Constructs an empty list.
     * Default empty constructor -- Note that LinkedList does not provide a constructor for the specified capacity
     * /
     public LinkedList() {
     }
     / * *
       * Constructs a list containing the elements of the specified
       * collection, in the order they are returned by the collection's iterator.
     * Support for converting a Collection to a LinkedList
       *
       * @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);
     }

The Node Node

    
     / * *
     * Store object structure:
     * Each Node contains references to the previous Node and the next Node, thus forming a bidirectional linked list
     * /
     private static class Node<E> {
     E item; // Store elements
     Node<E> next; // point to the next node
     Node<E> prev; // point to the previous node
     // The first element is prev, and the second element is the storage element
         Node(Node<E> prev, E element, Node<E> next) {
             this.item = element;
             this.next = next;
             this.prev = prev;
         }
     }

3. LinkedList storage

Add method parsing

    
     / * *
       * Appends the specified element to the end of this list.
       * <p>This method is equivalent to {@link #addLast}.
     * Insert a new element to the end of the list
       * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add}
     * /
     public boolean add(E e) {
         linkLast(e);
         return true;
     }
     / * *
       * Inserts the specified element at the specified position in this list.
       * Shifts the element currently at that position (if any) and any
       * subsequent elements to the right (adds one to their indices).
     * Inserts a new element at the specified subscript position, and all elements greater than that subscript are moved one bit to the right
       * @param index index at which the specified element is to be inserted
       * @param element element to be inserted
       * @throws IndexOutOfBoundsException {@inheritDoc}
     * /
     public void add(int index, E element) {
     checkPositionIndex(index); // subscript boundary check
     If (index == size) // Insert tail when subscript == list length
             linkLast(element);
         else
     linkBefore(element, node(index)); // Otherwise, insert front (start position index)
     }

CheckPositionIndex method resolution

    
     private void checkPositionIndex(int index) {
     if (! isPositionIndex(index))
             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
     }
     / * *
       * Tells if the argument is the index of a valid position for an iterator or an add operation.
     * Determine the bounds of subscripts when iterating or inserting
     * /
     private boolean isPositionIndex(int index) {
         return index >= 0 && index <= size;
     }

LinkLast method parsing

    
     / * *
       * Links e as last element.
     * Change e to the last element in the list
     * /
     void linkLast(E e) {
         final Node<E> l = last;
     final Node<E> newNode = new Node<>(l, e, null); // Note: Next of the new node is null
     last = newNode; // Use the new node as the end of the list
     // When the end of the queue is null, the list is empty
         if (l == null)
     first = newNode; // Use the new node as the head of the list
         else
     l.next = newNode; // Add the next reference to the end node of the original list to the new node
     size++; // The current list length is +1
     modCount++; // The new operation is a structural change, modCount counts +1
     }

LinkBefore method parsing

    
     / * *
       * Inserts element e before non-null Node succ.
     * Inserts a new element before the specified non-empty node
     * /
     void linkBefore(E e, Node<E> succ) {
     // assert succ ! = null;
     // The logic is basically the same as linkLast except that last is changed to prev and the new node is inserted before the suCC node
         final Node<E> pred = succ.prev;
         final Node<E> newNode = new Node<>(pred, e, succ);
     succ.prev = newNode; // The only difference is that the new node is inserted before the succ node
         if (pred == null)
             first = newNode;
         else
             pred.next = newNode;
         size++;
     modCount++; // Insert is a structural change, modCount counts +1
     }

If the reader cares, he willlinkBefore()There are no short pointer judgments, but only comment hints, for two reasons
- CheckPositionIndex (index) : checkPositionIndex(index) : checkPositionIndex(index)IndexOutOfBoundsExceptionTo terminate the method
- Succ =node(index) succ=node(index) succ=node(index)

4. Read LinkedList

Get method parsing

    
     / * *
       * Returns the element at the specified position in this list.
     * Gets the specified subscript element
       * @param index index of the element to return
       * @return the element at the specified position in this list
       * @throws IndexOutOfBoundsException {@inheritDoc}
     * /
     public E get(int index) {
         checkElementIndex(index);
     return node(index).item; // Return item instead of node; Node must not be null, and item can be null
     }

The checkElementIndex method resolves

    
     private void checkElementIndex(int index) {
     if (! isElementIndex(index))
             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
     }
     / * *
       * Tells if the argument is the index of an existing element.
     * To determine whether the current index has an element, see 'linkBefore' for the principle
     * Attentive readers may have noticed:
     * (get) isElementIndex = index >= 0 && index < size;
     * (add) isPositionIndex = index >= 0 && index <= size;
     * isPositionIndex =size * isPositionIndex =size * isPositionIndex =size
     * From this we can see that:
     * Get subscript must be smaller than size, otherwise subscript out of bounds;
     * Add (specify elements) :
     * When index = size, use tail insertion, because to occupy the subscript size position;
     * When index < size, use front insert, because to occupy the index position, and the original position element moved back;
     * /
     private boolean isElementIndex(int index) {
         return index >= 0 && index < size;
     }

Node method parsing

    
     / * *
       * Returns the (non-null) Node at the specified element index.
     * Returns a non-empty node with the specified subscript
     * Node has no verb form, so why not getNode?
     * By the way: nodeJs is really good!
     * /
     Node<E> node(int index) {
         // assert isElementIndex(index);
     // It is worth mentioning that, in order to improve query efficiency, node queries choose to use binary lookup method
     // Personal opinion: But probably because The great God Josh Bloch doesn't think LinkedList is a good place to find, it's just a simple binary
         if (index < (size >> 1)) { 
     Node<E> x = first; // If it's in the front, look from front to back
             for (int i = 0; i < index; i++)
                 x = x.next;
             return x;
         } else {
     Node<E> x = last; // If in the back, go from the back to the front
             for (int i = size - 1; i > index; i--)
                 x = x.prev;
             return x;
         }
     }

5. Remove the LinkedList

Remove method parsing

    
     / * *
       * Retrieves and removes the head (first element) of this list.
     * The header node is deleted by default
       * @return the head of this list
       * @throws NoSuchElementException if this list is empty
     * @ since 1.5
     * /
     public E remove() {
         return removeFirst();
     }
     / * *
       * Removes the element at the specified position in this list.  Shifts any
       * subsequent elements to the left (subtracts one from their indices).
       * Returns the element that was removed from the list.
     * Deletes elements based on subscripts
       * @param index the index of the element to be removed
       * @return the element previously at the specified position
       * @throws IndexOutOfBoundsException {@inheritDoc}
     * /
     public E remove(int index) {
     checkElementIndex(index); // index >= 0 && index < size
     return unlink(node(index)); // Unbind
     }
     / * *
       * Removes the first occurrence of the specified element from this list,if it is present. 
       * If this list does not contain the element, it is unchanged.
       * More formally, removes the element with the lowest index {@code i}  such that
     * <tt>(o==null? get(i)==null:; o.equals(get(i)))</tt> (if such an element exists).
       * Returns {@code true} if this list contained the specified element (or equivalently, 
       * if this list changed as a result of the call).
     * Remove an element directly:
     * When the element does not exist, nothing changes
     * Returns true if the element existed and was successfully removed, false otherwise
     * When there are duplicate elements, only the first occurrence of the same element is deleted:
     * For example, remove only the first occurrence of null (i.e., null with the smallest subscript)
       * @param o element to be removed from this list, if present
       * @return {@code true} if this list contained the specified element
     * /
     public boolean remove(Object o) {
     // Although it is traversal like ArrayList, it is more efficient because there is no need to call the time-consuming 'system. arrayCopy'
         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;
     }

Unlink method parsing

    
     / * *
       * Unlinks non-null node x.
     * Unlinking node does three things:
     * 1. Unbind the links between the front and back nodes of the current element and rebind the relationship between the front and back nodes
     * 2. Clear all attributes of the current element, help GC
     * 3. List length -1, modCount count +1(help fail-fast)
     * @return returns the element itself. Note that this is item, not node
     * /
     E unlink(Node<E> x) {
     // assert x ! = null;
         final E element = x.item;
     final Node<E> next = x.next; // The last node
     final Node<E> prev = x.prev; // The previous node
     // Unbind the first node
     If (prev == null) {// The current node is in the head of the list
     first = next; // Place the last node at the head of the list
         } else {
     // Unlinked list header
     prev.next = next; // Next points to the next node
     x.prev = null; // The first node of the current node clears, help GC
         }
     // Unbind the last node
     If (next == null) {// The current node is at the end of the list
     last = prev; // put the previous node at the end of the list
         } else {
     // Unlinked list tail
     next.prev = prev; // Point the prev of the latter node to the former node
     x.next = null; // The last node of the current node is cleared, help GC
         }
     x.item = null; // The current node element is cleared
     size--; // The list length is -1
     modCount++; // Delete operations are structural changes, modCount counts +1
     return element; // Returns the element itself
     }

UnlinkFirst method parsing

    
     / * *
       * Unlinks non-null first node f.
     * Unbind the head
     * /
     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; // The next node is the new head node
     If (next == null) // The header is already null, then the tail is also null
             last = null; 
         else
     next.prev = null; // The prev of the new head node needs to be emptied, non-closed loop
         size--;
         modCount++;
         return element;
     }

UnlinkLast method parsing

    
     / * *
       * Unlinks non-null last node l.
     * Unbind the tail
     * /
     private E unlinkLast(Node<E> l) {
     // assert l == last && l ! = null;
         final E element = l.item;
         final Node<E> prev = l.prev;
         l.item = null;
         l.prev = null; // help GC
     last = prev; // The last node is the new tail node
     If (prev == null) // If the tail is already null, then the header is also null
             first = null;
         else
     prev.next = null; // Next of the new tail node needs to be emptied, non-closed loop
         size--;
         modCount++;
         return element;
     }

6. Collation of other major apis for LinkedList

To find the

Get the header node:getFirst().peekFirst().peek().element()

Get the tail node:getLast().peekLast()

NoSuchElementException:getFirst() 和 getLast()

null:peekFirst() 和 peekLast()

peek()Is equivalent topeekFirst().element()Internally calledgetFirst()

insert

Head insert:addFirst(E e).offerFirst(E e)

Tail insert:addLast(E e).offerLast(E e)

void:addFirst(E e),addLast(E e).push(E e)

boolean:add(E e),offer(E e),offerFirst(E e).offerLast(E e)

linkLast(E e)Is equivalent toadd(E e), most methods are implemented aslinkFirst(E e) 和 linkLast(E e)

delete

Header deletion:removeFirst().poll().pollFirst().pop()

Tail delete:removeLast().pollLast()

NoSuchElementException:remove(),removeFirst().removeLast().removeLast()

null:poll(),pollFirst(),pollLast()

remove()Is equivalent toremoveFirst(), most methods are implemented asunlinkFirst(Node<E> n) 和 unlinkLast(Node<E> n)

removeLastOccurrence(Object o) 与 remove(Object o)The implementation of almost the same, the difference between the former is reverse order search, the latter is positive order search

7. Stack implementation of LinkedList

A Stack is a linear list limited to insert and delete operations at one end

According to LIFO, the top is called the top of the stack and the bottom is called the bottom of the stack.

    
     / * *
     * Simple implementation of the LinkedList version of the queue
     * Use first (same principle with last, make sure you only work on one end)
     * /
     class Stack<T> {
         LinkedList<T> linkedList = new LinkedList<T>();
     / * *
     * into the stack
     * /
         public void push(T v) {
            linkedList.addFirst(v);
         }
     / * *
     * Out of the stack without deleting the top element
     * /
         public T peek() {
            return storage.getFirst();
         }
     / * *
     * Remove the top element from the stack
     * /
         public T pop() {
            return storage.removeFirst();
         }
     }

8. Queue implementation of LinkedList

A Queue is a linear list of limited inserts and deletions at one end

According to the first in, first out (FIFO) principle, the end of the table that allows inserts is called Rear, and the end that allows deletions is called Front.

    
     / * *
     * Simple implementation of the LinkedList version of the queue
     * Here we use the end of the queue insert, head delete notation (the reverse principle is the same, as long as the insert and delete are on each end)
     * /
     class Queue<T> {
         LinkedList<T> linkedList = new LinkedList<T>();
     / * *
     * To join a queue, insert the specified element at the end of the queue
     * /
         public void offer(T v) {
             linkedList.offer(v);
         }
     / * *
     * Gets the header element, but does not delete it, or returns NULL if the queue is empty
     * /
         public T peek() {
             return linkedList.peek();
         }
     / * *
     * Out of the queue, get the header element, but do not delete, if the queue is empty, throw exception
     * /
         public T element() {
             return linkedList.element();
         }
     / * *
     Get the header element and delete it, or return NULL if the queue is empty
     * /
         public T poll() {
             return linkedList.poll();
         }
     / * *
     Get the header element and delete it. If the queue is empty, throw an exception
     * /
         public T remove() {
             return linkedList.remove();
         }
     }

Table of contents

- - COLLECTIONS 7
  - LinkedList is pass
  - ArrayList is pass
  - LinkedHashSet is pass
  - LinkedHashMap are general
  - HashTable is pass
  - HashSet is pass
  - HashMap is pass
- - JAVA 7
  - LinkedList is pass
  - ArrayList is pass
  - LinkedHashSet is pass
  - LinkedHashMap are general
  - HashTable is pass
  - HashSet is pass
  - HashMap is pass
- - Source 7
  - LinkedList is pass
  - ArrayList is pass
  - LinkedHashSet is pass
  - LinkedHashMap are general
  - HashTable is pass
  - HashSet is pass
  - HashMap is pass

1. What is LinkedList

2. Data structure of LinkedList

3. LinkedList storage

4. Read LinkedList

5. Remove the LinkedList

6. Collation of other major apis for LinkedList

7. Stack implementation of LinkedList

8. Queue implementation of LinkedList

Table of contents

Related Posts

Java concurrency (4) Synchronized keyword and various locks implementation principle

Message middleware that thing | Java development practice

JDK 16 was released yesterday.