โญ Write in front
- This is the way to learn the source code of Wenwen al
- ๐ If it helps you, give the blogger a free praise to encourage QAQ
- ๐ Blog home page ๐ Winwin El learning house
- โญ More articles ๐จ๐ Stay tuned to wenwendell's home page
- ๐ Article release date: December 2021 sixteen
- ๐ java learning road!
- ๐ For more articles, please pay attention to the personal home page!
- ๐ List of popular articles:
- ๐ [source code] super detailed ArrayList underlying source code + classic interview questions
- ๐ HashMap underlying red black tree principle (super detailed diagram) + handwritten red black tree code
- ๐ HashMap underlying source code analysis (super detailed illustration + interview questions)
- ๐ HashMap underlying source code analysis (super detailed illustration)
โญ ๏นฅ 1 inheritance system diagram of LinkedList
You can see from the inheritance system - LinkedList Realized Queue and Deque Interface, so it can be used as List It can also be used as a double ended queue, or even as a - Stack to use - LinkedList Realized Cloneable and Serializable Interface, from which LinkedList Can be cloned and serialized
โญ โ ธ 2 LinkedList source code analysis
โญ โ 2.1 main properties of LinkedList
//size: the number of elements in the linked list transient int size = 0; //first: the head node in the linked list transient Node<E> first; //Last: the last node in the linked list transient Node<E> last;
transient:
Add the keyword transient before the attribute that does not need to be serialized. When serializing an object, this attribute will not be serialized to the specified destination
Therefore, size, first and last will not be serialized
โญ 2.2 LinkedList source code
โญ ๏ธ2.2. 1. LinkedList construction method
Nonparametric structure
public LinkedList() {
}
Parametric structure
//Pass in the Collection collection and add the elements in the Collection collection to the LinkedList Collection
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//Check whether the index is out of bounds
checkPositionIndex(index);
//Convert collection to Object [] array
Object[] a = c.toArray();
//Get the length of the array and record it as numNew
int numNew = a.length;
//If the array length is 0, it proves that there are no elements to add
if (numNew == 0)
return false;
//pred is the precursor node pointer of the set to be spliced, and succ is the successor node pointer of the set to be spliced
Node<E> pred, succ;
//If the index of the position to be inserted is at the end of the linked list
if (index == size) {
//The successor of set c is empty
succ = null;
//The precursor of set c is the tail node of the original linked list
pred = last;
} else {
//node(index) is the node at the index. The successor of the collection to be inserted points to it
succ = node(index);
//The predecessor node of the collection to be inserted points to the previous node of the node where index is located
pred = succ.prev;
}
//Start insertion
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//Create a new node. The precursor of the new node points to the precursor of the node where index is located
Node<E> newNode = new Node<>(pred, e, null);
//If it is empty, it proves that the node to be inserted is at the head of the linked list
if (pred == null)
//The first pointer points to the new node
first = newNode;
else
//Otherwise, the successor of pred points to the new node
pred.next = newNode;
//pred move backward
pred = newNode;
}
//If succ==null, it means that index is at the end of the linked list. Add a collection directly at the end
if (succ == null) {
//The tail pointer points to the tail of the spliced linked list
last = pred;
} else {
//Otherwise, the successor to the tail of the set to be inserted is succ
pred.next = succ;
//The precursor of succ points to the tail of the insertion set
succ.prev = pred;
}
//Linked list capacity + length of set to be inserted
size += numNew;
//Linked list modification times + 1
modCount++;
return true;
}
โญ ๏ธ2.2. 2 method of adding elements
As a double ended queue, LinkedList can add elements from the head of the queue or from the tail of the queue
โญ Add element at the head of the team
public void addFirst(E e) {
//Call the linkFirst method and insert the e element into the linkedlist header
linkFirst(e);
}
private void linkFirst(E e) {
//f record the first node of the queue
final Node<E> f = first;
//Create a new node so that the next of the new node is the first node of the original queue, and the prev of the new node is empty
final Node<E> newNode = new Node<>(null, e, f);
//The new node is the new first node, and the first pointer points to the new node
first = newNode;
//Determine whether the linked list is empty
//If NULL, the tail pointer last points to the new node
//Otherwise, point the prev of the original queue head node to the new node
if (f == null)
last = newNode;
else
f.prev = newNode;
//Linked list capacity + 1
size++;
//The number of times the linked list is modified + 1, indicating that this is a set that supports fail fast
modCount++;
}
โญ Add elements at the end of the queue
public void addLast(E e) {
//Call the linkLast method and insert the e element at the end of linkedlist
linkLast(e);
}
void linkLast(E e) {
//l record queue tail node
final Node<E> l = last;
//Create a new node. The prev of the new node is the end of the original queue, and the next of the new node is empty
final Node<E> newNode = new Node<>(l, e, null);
//The new node is the new tail node, and the tail pointer points to the new node
last = newNode;
//Determine whether there are element nodes in the linked list
//If empty, the new node is the first element of the queue
//Then the header pointer also points to the new node
if (l == null)
first = newNode;
else
//If the linked list is not empty, the next of the original last node points to the new node to add the new node to the linked list
l.next = newNode;
//Linked list capacity + 1
size++;
//The number of times the linked list is modified + 1, indicating that this is a set that supports fail fast
modCount++;
}
โญ ๏นฅ add an element at the specified element location
public void add(int index, E element) {
//Check whether the index is out of bounds
checkPositionIndex(index);
//Determine whether the index is the tail position
if (index == size)
//If the index is the tail position, insert it directly after the tail node
linkLast(element);
else
//Otherwise, in the middle position, call linkBefore to insert the node in the middle position
//node(index) is the node at the current insertion location
linkBefore(element, node(index));
}
//Find the Node at the index location according to the index
Node<E> node(int index) {
//Size > > 1 = size / 2. If index < size / 2, it proves that the node is in the first half of the linked list
if (index < (size >> 1)) {
//Locate the position of the index element from the beginning node
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;//The pointer moves backward until the index is reached
return x;//When the index position is reached, the node node of the position is returned
} else {
//Otherwise, start looking for the index element from the tail node
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;//Before reaching the index, the pointer moves forward
return x;//When the index position is reached, the node node of the position is returned
}
}
//e is the node to be inserted, and succ is the original location node
void linkBefore(E e, Node<E> succ) {
//Find the previous node of the original location node and mark it as pred
final Node<E> pred = succ.prev;
//Create a new node according to e, the prev of the new node is the previous node of the original location node, and the next of the new node is the original location node
final Node<E> newNode = new Node<>(pred, e, succ);
//The leading pointer prev of the original node points to the new node
succ.prev = newNode;
//If succ is the first element of the linked list
if (pred == null)
//Then the first pointer points to the new node, which is the chain header node
first = newNode;
else
//Otherwise, the next of pred is a new node
pred.next = newNode;
//Linked list capacity + 1
size++;
//Linked list modified times + 1
modCount++;
}
โญ ๏ฎ illustration of three ways to add elements
You can see that adding elements at the beginning and end of the queue is very efficient, and the time complexity is O(1)
Adding elements in the middle is inefficient. You need to find the node at the insertion position first, and then modify the front and rear pointers. The time complexity is O(n)
โญ ๏ธ2.2. 3 delete element
As mentioned above, LinkedList implements the Queue and Deque interfaces, so it can be used as a List or as a double ended Queue. As a double ended Queue, it can delete elements from the head of the Queue or from the tail of the Queue. As a List, it can also delete elements from the middle
โญ ๏นฅ delete element from header
public E removeFirst() {
//Get first node
final Node<E> f = first;
//If the first node is empty, the linked list is empty and a NoSuchElementException() exception is thrown
if (f == null)
throw new NoSuchElementException();
//Otherwise, delete the header element
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//Gets the value of the header node, which is used to return
final E element = f.item;
//Obtain the successor node of the first node
final Node<E> next = f.next;
//Set the value of the first node to null
f.item = null;
//Empty the successor of the first node
f.next = null; // The purpose of empty is to facilitate GC garbage collection
//Take the successor of the first node as the new first node
first = next;
//If the linked list is empty after deletion
if (next == null)
//Set last to null
last = null;
else
//Set the precursor of next to null
next.prev = null;
//Capacity of linked list - 1
size--;
//Modification times of linked list + 1
modCount++;
//Returns the deleted element
return element;
}
โญ Delete element from tail
public E removeLast() {
//Get tail node
final Node<E> l = last;
//If the linked list is empty, an exception is thrown
if (l == null)
throw new NoSuchElementException();
//Otherwise, delete the tail element
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
//Gets the value of the tail node
final E element = l.item;
//Get the precursor of the tail node
final Node<E> prev = l.prev;
//Set the value of the tail node to null
l.item = null;
//Leave the precursor of the tail node empty
l.prev = null; //garbage collection
//The precursor of the tail node is used as the new tail node
last = prev;
//If the precursor of the tail node is empty, the linked list is empty and first is empty
if (prev == null)
first = null;
else
//Otherwise, the successor of prev is set to null
prev.next = null;
//Capacity of linked list - 1
size--;
//Number of times the linked list has been modified + 1
modCount++;
//Return the deleted tail node
return element;
}
โญ Delete the specified subscript node
public E remove(int index) {
//Check whether the index is out of bounds. If it is out of bounds, an IndexOutOfBoundsException exception will be thrown
checkElementIndex(index);
//node(index) is the node to be deleted
return unlink(node(index));
}
//Find the Node at the index location according to the index
Node<E> node(int index) {
//Size > > 1 = size / 2. If index < size / 2, it proves that the node is in the first half of the linked list
if (index < (size >> 1)) {
//Locate the position of the index element from the beginning node
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;//The pointer moves backward until the index is reached
return x;//When the index position is reached, the node node of the position is returned
} else {
//Otherwise, start looking for the index element from the tail node
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;//Before reaching the index, the pointer moves forward
return x;//When the index position is reached, the node node of the position is returned
}
}
E unlink(Node<E> x) {
//Get the value of the node (x) to delete
final E element = x.item;
//Obtain the successor node of x
final Node<E> next = x.next;
//Get the precursor node of x
final Node<E> prev = x.prev;
//If the precursor is empty, x is the first node, and the successor of x is the new first node
if (prev == null) {
first = next;
} else {
//Then the next of the precursor points to the successor of x
prev.next = next;
//Empty the front drive of x
x.prev = null;
}
//If the successor is empty, x is the tail node, and the precursor of x is the new tail node
if (next == null) {
last = prev;
} else {
//Otherwise, point the subsequent prev to the precursor of x
next.prev = prev;
//The successor of x is set to null
x.next = null;
}
//After the above two steps, the predecessor and successor of x are empty. Set the value of x to empty for GC garbage collection
x.item = null;
//Capacity of linked list - 1
size--;
//Number of times the linked list has been modified + 1
modCount++;
//Returns the deleted element
return element;
}
โญ Illustration of three methods to delete elements
From this we can know
- When deleting elements, it is efficient to delete elements at the beginning and end of the queue, and the time complexity is O(1)
- It is inefficient to delete elements in the middle. First, stand at the node where they are deleted, and then modify the front and back pointers. The time complexity is O(n)
โญ โ ถ 3 Summary
- LinkedList Is a double linked list to achieve List๏ผ - LinkedList It is also a double ended queue, which has the characteristics of queue, double ended queue and stack; - LinkedList Adding and deleting elements at the beginning and end of the queue is very efficient, and the time complexity is O(1)๏ผ - LinkedList Adding and deleting elements in the middle is inefficient, and the time complexity is O(n)๏ผ - LinkedList Random access is not supported, so it is inefficient to access non queue elements; - LinkedList Functionally equal to ArrayList + ArrayDeque๏ผ
- This is the way to learn the source code of Wenwen al
- ๐ If it helps you, give the blogger a free praise to encourage QAQ
- ๐ Blog home page ๐ Winwin El learning house
- โญ More articles ๐จ๐ Stay tuned to wenwendell's home page
- ๐ Article release date: December 2021 sixteen
- ๐ java learning road!
- ๐ For more articles, please pay attention to the personal home page!
- ๐ List of popular articles:
- ๐ [source code] super detailed ArrayList underlying source code + classic interview questions
- ๐ HashMap underlying red black tree principle (super detailed diagram) + handwritten red black tree code
- ๐ HashMap underlying source code analysis (super detailed illustration + interview questions)
- ๐ HashMap underlying source code analysis (super detailed illustration)
