<> One , introduction

<>1. concept

*
LinkedList It is based on linked list , So let's explain what a linked list is . The linked list was originally C/C++ The concept of , It is a linear storage structure , This means that the data to be stored is stored in a storage unit , In addition to storing the data to be stored in this storage unit , It also stores the address of its next storage unit ( The address of the next storage location is necessary , Some storage structures also contain the address of the previous storage unit ), Every time you look up the data , Find the storage unit after the address of the next storage unit in a storage unit .
* understand :
* LinkedList It's a two-way linked list
* in other words list Each element in , In addition to storing its own value , still The addresses of its previous and subsequent elements are additionally stored , therefore It is easy to get the elements before and after the current element
* The last node of the tail element of the list is the head node of the list ; The first node of the list is the last node of the list ( Is it a bit like a snake in the end Head to tail , Brain tonic )
* Since it is a two-way linked list , Then there must be a basic storage unit , Let's see LinkedList The most basic storage unit of . // A private inner class private
static class Node<E> { E item; // Real stored data Node<E> next; // Previous node reference address Node<E>
prev; // The next node refers to the address Node(Node<E> prev, E element, Node<E> next) { this.item =
element; this.next = next; this.prev = prev; } }
Illustration :

<>2. Gathering points

main points explain
Can it be blank sure
Is it in order Order
Can it be repeated Allow repetition
Is thread safe Thread unsafe
<> Two , analysis

<>1. Class inheritance structure diagram

<>2. attribute
// LinkedList Number of nodes transient int size = 0; /** * Pointer to first node. Point to head node
* Invariant: (first == null && last == null) || * (first.prev == null &&
first.item != null) */ transient Node<E> first; /** * Pointer to last node.
Point to tail node * Invariant: (first == null && last == null) || * (last.next == null &&
last.item != null) */ transient Node<E> last;
<>3. Constructor

