LinkedList source code parsing (JDK1.8)

LinkedList is a bidirectional LinkedList based on a LinkedList implementation

Again, let’s start with the class diagram

As you can see from the class diagram, LinkedList inherits an abstract class and implements four interfaces, which are briefly described below:

  • AbstractSequentialList: Iterator iterator operations
  • List: provides operations such as adding, deleting, modifying, and checking linked lists and iterator traversal
  • Deque: provide operation of adding, deleting, modifying and checking of the first and last team
  • Cloneable: Copy operations by field
  • Serializable: Enables its serialization operation

attribute

Attribute related source code

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;Copy the code

transient int size = 0; // The number of elements in the list

transient Node first; / / head node

transient Node last; / / end nodes

A constructor



    /**
     * 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);
    }

Copy the code

You can see that there are two constructors:

  • LinkedList() : no-argument constructor
  • LinkedList(Collection
    c): constructor for collection C to directly set the list order

node

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; }}Copy the code

Element represents the stored Value, pre and Next point to the previous node and the next node of the current node respectively, which can also be seen as bidirectional

Add and delete

In our actual project, the most we do around LinkedList is to add, delete, change and check related operations. We will carefully explore the official implementation method

Elements borrowed from

Single element is removed

Unpacking elements we’ll start with the simplest single unpacking elements

public boolean add(E e) { linkLast(e); return true; } void linkLast(E E) {final Node<E> l = last; Final Node< e > newNode = newNode <>(l, e, null) final Node< e > newNode = newNode <>(L, e, null) // Last = newNode; If (l == null) first = newNode; if (l == null) first = newNode; if (l == null) first = newNode; else l.next = newNode; // Number of elements +1; // list changes +1 modCount++; }Copy the code

As you can see from above, adding (e) directly is very simple, so let’s look at other methods of unpacking elements

Subscript position unhooks nodes

Public void add(int index, E element) {public void add(int index, E element) {checkPositionIndex(index); If (index == size) linkLast(element); if (index == size) linkLast(element); else linkBefore(element, node(index)); Void linkBefore(E E, Node<E> succ) {// Assert succ! = null; // Final Node<E> pred = succ.prev; Final Node<E> newNode = newNode <>(pred, E, succ); final Node<E> newNode = newNode <>(pred, E, succ) Succ. prev = newNode; succ.prev = newNode; If (pred == null) first = newNode; if (pred == null) first = newNode; Else // if pred is not null, change the next node of pred to the newNode pred.next = newNode; // Number of elements +1; // list changes +1 modCount++; }Copy the code

AddFirst (), addLast() are also new and simple, source code to take a look at the line, we will explain the addAll() method

Multiple elements are removed

public boolean addAll(int index, Collection<? Extends E> c) {extends E> c) {extends E> c) {extends E> c) { [] a = c.toarray (); // Convert the collection of elements to array Object[] a = c.toarray (); Int numNew = a.length; if (numNew == 0) return false; // define the previous Node, the current Node Node<E> pred, succ; If (index == size) {// If (index == size) {succ = null; pred = last; } else {// If succ = node(index); // if succ = node(index); pred = succ.prev; For (Object O: a) {// Element conversions @suppressWarnings ("unchecked") E E = (E) o; < e > newNode = newNode <>(pred, e, null); If (pred == null) first = newNode; // If (pred == null) first = newNode; Else // if pred is not null, set the next node of the original index node to the current newNode. Pred = newNode; // after a newNode is completed, set the previous node to the current newNode until all elements are unwrapped. If (succ == null) {last = pred; if (succ == null) {last = pred; } else {//index is not null, then set next to the last element of the array to succ,succ before the current one. succ.prev = pred; } // Get the number of new list elements size += numNew; // list changes +1 modCount++; return true; }Copy the code

The direct addAll (Collection <? Extends E> c) extends E> c) Extends E> c) Extends E> c) Extends E> c) Extends E> c) Extends E> c) Extends E> c) Extends E> c) Extends E> c

Remove elements

Single element deletion

Public Boolean remove(Object o) {if (o == null) {public Boolean remove(Object o) { For (Node<E> x = first; x ! = null; x = x.next) { if (x.item == null) { unlink(x); return true; For (Node<E> x = first; x ! = null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; Unlink (Node<E> x) {// Assert! = null; Final E element = x.tem; Final Node<E> next = x.next; final Node<E> prev = x.prev; If (prev == null) {first = next; } else {// set prex.next to x.ext prev.next = next; // the previous node of x is null x.rev = null; } // If (next == null) {// Set last = prev; } else {// set x.ext.prev to x.prev next-prev = prev; // the last node of x is null x.ext = null; } // set the element of the x node to null to help gc reclaim X.tem = null; // list element -1 size--; ModCount++; return element; }Copy the code

I’m just going to delete an element and just to finish up, let’s talk about deleting an element by index

Public E remove(int index) {public E remove(int index) {public E remove(int index) {public E remove(int index) { return unlink(node(index)); } Node<E> node(int index) { // assert isElementIndex(index); If (index < (size >> 1)) {// if (index < (size >> 1)) {Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else {Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; }}Copy the code

Remove (int index) is also well understood. Remove () and removeFirst() both remove from the beginning node and removeLast() remove from the end node

Update the element

Public E set(int index, E element) {public E set(int index, E element) {public E set(int index, E element) { //node <E> x = node(index); // Set the element of the new node and return the old element E oldVal = x.tem; x.item = element; return oldVal; }Copy the code

Look for the element

All the methods inside get() have been introduced

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
Copy the code

On the whole, the implementation of LinkedList is also very simple. We can see that it is fast to add and delete LinkedList, but slow to change and search. The comparison and analysis between ArrayList and LinkedList is easy to understand, and the speed of increase, delete, change and search is completely opposite. Therefore, it can also be concluded that in actual projects, we need to use LinkedList for frequently adding and deleting data, and ArrayList for frequently checking data

Other methods

Contains () and clear() are also briefly looked at

public boolean contains(Object o) { return indexOf(o) ! = 1; } public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x ! = null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x ! = null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } public void clear() {// Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even If there is a reachable Iterator, set the element to null for (Node<E> x = first; x ! = null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }Copy the code

Thread safety

  • LinkedList is thread-unsafe
  • Collections. SynchronizedList () can realize LinkedList thread-safe
  • ConcurrentLinkedDeque is thread-safe

We need to compare the related ones above to facilitate our understanding and analysis, and then we need to compare them with ArrayList