LinkedList source code analysis

Due to my busy work recently, I optimized part of the APP, during which I also learned a lot of knowledge about layout optimization and other performance optimization, but I still feel that it is not systematic, and I look forward to more high-quality performance optimization actual combat articles can emerge, so that we can communicate and learn together.

Over the weekend, I will have time to put my work on hold and continue to study the source code of Java collections. Learn the source code for LinkedList today.

  1. LinkedList is an overview of the
  2. Constructor of LinkedList
  3. Add, delete, change and check LinkedList.
  4. LinkedList is added, deleted, changed, and checked when used as a Queue.
  5. The traversal method of LinkedList

LinkedList is an overview of the

The first step is to open IntelliJ IDEA to find the class you want to view. The second step is to right click on the right button. Diagrams Selecting any item in the Second level menu gives you a diagram like the following. There are many convenient operations. You can use IntelliJ IDEA to view the Diagrams of class inheritance in this article.

The solid blue arrow is the inheritance relationship, and the dotted green arrow is the interface implementation relationship.

  1. LinkedList is derived from AbstrackSequentialList and implements the List interface and Deque two-way queue interface. Therefore, LinkedList not only has list-related operation methods, but also has queue-related operation methods.

  2. Like ArrayList, LinkedList implements Serializable and Cloneable interfaces that allow serialization and cloning.

Some key features of LinkedList:

  1. LinkedListThe underlying data structure of the collection is a bidirectional linked list
  2. LinkedListElements in collections are allowed to be NULL
  3. LinkedListAllow storing duplicate data
  4. LinkedListElements are stored in the order of storage.
  5. LinkedListNon-thread-safe, if you want to ensure thread-safe premise operationLinkedList, you can useList list = Collections.synchronizedList(new LinkedList(...) );To generate a thread-safeLinkedList

Linked list is a data structure different from array. Bidirectional linked list is a sub-data structure of linked list. It has the following characteristics:

Each node has three fields: the current node’s data field, the field pointing to the previous node (prev), and the field pointing to the next node (Next).

LLink Data RLink

LinkedList implementation and member variables

The overview describes the characteristics of bidirectional LinkedList, and LinkedList inherits from Deque, the double LinkedList interface. Before introducing the specific method of LinkedList, we first understand the realization of bidirectional LinkedList.

Private static class Node<E> {private static class Node<E> {private static class Node<E> { // The index of the next Node Node<E> next; // index Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }}Copy the code

As we said, the node implementation of LinkedList fully conforms to the data structure requirements of a two-way LinkedList, and the constructor takes the index of the previous node, the element of the current node, and the index of the next node.

The main member variables of LinkedList are as follows:

//LinkedList transient int size = 0; //LinkedList transient Node<E> first; //LinkedList transient Node<E> last;Copy the code

The reason LinkedList stores the first and last node of a LinkedList is because, as we all know, LinkedList data structures, as opposed to array structures, have a little bit of addition and deletion, but a little bit of lookup. If we save both ends of the LinkedList, when we need to search for nodes by index, we can determine whether to search from the beginning or from the end according to the index and size/2, which makes up for the shortcomings of the single-linked list data structure to some extent.

Constructor of LinkedList

LinkedList has two constructors:

/** * empty argument construction due to generating an empty list first = last = null */ publicLinkedList() {} /** * pass in a collection class, To construct a collection of linkedLists with certain elements * @param c whose internal elements will be used as LinkedList nodes in order * @throws NullPointerException if the parameter collection Public LinkedList(Collection<? extends E> c) { this(); addAll(c); }Copy the code

The constructor with arguments calls addAll(c), which actually calls addAll(size, c) and, when externally called separately, adds the elements of the specified collection as nodes to the end of the LinkedList: AddAll (size, c) inserts collection elements into the specified index node.

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
Copy the code
/** * Insert a node containing all c set elements before the index node. */ public Boolean addAll(int index, Collection<? Extends E> c) {// Check if 0 =< index =< size; // Call the toArray method of the corresponding Collection implementation class to convert the Collection to an array Object[] a = c.toarray (); // Check the length of the arrayfalseInt numNew = a.length;if (numNew == 0)
       return false; Pred Node<E> pred, succ; // If index = size, insert at the end of the listif (index == size) {
       succ = null;
       pred = last;
   } else{ succ = node(index); pred = succ.prev; } // Iterate over the number group to wrap the corresponding element as a node to add to the listfor (Object o : a) {
       @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); // If pred is empty, there are no elements in the LinkedList collection. // The first node generated will be assigned as the head node to the first member variableif (pred == null)
           first = newNode;
       elsepred.next = newNode; pred = newNode; } // If the index element is null, the node pointed by pred is the last node of the new list and is assigned to the last member variableif (succ == null) {
       last = pred;
   } else{// Otherwise, pred next index points to succ, and prev index points to pred pred.next = succ; succ.prev = pred; } // Update the current list length size and returntrueSize += numNew; modCount++;return true;
}
Copy the code

