@[TOC]
Introduction to the
- LinkedList is implemented based on a LinkedList, which is a bidirectional LinkedList as you can see from the UML diagram. In addition to being used as a linked list, it can also operate as a stack, queue, or double-endian queue. Not thread-safe, AbstractSequentialList implementation List, Deque, Cloneable, Serializable.
- LinkedList is implemented based on linked lists, so insertions and deletions are efficient and lookups are inefficient (although there is an accelerated action)
- LinkedList is implemented based on linked lists, so there is no capacity problem, so there is no way to expand
- If you want to use LinkedList to become thread-safe, you call the synchronizedList method in the static class Collections class
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable.java.io.Serializable
Copy the code-
Inheriting AbstractSequentialList, AbstractSequentialList implements get(int index), set(int index, E element), Add (int index, E element), and remove(int index) functions.
-
Implement the List interface, it can carry out queue operations
-
Implement the Deque interface and use the LinkdList as a double-ended queue
-
Cloneable interface is implemented, that is, clone
-
Implement the Java.io.Serializable interface, which means that LinkedList supports serialization and can be transmitted via serialization.
The internal structure
/** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item ! = null) */
transient Node<E> first;
/** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item ! = null) */
transient Node<E> last;
Copy the codeprivate static class Node<E> {
E item; / / the node values
Node<E> next; // Next node
Node<E> prev; // Last node
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeThis class represents the Node of a double-ended list. This class has three attributes: the value of the node, the next node, and the previous node
Source code analysis
1. Construction method
Empty constructor:
public LinkedList(a) {}Copy the codeCollection create linked list constructor:
public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }Copy the code2. The add method
The add(E E) method adds an element to the end of the list
public boolean add(E e) {
linkLast(e); // Add to the last element of the list
return true;
}
Copy the codevoid linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode; // Create a node
if (l == null)
first = newNode;
else
l.next = newNode; // points to the next element
size++;
modCount++;
}
Copy the codeAdd (int index, E Element) : Adds an element at the specified position
public void add(int index, E element) {
checkPositionIndex(index); // Check whether the index is between [0-size]
if (index == size)
linkLast(element); // Add to the end of the list
else
linkBefore(element, node(index)); // Add to the middle of the list
}
Copy the code- The linkBefore method takes two arguments, the value of the insertion node and the specified node
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
Copy the codeaddAll(Collection<? Extends E> c) method: Adds an element to the end of the list
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
Copy the codepublic boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); // Check if the index is in range
Object[] a = c.toArray(); The toArray() method stores the collection's data into an array
int numNew = a.length;
if (numNew == 0)
return false;
// Get the front and back nodes
Node<E> pred, succ;
if (index == size) { // If index == 0, the first Node initializes a Node and the second Node is null
succ = null;
pred = last;
} else { // Instead of 0, call node() to get the back node and the front node
succ = node(index);
pred = succ.prev;
}
// Iterate over the data to insert the data
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
// Superkey new node
Node<E> newNode = new Node<>(pred, e, null);
// If the insertion position is in the header of the table
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// If the insertion position is at the end, reset the last node
if (succ == null) {
last = pred;
} else { // Otherwise, join the inserted list with the previous list
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
Copy the codeAddAll methods are divided into:
- Check whether the following table for index is between 0 and size
- ToArray stores the collection’s data into an array of objects
- Get the front and back nodes of the insertion position
- Compare the data there and insert the data into the specified location
AddFirst (E E) : Adds an element to the head of the list
public void addFirst(E e) {
linkFirst(e);
}
Copy the codeprivate void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f); // Create a node
first = newNode;
// If the list is empty, the last node also points to that node
if (f == null)
last = newNode;
// Otherwise, point to the previous element
else
f.prev = newNode;
size++;
modCount++;
}
Copy the codeAddLast (E E) : Adds elements to the end of the list, just like the add(E E) method
public void addLast(E e) {
linkLast(e);
}
Copy the codevoid linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
Copy the code3. Obtain data based on location
Get (int index) : returns data according to the specified index
public E get(int index) {
// check index range
checkElementIndex(index);
// Call Node (index) to find the Node corresponding to index and return its value
return node(index).item;
}
Copy the codeGetFirst () : Gets the header element
public E getFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
Copy the codeGetLast () : Gets the tail element
public E getLast(a) {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
Copy the code4. Obtain the index by object
IndexOf (Object O) : Traverses the search from the beginning
public int indexOf(Object o) {
int index = 0;
if (o == null) {
//x = first iterates the query from the beginning
for(Node<E> x = first; x ! =null; x = x.next) {
if (x.item == null)
returnindex; index++; }}else {
//x = first iterates the query from the beginning
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item))
returnindex; index++; }}return -1;
}
Copy the codeInt lastIndexOf(Object O) : Search from the end
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
// x is last traversed from the tail
for(Node<E> x = last; x ! =null; x = x.prev) {
index--;
if (x.item == null)
returnindex; }}else {
for(Node<E> x = last; x ! =null; x = x.prev) {
index--;
if (o.equals(x.item))
returnindex; }}return -1;
}
Copy the code5. Whether to contain elements
Contains (Object O) : Indicates whether the Object exists in the linked list
public boolean contains(Object o) {
// Call indexOf to traverse the query
returnindexOf(o) ! = -1;
}
Copy the code6. Delete
Remove () : removes the head node
public E remove(a) {
// Call the method to remove the head node
return removeFirst();
}
Copy the codepublic E removeFirst(a) {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
Copy the codeprivate E unlinkFirst(Node<E> f) {
// assert f == first && f ! = null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
Copy the codePoll () : Deletes the header element
public E poll(a) {
final Node<E> f = first;
return (f == null)?null : unlinkFirst(f);
}
Copy the codeRemoveLast () : Removes the tail element
public E removeLast(a) {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
Copy the codePollLast () : Remove the tail element
public E pollLast(a) {
final Node<E> l = last;
return (l == null)?null : unlinkLast(l);
}
Copy the codeRemove (Object O) : Deletes objects based on elements
public boolean remove(Object o) {
// If the object is null, we can insert null values
if (o == null) {
// x == first iterates through the elements from the beginning
for(Node<E> x = first; x ! =null; x = x.next) {
// Find the element
if (x.item == null) {
// Remove the element
unlink(x);
return true; }}}else {
// x == first iterates through the elements from the beginning
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item)) {
// Delete the element from the list
unlink(x);
return true; }}}return false;
}
Copy the codeUnlink (Node x)
E unlink(Node<E> x) {
// assert x ! = null;
final E element = x.item;
final Node<E> next = x.next; // Get the next node
final Node<E> prev = x.prev; // Get the last node
// If = null
if (prev == null) {
first = next; // Point the first node to the next element
} else {
prev.next = next; // The next node of the previous node specifies the next node
x.prev = null;
}
// Delete the next element
if (next == null) {
last = prev; // If the last node is deleted, make it point to the previous node of the node
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
Copy the codeRemove (int index) : deletes the element at the specified position
public E remove(int index) {
// Check the index range
checkElementIndex(index);
// Delete the node
return unlink(node(index));
}
Copy the codePersonal blog address: blog.yanxiaolu.cn /