1 LinkedList brief introduction
LinkedList It's an implementation <font color="red">List Interface </font> and <font color="red">Deque Interface </font> Of <font color="red"> Double ended linked list </font>.
<img src="https://img-blog.csdnimg.cn/20201108105348736.png" />
LinkedList Inherited from AbstractSequentialList, Realized List、 Deque、 Cloneable、java.io.Serializable Interface .
LinkedList Realized List Interface , It shows that it can insert and delete the linked list efficiently .LinkedList Realized Deque Interface , That can be LinkedList Used as a double-ended queue .LinkedList It's done Cloneable Interface , That overrides the function clone(), Be able to clone .LinkedList Realized java.io.Serializable Interface , It means LinkedList Support serialization , Can transmit data through serialization .
LinkedList Not thread safe , If you want to make LinkedList Become thread safe , Static classes can be called Collections Class synchronizedList Method
List list=Collections.synchronizedList(new LinkedList(...));
2 Member attribute
// Total nodes
transient int size = 0;
// Head node
transient Node<E> first;
// Tail node
transient Node<E> last;You can find LinkedList It is based on bidirectional linked list , Use Node Store linked list node information .
private static class Node<E> {
E item;// Node values
Node<E> next;// The subsequent nodes
Node<E> prev;// Precursor node
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}therefore LinkedList The structure is as follows ：
3 Construction method
// The construction method of empty parameter , Only objects are generated
public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
// First construct an empty linked list
this();
// add to Collection The elements in
addAll(c);
}4 Common methods
4.1 Additive elements
add(E e) ： Add elements to the end of the list
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Linking makes e As the last element .
*/
void linkLast(E e) {
// Find the current tail node
final Node<E> l = last;
// Build new nodes , The precursor node of this node is the last tail node
final Node<E> newNode = new Node<>(l, e, null);
// The newly created node is used as the end node of the current linked list
last = newNode;
if (l == null)
first = newNode;// If the tail node is empty , So the list is empty , Then take the newly built node as the head node
else
l.next = newNode;// If it's not empty , Then set the post node of the tail node before adding as our new tail node
size++;
modCount++;
}add(int index,E e)： Add the element in the specified position
public void add(int index, E element) {
checkPositionIndex(index);// Check index index Is it in [0-size] Between
if (index == size)
linkLast(element);// Add to the end of the list
else
linkBefore(element, node(index));// Insert into index In front of the node of the indicated position
}
/**
* Insert a new node in front of the specified node
*/
void linkBefore(E e, Node<E> succ) {
// Take out the previous node at the specified location
final Node<E> pred = succ.prev;
// Build new nodes ,pred The precursor node of the specified location ,succ The specified location ,e It's the added element
final Node<E> newNode = new Node<>(pred, e, succ);
// The predecessor node of the specified node points to the node to be inserted .
succ.prev = newNode;
// If the predecessor node of the specified location is empty , That is, the designated location succ It's the head node , namely newNode Set as head node
if (pred == null)
first = newNode;
else
pred.next = newNode; // Not empty , The post node of the previous node in the original position is set as the new node .
size++;
modCount++;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;// Check index index Is it in [0-size] Between
}addAll(Collection c )： Insert the collection elements into the linked list
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 1、 Check index Whether the scope is in size within
checkPositionIndex(index);
// 2、 Save the data of the set in the object array
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
// 3、 The precursor node and successor node of the insertion position are obtained
Node<E> pred, succ;
// If the insertion position is tail , The precursor node is last, The subsequent nodes are null
if (index == size) {
succ = null;
pred = last;
}
// otherwise , call node() Method to get the successor node , And then we get the precursor node
else {
succ = node(index);
pred = succ.prev;
}
// 4、 Traversing data and inserting data into
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// Create a new node
Node<E> newNode = new Node<>(pred, e, null);
// If the insertion position is at the head of the list
if (pred == null)
// Point the previous node backward newNode
first = newNode;
else
pred.next = newNode;
// stay if-else outside , If there is no such sentence ,pred A node is a fixed node , So the nodes need to be replaced in each cycle
pred = newNode;
}
// If the insertion position is at the tail , Reset last node
if (succ == null) {
last = pred;
}
// The inserted list is linked to the previous list
else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
} addFirst(E e)： Add elements to the head of the list
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
// Find the current head node
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);// The new node , Take the front node as the successor node
// The new node is the head node
first = newNode;
// If the list is empty ,last Nodes also point to new nodes
if (f == null)
last = newNode;
// otherwise , Point the leading pointer of the preceding node to the new node , That is to say, the next element
else
f.prev = newNode;
size++;
modCount++;
}addLast(E e)： Add elements to the end of the list , And add(E e) The method is the same
public void addLast(E e) {
linkLast(e);
}4.2 Look for the element
get(int index)： Returns data according to the specified index
public E get(int index) {
// Check index Is it in a legal position
checkElementIndex(index);
// call Node(index) Go find index Corresponding node Then return its value item
return node(index).item;
}Get the header node （index=0） Data method :
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E element() {
return getFirst();
}
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
} difference ：
getFirst() and element() Method will be used when the linked list is empty , Throw an exception ;
element() The internal part of the method is to use getFirst() Realized . They will be when the list is empty , Throw out NoSuchElementException .
Get tail node （index=-1） Data method :
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
} Difference between them ：
getLast() Method when the linked list is empty , Will throw out NoSuchElementException; and peekLast() It's just going back to null.
4.3 Remove elements
remove() 、removeFirst()、pop(): Delete header node
public E pop() {
return removeFirst();
}
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}removeLast()、pollLast(): Delete tail node
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}difference ： removeLast() When the linked list is empty NoSuchElementException;pollLast() Method returns null.
remove(Object o): Deletes the specified element
public boolean remove(Object o) {
// If you want to delete the object as null
if (o == null) {
// Traverse from the beginning
for (Node<E> x = first; x != null; x = x.next) {
// Element found
if (x.item == null) {
// Remove the found element from the linked list
unlink(x);
return true;
}
}
} else {
// Traverse from the beginning
for (Node<E> x = first; x != null; x = x.next) {
// Element found
if (o.equals(x.item)) {
// Remove the found element from the linked list
unlink(x);
return true;
}
}
}
return false;
}When deleting the specified object , Just call remove(Object o) that will do , However, this method will only delete one matching object at a time , If you delete the matching object , return true, otherwise false.
unlink(Node<E> x) Method ： Delete the specified node
E unlink(Node<E> x) {
final E element = x.item;
// obtain x Successor node
final Node<E> next = x.next;
// obtain x The precursor node of
final Node<E> prev = x.prev;
// x It's the head node
if (prev == null) {
// If the deleted node is the head node , Make the head node point to the successor node of the node
first = next;
} else {
// Point the successor node of the precursor node to x Successor node
prev.next = next;
// Delete x The front of
x.prev = null;
}
// x It's the tail node
if (next == null) {
last = prev;// If the deleted node is the tail node , Make the tail node point to the precursor node of the node
} else {
next.prev = prev;
x.next = null;
}
// Delete the content of the specified node
x.item = null;
size--;
modCount++;
return element;
}remove(int index)： Deletes the element at the specified location
public E remove(int index) {
// Check index Range
checkElementIndex(index);
// Delete node
return unlink(node(index));
}4.4 Modifying elements
set(int index, E element) Method ： Modify the specified node element
public E set(int index, E element) {
// Check for out of line
checkElementIndex(index);
// Find nodes by index
Node<E> x = node(index);
// oldVal Store what needs to be changed
E oldVal = x.item;
x.item = element;
// Returns the value before the change
return oldVal;
}5 ArrayList And LinkedList similarities and differences
| similarities and differences | ArrayList | LinkedList |
|---|---|---|
| Whether thread safety is guaranteed | no | no |
| Whether insertion and deletion are affected by the location of the element | yes | no |
| Whether to support fast random access | yes | no |
| Is it implemented RandomAccess Interface | yes | no |
| Underlying data structure | Object Array | Double linked list （JDK1.6 It was a circular list ,JDK1.7 The loop was canceled ） |
| Memory footprint | The expansion mechanism leads to list A certain amount of space will be reserved at the end of the list | Each element costs extra to store the next / The space of the precursor |
