Art is long, life is long
Click the link below to view the corresponding chapter:
[Dead knock Java collection] – ArrayList source analysis
CopyOnWriteArrayList source code analysis
[Deadknock Java collection] – Source analysis of HashMap
The problem
(1) Is LinkedList just a List?
(2) What other features does LinkedList have?
(3) Why is LinkedList often compared to ArrayList?
(4) Why did I put My LinkedList in the last chapter?
Introduction to the
LinkedList is a List implemented as a two-way LinkedList. It can also be used as a queue or stack. Let’s study together.
Inheritance system
Through inheritance, we can see that LinkedList implements not only the List interface, but also the Queue and Deque interface, so it can be used as a List, as a dual-ended Queue, and of course as a stack.
Source code analysis
The main properties
// Number of elements
transient int size = 0;
// the first node of the list
transient Node<E> first;
// The end of the list
transient Node<E> last;
Copy the codeThe attribute is simple and defines the number of elements size and the first and last nodes of the list.
Main inner class
Typical double-linked list structure.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeMain construction methods
public LinkedList(a) {}public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }Copy the codeThe two constructors are also simple, as you can see from an unbounded queue.
Add elements
As a double-ended queue, there are two main ways to add elements, one is to add elements at the end of the queue, and the other is to add elements at the head of the queue. These two forms are mainly implemented in the LinkedList through the following two methods.
// Add an element from the head of the queue
private void linkFirst(E e) {
/ / the first node
final Node<E> f = first;
// Create a new node, next of which is the first node
final Node<E> newNode = new Node<>(null, e, f);
// make the new node the new first node
first = newNode;
// Determine if the element is the first to be added
// If so, set last to the new node
// Otherwise, set the prev pointer of the original first node to the new node
if (f == null)
last = newNode;
else
f.prev = newNode;
// The number of elements increases by 1
size++;
// The number of changes added by 1 indicates that this is a fail-fast set
modCount++;
}
// Add elements from the end of the queue
void linkLast(E e) {
// End of queue
final Node<E> l = last;
// Create a new node whose prev is the tail node
final Node<E> newNode = new Node<>(l, e, null);
// Make the new node the new tail node
last = newNode;
// Determine if the element is the first to be added
// If yes, set first as the new node
// Otherwise, set the next pointer to the last node to the new node
if (l == null)
first = newNode;
else
l.next = newNode;
// The number of elements increases by 1
size++;
// The number of changes is increased by 1
modCount++;
}
public void addFirst(E e) {
linkFirst(e);
}
public void addLast(E e) {
linkLast(e);
}
// As an unbounded queue, adding elements always succeeds
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
Copy the codeTypical double-linked lists add elements at the beginning and end of the method, the code is relatively simple, here is not described in detail.
As a double-ended queue, it has the first and last elements to add to it, but as a List?
As a List, it is necessary to support adding elements in the middle, mainly through this method.
// Add elements before node succ
void linkBefore(E e, Node<E> succ) {
// succ is the successor of the node to be added
// Find the front node of the node to be added
final Node<E> pred = succ.prev;
// Create a new node between its front node and its successor
final Node<E> newNode = new Node<>(pred, e, succ);
// Modify the leading pointer to the new node
succ.prev = newNode;
// Check whether the front node is empty
// If it is null, it is the first element to be added
// Otherwise, change next of the front node to the new node
if (pred == null)
first = newNode;
else
pred.next = newNode;
// Change the number of elements
size++;
// The number of changes is increased by 1
modCount++;
}
// Find the index node
Node<E> node(int index) {
// Because it is doubly linked
// So whether the index is in the first half or the second half determines whether the index is traversed from the front or back
// So that the index traverses half of the elements in the second half
if (index < (size >> 1)) {
// If it is in the first half
// Just go through it before
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// If it is in the second half
// go from the back
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
returnx; }}// Add the element at the specified index position
public void add(int index, E element) {
// Determine if the boundary is crossed
checkPositionIndex(index);
// If index is a position after the last node of the queue
// Add the new node directly after the last node
// Otherwise call linkBefore() to add nodes in the middle
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
Copy the codeThe way to add elements in the middle is also very simple, the way to add elements in the middle of a typical double-linked list.
The three ways to add elements are roughly as shown below:
Adding elements at the beginning and end of the queue is efficient, with O(1) time.
It is inefficient to add elements in the middle. First, the node at the insertion position should be found, and then the pointer of the before and after nodes should be modified. The time complexity is O(n).
Remove elements
As a double-ended queue, there are two ways to delete elements, one is to delete elements at the beginning of the queue, the other is to delete elements at the end of the queue.
As a List, you need to support intermediate deletion of elements, so there are three methods for deleting elements, respectively as follows.
// Delete the first node
private E unlinkFirst(Node<E> f) {
// The element value of the first node
final E element = f.item;
// Next pointer to the first node
final Node<E> next = f.next;
// Add the contents of the first node to assist GC
f.item = null;
f.next = null; // help GC
// make next of the first node as the new first node
first = next;
// If there is only one element, delete it and set last to null
// Otherwise, set next's leading pointer to null
if (next == null)
last = null;
else
next.prev = null;
// The number of elements is reduced by 1
size--;
// The number of changes is increased by 1
modCount++;
// Returns the deleted element
return element;
}
// Delete the tail node
private E unlinkLast(Node<E> l) {
// The element value of the last node
final E element = l.item;
// The leading pointer to the tail node
final Node<E> prev = l.prev;
// Clear the contents of the tail node to assist GC
l.item = null;
l.prev = null; // help GC
// Make the front node the new tail node
last = prev;
// If there is only one element, delete and set first to null
// Otherwise, empty next for the front node
if (prev == null)
first = null;
else
prev.next = null;
// The number of elements is reduced by 1
size--;
// The number of changes is increased by 1
modCount++;
// Returns the deleted element
return element;
}
// Delete node X
E unlink(Node<E> x) {
// The element value of x
final E element = x.item;
// The front node of x
final Node<E> next = x.next;
// the post-node of x
final Node<E> prev = x.prev;
// If the front node is empty
// specify the first node, so that first points to the node after x
// Otherwise change next of the front node to the back node of x
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// If the back node is empty
// Last points to the front node of x
// Otherwise, change the prev of the rear node to the front node of X
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// Empty the element value of x to assist GC
x.item = null;
// The number of elements is reduced by 1
size--;
// The number of changes is increased by 1
modCount++;
// Returns the deleted element
return element;
}
// remove throws an exception if no element is present
public E removeFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// remove throws an exception if no element is present
public E removeLast(a) {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
// poll returns null if there are no elements
public E pollFirst(a) {
final Node<E> f = first;
return (f == null)?null : unlinkFirst(f);
}
// poll returns null if there are no elements
public E pollLast(a) {
final Node<E> l = last;
return (l == null)?null : unlinkLast(l);
}
// Delete the intermediate node
public E remove(int index) {
// Check for overbounds
checkElementIndex(index);
// Delete the index node
return unlink(node(index));
}
Copy the codeThe three methods for deleting elements are typical double-linked list deletion methods, and the general process is shown in the following figure.
[
Removing elements at the beginning and end of the queue is efficient and takes O(1) time.
It is inefficient to delete elements in the middle. First, it is necessary to find the node at the deleted position, and then modify the pointer before and after. The time complexity is O(n).
The stack
Earlier we said that LinkedList is a two-ended queue, remember that a two-ended queue can be used as a stack?
Example:
package org.example.test;
import java.util.LinkedList;
/** * use LinkedList to simulate the characteristics of stack */
public class Test12 {
private LinkedList<String> linkList = new LinkedList<String>();
/ / pressure stack
public void push(String str){
linkList.addFirst(str);
}
/ / out of the stack
public String pop(a){
return linkList.removeFirst();
}
/ / check
public String peek(a){
return linkList.peek();
}
// Check whether it is null
public boolean isEmpty(a){
returnlinkList.isEmpty(); }}class Test13 {
public static void main(String[] args) {
/ / test stack
Test12 test12 = new Test12();
test12.push("I was the first one in.");
test12.push("I was the second one to go in.");
test12.push("I was the third one to go in.");
test12.push("I was the fourth to go in.");
test12.push("I was the fifth to go in.");
/ / remove
while(! test12.isEmpty()){ String pop = test12.pop(); System.out.println(pop); }// Print the result
/* I was the fifth in, I was the fourth in, I was the third in, I was the second in, I was the first in */}}Copy the codeThe stack feature is LIFO(Last In First Out), so it is easy to use as a stack, adding and removing elements only operate on the First node of the queue.
conclusion
(1) LinkedList is a List implemented as a double-linked List;
(2) LinkedList is also a double-ended queue, which has the characteristics of queue, double-ended queue and stack;
(3) The LinkedList is very efficient in adding and deleting elements at the beginning and end of the queue, and the time complexity is O(1);
(4) Adding and deleting elements in the middle of LinkedList is inefficient, and the time complexity is O(n);
(5) LinkedList does not support random access, so accessing non-queue elements is inefficient;
(6) LinkedList is functionally equal to ArrayList + ArrayDeque.
The last
Author: Tong Brother
Reference: www.cnblogs.com/tong-yuan/