Focus on the source code of LinkedList

1. From the underlying data structure, expansion strategy
2. LinkedList additions, deletions and changes
3. Special processing focuses on attention
4. Traversal speed, random access and iterator access efficiency comparison

1. From the underlying data structure, expansion strategy

The constructor does not do For any operation, as long as the data is initialized when adding again, the logic is driven by the operation, and the linkedlist is a doubly linked list, so it can be traversed forward and backward in both directions.
Because the constructor does not have any operations, in fact, we can look at it first. New operation, and because it is a linked list, it cannot be accessed randomly. Random reading here will be slower

?

The underlying structure is the size, the first node, the last node, and the commonality that a List has modCount, this value is used to record how many times this list has been modified

2. LinkedList addition, deletion, modification check

2.1 add operation, linklast

The essence of the Add operation is to perform the linklast operation

The operation of linklast is to add the node to the end at the end and correct the size

< img alt="Share a picture" src="/wp-content/uploads/images/os/data-structure/1626797652157.png" >

 public boolean add(E ele) {

 linkLast(ele);

 return true;

 }

Let’s see if the operation is to insert an element at a specified position.
First, confirm the index and then specify the range
There is a small optimization here. If it is added at the end, we can directly call linklast.
If it is not the last one, then first get the node node at the specified location, when we traverse the specified location< br>You can determine the position of the index if it is more than halfway, then from back to front, if it is not more than half, then from front to back
1. Create a node directly again index, and then merge it back and forth
2. The node at the index position is disconnected, let the pre of this node point to the new node
3. Determine whether the pre-node is at the end, it is empty
4. Point the next of the pre-node to the new node

< p> First look at the node positioning operation

Then we look at linkbefore, insert before

public void linkBefore(E e, Node succ) {

 final Node pred = succ.prev;

 final Node newNode = new Node< >(pred, e, succ);

 succ.prev = newNode;

 if (pred == null)

 first = newNode;

 else

 pred.next = newNode;

 size++;

 modCount++;

 }

Then we need to insert into the specified position method can be very simple to achieve
Linkbefore(e, node(index)) ie Yes

2.2 Delete

View the source code, compare remove(), remove(object), remove(index) and other operations. In the final analysis, it is still an unlink operation.
We need to unlink the specified node Operation
Just two steps of operation
1. The previous node of the current node points to the next node of the current node, to put it plainly node.pre.next = node.next;
2. The next node of the current node The preceding node points to the previous node of the current node: node.next.pre = node.pre;
The other details are the processing of the first and last nodes

public E unlink(Node node) {

 // assert x != null;

 // Here are three nodes, the front node , Current node, post node

 final E element = node.item;

 final Node prev = node.prev;

 final Node next = node.next;



 //The previous node of the current node points to the next one of the current node Node, to put it plainly node.pre.next = node.next;

 if (prev == null) {

 //Avoid first node operations

 first = next;

} else {

 prev.next = next;

 node.prev = null; //Disconnect the original connection

}



 //The previous node of the next node of the current node points to the current The previous node of the node: node.next.pre = node.pre;

 if (next == null) {

 last = prev;

} else {

 next.prev = prev;

 node.next = null;

}



 //Clear current node

 node.item = null;

 size--;

 modCount++;

 return element;

 }

The rest of the operation is basically to call the unlink method to operate

Not much to modify set and get get, just pay attention to the time of set operation , Will return the old value, and these two operations will not modify the modCount value, which means that the linked list will not change

3. Special processing focuses on, iterator, serialization< /h2>

Not much to say about iterator, in fact, it is still calling the above methods, traversal is the same as next and pre and loop traversal
But note that it is possible to perform remove and add through iterators, but note that if you use iterators to pass remove or add operations, and also use general remove and add then it will invalidate the iterator

Serialization Here we only do an understanding, and the subsequent chapters will specifically learn about java serialization:

When serialization and deserialization are performed, the virtual machine first tries to call the object In the writeObject and readObject methods, user-defined serialization and deserialization are performed. If there is no such method, the defaultWriteObject method of ObjectOutputStream and the defaultReadObject method of ObjectInputStream are called by default. In other words, with the custom writeObject method and readObject method, users can control the serialization and deserialization process by themselves.
———————
Copyright statement: This article is the original article of the CSDN blogger “zthgreat”, following the CC 4.0 by-sa copyright agreement , Please attach a link to the original source and this statement for reprinting.
Original link: https://blog.csdn.net/u014634338/article/details/78165127

4. The speed of traversal, Random access and iterator access efficiency comparison

This problem can actually be discarded. The essence of traversal here is to use the traversal method of linked list to traverse.

/p>

5. Do you support multi-threading?

LinkedList is thread-unsafe and allows a doubly linked list with null elements.

Reference: https://blog.csdn.net/u014634338/article/details/78165127

 public boolean add(E ele) {

 linkLast(ele);

 return true;

 }

public void linkBefore(E e, Node succ) {

 final Node pred = succ.prev;

 final Node newNode = new Node< >(pred, e, succ);

 succ.prev = newNode;

 if (pred == null)

 first = newNode;

 else

 pred.next = newNode;

 size++;

 modCount++;

 }

public E unlink(Node node) {

 // assert x != null;

 // Here are three nodes, the front node , Current node, post node

 final E element = node.item;

 final Node prev = node.prev;

 final Node next = node.next;



 //The previous node of the current node points to the next one of the current node Node, to put it plainly node.pre.next = node.next;

 if (prev == null) {

 //Avoid first node operations

 first = next;

} else {

 prev.next = next;

 node.prev = null; //Disconnect the original connection

}



 //The previous node of the next node of the current node points to the current The previous node of the node: node.next.pre = node.pre;

 if (next == null) {

 last = prev;

} else {

 next.prev = prev;

 node.next = null;

}



 //Clear current node

 node.item = null;

 size--;

 modCount++;

 return element;

 }