As you can see from the code comments above, the method of adding nodes in batches to LinkedList is implemented. It can be divided into the following steps:

  1. Check if the index value is valid. If not, an out-of-bounds exception will be thrown
  2. Save the index position of the node, and index-1 position of the node, for the single linked list familiar with the students must be clear for the linked list to add and delete operations need two pointer variables to complete, can refer to: understand the single linked surface questions to further understand.
  3. The set of parameters is converted to an array, and the elements of the array are looped into nodes to add to the list.
  4. Updating the list length and returning Add true indicates success.

CheckPositionIndex = 0 && index < size; checkPositionIndex = 0 && index < size;

private String outOfBoundsMsg(int index) {
   return "Index: "+index+", Size: "+size;
}

private void checkElementIndex(int index) {
   if(! isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void checkPositionIndex(int index) {if(! isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } /** * Tellsif the argument is the index of an existing element.
*/
private boolean isElementIndex(int index) {
   return index >= 0 && index < size;
}

/**
* Tells if the argument is the index of a valid position for an
* iterator or an add operation.
*/
private boolean isPositionIndex(int index) {
   return index >= 0 && index <= size;
}
Copy the code

Add, delete, change and check LinkedList

LinkedList Method of adding nodes

LinkedList is an implementation of a LinkedList data structure. Unlike arrays, it can easily insert a node at the beginning and end of the list. Add adds nodes at the end of the list by default:

/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
 public void addFirst(E e) {
    linkFirst(e);
 }

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
 public void addLast(E e) {
    linkLast(e);
 }
    
/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @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;
 }
Copy the code

Note that the add method returns a value. LinkXXX = linkXXX = linkXXX = linkXXX

// Private void linkFirst(E E) {// Final void linkFirst(E E) <E> f = first; Final Node<E> newNode = newNode <>(null, E, f); // first index points to the newNode first = newNode; // If the previous list is empty, the new node will also be considered as unnodeif (f == null)
       last = newNode;
   elsef.prev = newNode; // otherwise, the prev pointer to the previous head node points to the new node, size++; modCount++; Void linkLast(E E) {final Node<E> l = last; NewNode = newNode <>(l, E, null); final Node<E> newNode = newNode <>(l, E, null); //last index points to the last node last = newNode;if(l == null)// if the list was previously empty, the newNode is also the head node;else// otherwise, the next pointer from the previous node-free node points to the newNode l.ext = newNode; size++; modCount++; // operand ++}Copy the code

In addition to the above methods for adding elements, as well as the addAll method described earlier in the construction, LinkedList also provides Add (int index, E Element); Method, let’s look at this method:

Public void add(int index, E element) {// checkPositionIndex(index); // If index = size, insert the node at the endif (index == size)
       linkLast(element);
   else
       linkBefore(element, node(index));
}
Copy the code

LinkBefore (element, node(index)) when 0 =< index 

/** * returns a non-empty Node at index */ Node<E> Node (int index) {assert isElementIndex(index); // If index < size/2, start from 0if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else{// if index >= size/2, start with sie-1.for (int i = size - 1; i > index; i--)
            x = x.prev;
        returnx; }}Copy the code

You might wonder why it says return a non-empty node? If the index is 0 and the list is empty at the beginning, then the index is null. In fact, if we didn’t have an element size = 0 in the list at the beginning, if we add an element at index = 0 we’re not going to go to else, we’re going to call linkLast(Element); Method to add elements. Therefore, the node method can be used to search the node whose index position is specified by the size/2 limit.

So if we go back to linkBefore, why we call it linkBefore, because if we add a node in the middle of the list, we’re just adding a node in front of the original index node, and to add a node we need to know the previous node and the current node of that node,

  1. Prev points to the preceding element of index.
  2. The next pointer points to the node at index,
  3. The index prev pointer points to the new node
  4. The next pointer to the pre-index node (pred) points to the new node.

LinkBefore also does four things:

void linkBefore(E e, Node<E> succ) { // assert succ ! = null; Final Node<E> pred = succ.prev; final Node<E> pred = succ.prev; // New Node prev is pred, next is succ final Node<E> newNode = newNode <>(pred, E, succ) // the prev of the original node points to the newNode succ.prev = newNode; // If pred is null, i.e. a node is inserted out of the head node, the new node is assigned to the first indexif (pred == null)
       first = newNode;
   elsepred.next = newNode; // otherwise, the next pred node is changed to a new one, size++; modCount++; }Copy the code

LinkedList Method of deleting a node

The corresponding method to adding a node is deleting a node:

/** * delete the head node * @returnElement * @throws NoSuchElementException Throws an exception if the list is empty */ public EremoveFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    returnunlinkFirst(f); } /** * delete the tail node ** @returnElement * @throws NoSuchElementException Throws an exception if the list is empty */ public EremoveLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
 }
 
