<> 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,
Final review of database : Summary of comprehensive application questions Laplance operator ( Second derivative ) Simple learning of computer composition principle pyqt Button call python program _PyQt: Link button to function in program How much can you go up once you change jobs ? Today, I saw the ceiling of job hopping python in str Function usage _python in str Usage Summary of built-in functions MySQL trigger web The server nginx---linux Installation and deployment C++ Chapter V polymorphism exercises :( It's coming to an end )python Check built-in functions , How to check python Built in function