LinkedList source – Add source code analysis

LinkedList overview

LinkedList is an implementation class of List that belongs to a Collection of collections. LinkedList is an abstract class that inherits AbstractSequentialList. The List, Deque, Cloneable, java.io.Serializable interfaces are also implemented, so LinkedList has serialization and cloning features. The data structure underlying LinkedList implementation is a bidirectional LinkedList (implements the Deque interface)

LinkedList is added, deleted, modified and checked just like a two-way list

Let’s start with the Add method for LinkedList

The Add method

Source:

First enter the source code of the linkLast method it calls, as shown in the figure:

First, assign the element last to Node. The definition of last can be seen in the following figure:

Last node is transient, indicating that this node will not be serialized. Linked list operations are based on the node

Let’s look at how this Node is defined in LinkedList, as shown below:

This is an inner class defined in Linkedlist. There are three variables: item, Next, and prev. Item represents the element to be added, next represents the reference to the next node, and prev represents the reference to the previous node.

Among them, the constructor of the incoming parameters are respectively on a node, the node of the element, and the next node, when add a new element, the last node is the newly added nodes of precursor, because of the added element is the whole list the last element, so his successor nodes is set to null, We then assign the address of this new node to last, indicating that the current new node is the last node in the list. If last is null at the beginning, indicating that there are no elements and there is no list, the new node will be assigned to first.

As shown in the figure, the first node is also transient, indicating that it is not serializable. Indicates that the current new node is the head node. If it is not null, the new node is assigned to the next node of last node and represents the successor node of last node. After that,size++,size is initially initialized to 0, as shown:

After that, the ++ operation is performed for each additional element, which makes it easy to count how many elements there are in the list. ModCount ++, modCount, modCount, modCount, modCount, modCount

ModCount field analysis

ModCount is set to 0 at the beginning, and after that, I ++ operation will be performed for each operation of the linked list. This is a status field, which is used to record the change mark of the table, so we only need to compare this field before and after to know whether the middle time table has been changed. The common feature here is that all modCount attributes are thread unsafe, indicating that this field is mainly used for thread safety. When an iterator is initialized, it is given the expectedModCount of the object that calls the iterator. During the iterator traversal, Whenever you find that the modCount is different from the expectedModCount stored in the iterator you throw an exception. This is a mechanism called fail-fast and that’s what the modCount field is for.

If the element is added, a ture is returned to inform the caller that the element has been added to the list, and the add operation is complete.