Copy the code

The unlinkFirst and unlinkLast methods are called:

Private E unlinkFirst(Node<E> f) {// Assert f == first && f! = null; // Final E element = f.tem; Final Node<E> next = f.next; // Release the next pointer to the head node, and the element inner class f.tem = null on the next gc; f.next = null; //helpFirst = next; // If the next node is empty, that is, if the list has only one node, last points to nullif (next == null)
        last = null;
    elsenext.prev = null; // Next prev pointer to null size--; // change the list length modCount++; // Modify operandsreturnelement; Private E unlinkLast(Node<E> l) {// Assert l == last && L! = null; final E element = l.item; // Final Node<E> prev = l.prev; L.tem = null; l.prev = null; //helpLast = prev; // When the list has only one node, first points to nullif (prev == null)
       first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
 }
Copy the code

As mentioned above, there are four steps to add nodes in the specified location. Removing the first and last nodes is two special nodes, but overall it is the same. Unlink (node(index))

/** * Unlinks non-null node x. */ E unlink(Node<E> x) { // assert x ! = null; final E element = x.item; Final Node<E> next = x.next; final Node<E> next = x.next; final Node<E> prev = x.prev; // If the node is the head node, do the same as unlinkFirstif (prev == null) {
       first = next;
   } elsePrev. Next = next; // Release the index prev pointer x.rev = null; } // If the node is the last node, the last index points to the last nodeif (next == null) {
       last = prev;
   } else{// Otherwise, the next node prev pointer points to the previous node next-prev = prev; x.next = null; } x.item = null; size--; modCount++;return element;
}
Copy the code

Unlink unlink unlink unlink unlink unlink unlink unlink unlink unlink

Public E remove(int index) {checkElementIndex(index);returnunlink(node(index)); } /** * public Boolean remove(Object o) {// Compare null elements with equals instead of equalsif (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;
}
Copy the code

LinkedList implements the clear operation of the List interface, which is used to delete all nodes of the List:

/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {// Clear the nodes in turn to help free up memoryfor(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

LinkedList Method of querying a node

The methods of LinkedList to query nodes can be divided into three types: query according to the specified index, obtain the head node, and obtain no node. It is worth noting that it is not efficient to obtain node contents by index, so ArrayList is recommended to replace query operations with add and delete operations.

Public E get(int index) {checkElementIndex(index);returnnode(index).item; } /** * returns the contents of the node pointed to by the first index ** @return the first element inThrows NoSuchElementException this list * @throws NoSuchElementException if the list is emptygetFirst() {
   final Node<E> f = first;
   if (f == null)
       throw new NoSuchElementException();
   returnf.item; } /** * returns the contents of the node pointed to by the last index ** @return the last element inThrows NoSuchElementException this list * @throws NoSuchElementException if the list is emptygetLast() {
   final Node<E> l = last;
   if (l == null)
       throw new NoSuchElementException();
   return l.item;
}

Copy the code

Method of modifying nodes for LinkedList

Modifying a node can also be divided into modifying the node content of the specified index and modifying the content of the head node. LinkedList only provides a set(int index, E element) method.

public E set(int index, E element) {// Check whether the corner is out of bounds checkElementIndex(index); // use the node method to find the corresponding index node <E> x = node(index); // Save the original content value E oldVal = x.tem; // Set the new value x.tem = element; // Return the old valuereturn oldVal;
}

Copy the code

The element query method for LinkedList

As we know above, LinkedList provides a way to query nodes by corner tags, and LinkedList also provides a set of methods to determine the position of an element in a LinkedList.

/* * Returns the index of the element's node in the list. If there are duplicate elements, the index is the first identical element from the first node **. If there are no nodes, -1 is returned. * * @param o element to searchfor
* @return*/ public int indexOf(Object o) { int index = 0; // Apply equels to non-empty elementsif (o == null) {
       for(Node<E> x = first; x ! = null; x = x.next) {if (x.item == null)
               returnindex; index++; }}else {
       for(Node<E> x = first; x ! = null; x = x.next) {if (o.equals(x.item))
               returnindex; index++; }}return- 1; } /** ** returns the index of the element in the linked list. If there are duplicate elements, the index is the first identical element from the last node of the element. If there are no nodes of the element, -1 is returned. * * @param o element to searchfor
* @return the index of the last occurrence of the specified element in
*         this list, or -1 if this list does not contain the element
*/
public int lastIndexOf(Object o) {
   int index = size;
   if (o == null) {
       for(Node<E> x = last; x ! = null; x = x.prev) { index--;if (x.item == null)
               returnindex; }}else {
       for(Node<E> x = last; x ! = null; x = x.prev) { index--;if (o.equals(x.item))
               returnindex; }}return- 1; }Copy the code