<>3.1 Null parameter constructor
public LinkedList() { }
<>3.2 collection Parameter constructor
public LinkedList(Collection<? extends E> c) { this(); // Add to set
addAll(c); } public boolean addAll(Collection<? extends E> c) { // Set elements from the tail of the list
return addAll(size, c); } public boolean addAll(int index, Collection<? extends
E> c) { // 1. Rationality check for adding Subscripts checkPositionIndex(index); // 2. Convert collection to Object[] Array object
Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false;
// 3. The previous node and the subsequent node of the insertion position are obtained Node<E> pred, succ; if (index == size) { //
Add from tail : The predecessor node is the original last node ; The successor node is null succ = null; pred = last; } else { //
From the specified location ( Non tail ) Added cases : The preceding node is index Node of location , The successor node is index Location of the node before the node succ = node(index); pred
= succ.prev; } // 4. Traversing data , Insert data into for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o; // Create node Node<E> newNode = new
Node<>(pred, e, null); if (pred == null) // Insertion of empty linked list : first = newNode; else //
Insertion of non empty linked list : pred.next = newNode; // Update the front node to the latest inserted node ( Address of ) pred = newNode; } if
(succ == null) { // If it's inserted from the tail , Then last Set as last inserted element last = pred; } else { //
If it's not inserted from the tail , Then connect the tail data with the previous node pred.next = succ; succ.prev = pred; } size +=
numNew; // List size +num modCount++; // Modification times plus 1 return true; }
The data structure of linked list is like this :

All element operations are based on such a data structure , You can probably fill the brain , It's easy to understand .

because LinkedList That's it List Interface , Again Deque Interface , therefore LinkedList You can add the element to the tail , You can also add elements to the specified index location , You can also add an entire collection ; In addition, you can add , It can also be added at the end . So the following points list Interface implementation and deque Interface implementation to analyze .

<>4.List Interface

<>4.1 add(E e) method
// effect : Add the element to the end of the list public boolean add(E e) { linkLast(e); return true; } void
linkLast(E e) { final Node<E> l = last; // Get tail element final Node<E> newNode = new
Node<>(l, e, null); // Create a new node with the tail element as the preceding node last = newNode; // Update the tail node to the node to be inserted if
(l == null) // If the list is empty : Update at the same time first The node is also the node to be inserted .( in other words : This node is both the head node first It's also the tail node last)
first = newNode; else // It is not an empty linked list : Change the original tail node ( Now it's the penultimate node ) Of next Point to the node to be inserted l.next =
newNode; size++; // Update linked list size and modification times , Insert completed modCount++; }
<>4.2 add(int index, E element) method
// effect : Adds an element at the specified location public void add(int index, E element) { // Check the rationality of the index at the insertion position
checkPositionIndex(index); if (index == size) //
The case of insertion is the case of tail insertion : call linkLast() Explain above . linkLast(element); else //
The case of insertion is the case of non tail insertion ( Insert in the middle ):linkBefore() See below . linkBefore(element, node(index)); }
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw
new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean
isPositionIndex(int index) { return index >= 0 && index <= size; } void
linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred =
succ.prev; // Get the preceding node of the insertion position element final Node<E> newNode = new Node<>(pred, e, succ);
// Create a new node , Its predecessor node is succ Front node of , The back contact is succ node succ.prev = newNode; //
Update insertion position (succ) The new node is the front node if (pred == null) //
If pred by null, Indicates that the node is inserted before the head node , To reset first Head node first = newNode; else //
If pred Not for null, Then directly pred The following pointer to newNode that will do pred.next = newNode; size++; modCount++;
}
<>4.3 get(int index) method
public E get(int index) { // Rationality check of the following table of elements checkElementIndex(index); //
node(index) Actually query the matching elements and return return node(index).item; } // effect : Query the specified location element and return Node<E>
node(int index) { // assert isElementIndex(index); // If the index position is near the first half of the list , Traverse from scratch if
(index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x =
x.next; return x; } else { // If the index position is near the second half of the list , Traverse from tail Node<E> x = last; for (int i
= size - 1; i > index; i--) x = x.prev; return x; }
<>4.4 remove(int index) method
// effect : Removes the element at the specified location public E remove(int index) { // Remove rationality check for element index
checkElementIndex(index); // Delete node return unlink(node(index)); } E
unlink(Node<E> x) { // assert x != null; final E element = x.item; // Gets the value of the specified node
final Node<E> next = x.next; // Get the successor node of the specified node final Node<E> prev = x.prev; //
Get the predecessor node of the specified node // If prev by null Indicates that the deletion is the head node , Otherwise, it's not the head node if (prev == null) { first = next; }
else { prev.next = next; x.prev = null; // Empty the front node of the specified node to be deleted (null) } //
If next by null, Indicates that the tail node is deleted , Otherwise, it's not the tail node if (next == null) { last = prev; } else {
next.prev = prev; x.next = null; // Empty the post node of the specified node to be deleted } // Empty the value of the specified node to be deleted x.item =
null; size--; // Quantity reduction 1 modCount++; return element; }
<>4.5 clear() method
// Empty list 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 // conduct for loop , Empty one by one ; Until the last element for (Node<E> x = first; x !=
null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x
= next; } // Short and tail null first = last = null; size = 0; modCount++; }
<>4.6 indexOf(Object o)
// Returns the index of the element in the linked list , If not, return -1 public int indexOf(Object o) { int index = 0; //
If the element is null, Make the following circular judgment if (o == null) { for (Node<E> x = first; x != null; x =
x.next) { if (x.item == null) return index; index++; } } else { //
Element is not null. Make the following circular judgment for (Node<E> x = first; x != null; x = x.next) { if
(o.equals(x.item)) return index; index++; } } return -1; }
<>5. Duque Interface

<>5.1 addFirst(E e) method
// effect : Inserts the specified element into the chain header public void addFirst(E e) { linkFirst(e); } private void
linkFirst(E e) { final Node<E> f = first; // Get header element final Node<E> newNode = new
Node<>(null, e, f); // Create a new header element ( The original head element becomes the second ) first = newNode; //
The head of the list is empty ,( In other words, the linked list is empty ) if (f == null) last = newNode; // The head and tail elements are both e else f.prev =
newNode; // Otherwise, the original header element is updated prev Address reference for the new element size++; modCount++; }
<>5.2 addLast(E e) method
// effect : Add an element to the end of the list e public void addLast(E e) { // It has been explained above , See above .add() method
linkLast(e); }
<>5.3 push(E e) method
// effect : Add element to chain header e public void push(E e) { addFirst(e); }
<>5.4 getFirst() method
// effect : Get the head element public E getFirst() { final Node<E> f = first; if (f == null)
throw new NoSuchElementException(); return f.item; }
<>5.5 getLast() method
// effect : Get the tail element public E getLast() { final Node<E> l = last; if (l == null)
throw new NoSuchElementException(); return l.item; }
<>5.6 peek() method
// effect : Return header element , And do not delete . If it doesn't exist, it's good , return null public E peek() { final Node<E> f = first;
return (f == null) ? null : f.item; }
<>5.7 peekFirst() method
// effect : Return header element , And do not delete . If it doesn't exist, it's good , return null public E peekFirst() { final Node<E> f =
first; return (f == null) ? null : f.item; }
<>5.8 peekLast() method
// effect : Returns the tail element , If null, Then return null public E peekLast() { final Node<E> l = last;
return (l == null) ? null : l.item; }
<>5.9 poll() method
// effect : Returns the head node element , And delete the head node . And set the next node as the head node . public E poll() { final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f); }
<>5.10 pollFirst() method
// effect : Return to head node , And delete the head node , And set the next node as the head node . public E pollFirst() { final Node<E> f =
first; return (f == null) ? null : unlinkFirst(f); }
<>5.11 pollLast() method
// effect : Back to tail node , And delete the tail node , And set the previous node of the tail node as the tail node public E pollLast() { final Node<E> l =
last; return (l == null) ? null : unlinkLast(l); }
<>5.12 pop() method
// effect : Delete head node , If the head node is null. An exception is thrown public E pop() { return removeFirst(); } public
E removeFirst() { final Node<E> f = first; if (f == null) throw new
NoSuchElementException(); return unlinkFirst(f); }
<>5.13 push(E e) method
// effect : Add element to header public void push(E e) { addFirst(e); } public void addFirst(E
e) { linkFirst(e); } private void linkFirst(E e) { final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null)
last = newNode; else f.prev = newNode; size++; modCount++; }
<> Three , ending

<>1.LinkedList and ArrayList The difference between

*
Speed of sequential insertion ArrayList It will be faster ,LinkedList It's a little slower . because ArrarList Just assign a value in the specified position , and LinkedList You need to create Node object , And you need to establish a context , If the object is large , Slow it down .
* Based on the above understanding LinkedList It takes up more memory space .
*
How to traverse the array ArrayList Recommended for loop , and LinkedList It is recommended to use foreach, If used for loop , Efficiency will be slow .( There will be a separate article later , Now remember the conclusion )
* Generally we think so :ArrarList Query and access fast , Slow modification and deletion ;LinkedList Modify and delete fast , Slow query and access . In fact, it is not accurate to say so .
LinkedList Insert , When deleting , Slow addressing , Fast before and after just changing Entry Reference address of ;
ArrayList Insert , When deleting , Slow in the batch of array elements copy, Fast addressing .

therefore , If to be inserted , The deleted elements are in the first half of the data structure, especially in the very front position ,LinkedList Will be much faster ArrayList, because ArrayList Will batch copy A lot of elements ; More and more back , about LinkedList Come on , Because it's a two-way linked list , So in the first 2 Insert a data after elements and in the penultimate 2 There is no difference in the efficiency of inserting an element after an element , however ArrayList Due to the need for batch copy Less and less elements , Operation speed must catch up with or even exceed LinkedList.

<>2. How to choose in actual development ?

1, If you're absolutely sure you insert , The deleted element is in the first half , use LinkedList
2, If you're absolutely sure you delete it , Second half of deleted element , use ArrayList
3, If you're not sure about the two points above , It is recommended that you use LinkedList

explain : firstly ,LinkedList Insert as a whole , The execution efficiency of deletion is relatively stable , No, ArrayList It's going to get faster and faster ; second , When inserting elements , It's not good ArrayList There is going to be an expansion , and ArrayList The expansion of the underlying array is a time-consuming and space consuming operation , So in a comprehensive way, we can know which type to choose list

<>3. Version Description

* The source code here is JDK8 edition , Different versions may vary , But the basic principles are the same .
<>4. Review and reflection

* Or that sentence : Think again about the four objectives of learning the source code and the specific content above , Is there a sense of sudden enlightenment !!!

Technology
©2019-2020 Toolsou All rights reserved,
Hundreds of millions of locusts rarely collide Locusts want to be self driving Heroes Share has surpassed Ningde Era !LG Chemical confirmation to spin off battery business unit TypeScript Data types in is enough Python Garbage collection and memory leak msf Generate Trojan horse attack android mobile phone Element-UI Implementation of secondary packaging TreeSelect Tree drop-down selection component element-ui+vue-treeselect Verification of drop down box Spring Boot Lesson 16 :SpringBoot Implementation of multithreading with injection class A guess number of small games , use JavaScript realization Unity3D Input Key system