The two methods return the first node index identical to the parameter element from the beginning node and the first node index identical to the parameter element from the last node, respectively.

In addition to the above two methods we can call contains(Object O) to determine if the element exists in the list. Call indexOf to query the position of the element from the beginning. If =-1, it exists; otherwise, it does not exist

public boolean contains(Object o) {
    return indexOf(o) != -1;
}
Copy the code

LinkedList is added, deleted, and checked as a two-way queue

After analyzing LinkedList as the add, delete, change and check operation of List collection, let’s take a look at how LinkedList implements Deque interface method:

Deque dual-ended queue

Let’s take a look at Java’s two-endided Queue. We know that a Queue is a Queue that follows the FIFO rule, and we know that a Stack is a Stack structure that follows the FILO rule. In other words, the class that implements this interface can be used as either a stack or a queue.

Let’s look at the methods Queue gives us:

The head The head The tail The tail
insert addFirst(e) offerFirst(e) addLast(e) offerLast(e)
remove removeFirst() pollFirst() remveLast() pollLast
To obtain getFirst() peekFirst() getLast() peekLast

Since the Deque interface inherits the Queue interface, when the Deque is used as a Queue (FIFO), you only need to delete the head and add the tail. Let’s review the methods and differences in Queue:

  1. Both offer and add in queues insert an element into the Queue. The difference is that some implementations of queues have size limits on the Queue, so if you want to add a new item to a full Queue, the extra item will be rejected. Calling add() at this point raises an exception, and offer() simply returns false.

  2. The remove() and poll() methods both remove the first element from the queue. Remove () also throws an exception, while poll() returns NULL

  3. Element () and peek() are used to query elements at the head of the queue. When the queue is empty, Element () throws an exception, and peek() returns NULL.

The above method difference is a rule for the corresponding method of the implementation class of Queue, and the implementation of Queue should follow this rule.

Note that a Deque implements a Queue, so all methods of a Queue are available in a Deque. The following is a comparison of the methods used by deques to distinguish queues:

Queue Deque
add(e) addLast()
offer(e) offerLast()
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()

From the above table we can see the methods of Queue corresponding to Deque. How to implement their class LinkedList?

Methods to add elements to a Deque and Queue

Let’s compare the corresponding implementation method:

Public Boolean add(E E) {linkLast(E);return true; } public void addLast(E E) {linkLast(E); } public Boolean offer(E E) {public Boolean offer(E E) {returnadd(e); } public Boolean offerLast(E E) {addLast(E);return true;
}
    
Copy the code

As mentioned above, the difference between Queue offer and Add is for volumetric implementations, and obviously there is no limit to the size of the LinkedList, so their implementations are not substantially different in LinkedList.

Deque and Queue methods to delete elements

RemoveFirst raises NoSuchElement exception public Eremove() {
   returnremoveFirst(); } // Delete the Deque to implement public EremoveFirst() {
   final Node<E> f = first;
   if (f == null)
       throw new NoSuchElementException();
   returnunlinkFirst(f); } // The implementation of Queue removing elements does not throw an exception and returns null public E if the list is emptypoll() {
   final Node<E> f = first;
   return(f == null) ? null : unlinkFirst(f); } // The implementation of Deque does not throw an exception and returns NULL public E if the list is emptypollFirst() {
   final Node<E> f = first;
   return (f == null) ? null : unlinkFirst(f);
}
Copy the code

Deque and Queue get the implementation of the Queue header element

If the Queue is empty, raise the exception public Eelement() {
    returngetFirst(); } // if the queue is empty, throw an exception public EgetFirst() {
   final Node<E> f = first;
   if (f == null)
       throw new NoSuchElementException();
   returnf.item; } // Queue returns null public E when the Queue is emptypeek() {
   final Node<E> f = first;
   return(f == null) ? null : f.item; } // Deque returns null public E when the queue is emptypeekFirst() {
   final Node<E> f = first;
   return (f == null) ? null : f.item;
}
Copy the code

Above, we have analyzed the differences between the methods used in double-endian queues as queues, and we can also see that the implementation of LinkedList for corresponding methods follows queue design principles.

Different from Queue, Stack itself is the implementation class. It has the principle of FILO. The Stack is pushed by method, and the Stack is popped by method. Query operations are performed using the PEEK operation. When used as a stack, the Deque also follows the FILO rule, and is pushed and removed by adding and removing head nodes.

Stack Deque
push(e) addFist(e)
pop() removeFirst()
peek() peekFirst()

Since the queue was analyzed with addFist and removeFirst and peekFirst, let’s show the implementation of push and POP:

public void push(E e) {
   addFirst(e);
}

public E pop() {
   return removeFirst();
}
Copy the code

Wow, there’s no hiding the addFirst and removeFirst methods called directly. There’s nothing left to analyze.

LinkedList traversal

When ArrayList is analyzed, we know that the List implementation class has four traversal methods: for loop, advanced for loop, Iterator method, ListIterator method. Since ArrayList source code was analyzed in detail, we will only look at the differences between linkedLists of different data structures.

LinkedList has no separate Iterator implementation class; both its Iterator and listIterator methods return an object of ListItr. LinkedList as a two-way LinkedList data structure, used to be convenient for the last and next elements.

ListItr ListItr ListItr ListItr ListItr

Private class ListItr implements ListIterator<E> {private Node<E> lastReturned; private class ListItr implements ListIterator<E> {private Node<E> lastReturned; Private Node<E> next; Private int nextIndex; private int nextIndex; Private int expectedModCount = expectedModCount; private int expectedModCount = expectedModCount; ListItr(int index) {// Assert isPositionIndex(index); // Next = null if index == size next = (index == size)? null : node(index); nextIndex = index; } // Check whether pointer can also move public BooleanhasNext() {
       returnnextIndex < size; } // return the next iterated element public Enext() {// Check whether operands are valid checkForComodification(); // If hasNext returnsfalseThrow an exception, so we should call hasNext check before calling nextif(! hasNext()) throw new NoSuchElementException(); // move lastReturned pointer lastReturned = next; // Move next pointer next = next. Next; NextIndex cursor nextIndex++; // Return lastReturned after the movereturnlastReturned.item; } public Boolean specifies whether the cursor position contains the previous elementhasPrevious() {
       returnnextIndex > 0; } // The element preceding the current cursor position is public Eprevious() {
       checkForComodification();
       if(! hasPrevious()) throw new NoSuchElementException(); // same as lastReturned = next; next = (next == null) ? last : next.prev; LastReturned = next = (next == null)? last : next.prev; nextIndex--;return lastReturned.item;
   }
    
   public int nextIndex() {
       return nextIndex;
   }

   public int previousIndex() {
       returnnextIndex - 1; } // Remove the current node that next/previous returns, so lastReturned public voidremove() {
       checkForComodification();
       if(lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; // Call the LinkedList method unlink(lastReturned);if (next == lastReturned)
           next = lastNext;
       elsenextIndex--; LastReturned = null; // The node where the previous operation was performed was left empty. expectedModCount++; } // Set the value of the node being traversed public voidset(E e) {
       if(lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E E) {checkForComodification();} public void add(E E) {checkForComodification(); lastReturned = null;if (next == null)
           linkLast(e);
       elselinkBefore(e, next); nextIndex++; expectedModCount++; } // Whether the operands are legal final voidcheckForComodification() {
       if (modCount != expectedModCount)
           throw new ConcurrentModificationException();
   }
}
Copy the code

Refer to the following figure to understand the three variables of the LinkedList iterator.

conclusion

Starting from the source code of LinkedList, this paper analyzes the common operations of LinkedList collection, as well as the method of adding, deleting, changing and checking when it is used as a queue or stack. ArrayList is the second collection framework source code analysis after the previous one.

Have you ever seen the sun at 3 am in Beijing? No! The sun hasn’t risen yet at three o ‘clock