An overview of the
LinkedList and ArrayList are two different implementations of the List interface. The efficiency of adding and deleting a List is low, but the efficiency of changing a List is high. On the contrary, the addition and deletion of LinkedList is more efficient because it does not need to move the underlying array data, which is realized by LinkedList and only needs to modify the LinkedList node pointer.
However, both modification and lookup need to locate the target node first (because null values are allowed, two for loops are often traversed, with time complexity o(n)), so the efficiency is low.
To begin, say collection.toarray () again; . This method is very important, both ArrayList and LinkedList will be converted into arrays when batch add. Because arrays can be traversed directly with a for loop. More convenient and efficient
In a nutshell, LinkedList is a thread-unsafe two-way list that allows elements to be null. The underlying data structure is a linked List, which implements the List
, Deque
, Cloneable, java.io.Serializable interface, which implements Deque
, so it can also be a double-ended queue. Compared to ArrayList, RandomAccess is not implemented, so it is slower to randomly access elements with subscripts.
As its underlying data structure is a linked list, it is conceivable that its addition and deletion only need to move the pointer, so the time efficiency is high. No batch expansion is required, and no reserved space is required, so the space efficiency is higher than ArrayList.
The disadvantage is that when random access is required, the time efficiency is very low. Although the bottom layer will judge whether the target Node is in the first half or the second half according to the index when querying Node according to the index, and then decide whether to query in order or reverse order to improve the time efficiency. However, as n increases, the overall time efficiency is still very low. ModCount is modified each time it is added or deleted.
A constructor
// The number of set elements
transient int size = 0;
// List header node
transient Node<E> first;
// The end of the list
transient Node<E> last;
// Do nothing
public LinkedList(){}Public Boolean addAll(Collection
c) Inserts all elements of collection C into a linked list
public LinkedList(Collection<? extends E> c) {
this(a); addAll(c); }Copy the codeNode Node structure:
private static class Node<E> {
E item;/ / element value
Node<E> next;// back node
Node<E> prev;// The front node
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev; }}Copy the codeAs you can see, this is a two-way linked list.
Commonly used API
Increased 1.
AddAll Batch insert
//addAll, add a batch at the end
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);// Insert all elements in set C with size as insert subscript
}
// Insert all elements in c with index as index
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);// Check for out-of-bounds [0,size] closed interval
Object[] a = c.toArray();// Get the target collection array
int numNew = a.length;// The number of new elements
if (numNew == 0)// If the number of new elements is 0, it is not increased and false is returned
return false;
Node<E> pred, succ; // The index node is the front node and the back node
if (index == size) { // Append data to the end of the list
succ = null; //size must be null after the queue node
pred = last;// The front node is the end of the queue
} else {
succ = node(index);// Fetch the index node as the rear node
pred = succ.prev; // The front node is the node before the index node
}
// The list is added in batches by a for loop that iterates through the array and inserts nodes in sequence. ArrayList is added in batches through system. arrayCopy
for (Object o : a) {// Iterate over the nodes to be added.
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);// Build a new node with the preceding node and element value e,
if (pred == null) // If the front node is empty, it is a header
first = newNode;
else// Otherwise, the rear node of the front node is set to the new node
pred.next = newNode;
pred = newNode;// Step, the current node is the front node, ready for the next node to add
}
if (succ == null) {// After the loop ends, check if the trailing node is null. This indicates that the queue is at the end of the append.
last = pred; // Set the tail node
} else {
pred.next = succ; // If the node is inserted in the queue, update the front node and the back node
succ.prev = pred; // Update the front node of the rear node
}
size += numNew; // Change the quantity size
modCount++; / / modify modCount
return true;
}
// Select Node from index;
Node<E> node(int index) {
// assert isElementIndex(index);
// When retrieving a node by subscript, the index will be halved according to whether the index is in the first half or the second half to improve query efficiency
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
private void checkPositionIndex(int index) {
if(! isPositionIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size; // Insert check, subscript can be size [0,size]
}
Copy the codeInsert a single node
// Insert a node at the end: add
public boolean add(E e) {
linkLast(e);
return true;
}
// Generate a new node and insert it at the end of the list to update the last/first node.
void linkLast(E e) {
final Node<E> l = last; // Record the original tail node
final Node<E> newNode = new Node<>(l, e, null);// Use the old tail node as the front node of the new node
last = newNode;// Update the tail node
if (l == null)// If the original list is empty, additional headers need to be updated
first = newNode;
else// Update the last node to the current last node (new node)
l.next = newNode;
size++;/ / modify the size
modCount++;/ / modify modCount
}
Copy the code // Insert a node at index
public void add(int index, E element) {
checkPositionIndex(index);// check if the subscript is out of bounds [0,size]
if (index == size)// Insert after the last node
linkLast(element);
else// Insert in the middle
linkBefore(element, node(index));
}
// Insert a new node e before succ
void linkBefore(E e, Node<E> succ) {
// assert succ ! = null;
// Save the front node of the rear node
final Node<E> pred = succ.prev;
// Build a new node with the preceding and trailing nodes and element value e
final Node<E> newNode = new Node<>(pred, e, succ);
// The new node is the pre-node of the original node succ
succ.prev = newNode;
if (pred == null)// If the preceding node is empty, succ is the original header. So the new node is now the head node
first = newNode;
else// Otherwise, the post-node of the build front node is new
pred.next = newNode;
size++;// Change the number
modCount++;/ / modify modCount
}
Copy the codeSummary: Add-ons must modify modCount
Delete the remove
// Delete: remove target node
public E remove(int index) {
checkElementIndex(index);// check if subscript [0,size] is exceeded
return unlink(node(index));// Remove a node from the list
}
// Remove the x node from the list
E unlink(Node<E> x) {
// assert x ! = null;
final E element = x.item; // The element value of the current node
final Node<E> next = x.next; // The node after the current node
final Node<E> prev = x.prev;// The front node of the current node
if (prev == null) { // If the front node is empty (the current node was originally a head node)
first = next; // then the header is equal to the post-node
} else {
prev.next = next;
x.prev = null; // Empty the front node of the current node
}
if (next == null) {// If the last node is empty, the current node is the last node.
last = prev; // The last node is the front node
} else {
next.prev = prev;
x.next = null;// Empty the post-node of the current node
}
x.item = null; // Empty the current element value
size--; // Change the number
modCount++; / / modify modCount
return element; // Returns the value of the fetched element
}
private void checkElementIndex(int index) {
if(! isElementIndex(index))throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/ / the subscript [0, size)
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
Copy the codeDelete the specified element
// Because null elements are to be considered, it is also iterated twice
public boolean remove(Object o) {
if (o == null) {// If you want to delete a null node (as can be seen from remove and add, null elements are allowed)
// Iterate over each node comparison
for(Node<E> x = first; x ! =null; x = x.next) {
if (x.item == null) {
unlink(x);
return true; }}}else {
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true; }}}return false;
}
// Delete node x from the list
E unlink(Node<E> x) {
// assert x ! = null;
final E element = x.item;// Continue the element value for return
final Node<E> next = x.next;// Save the post-node of the current node
final Node<E> prev = x.prev;// The front node
if (prev == null) {// The front node is null,
first = next;// The first node is next
} else {// Otherwise update the rear node of the front node
prev.next = next;
x.prev = null;// Remember to set the preceding node of the node to null
}
// If the trailing node is null, it is the tail node
if (next == null) {
last = prev;
} else {// Otherwise update the front node of the back node
next.prev = prev;
x.next = null;// Remember to delete the node after the node is null
}
// Set the element value of the deleted node to null for GC
x.item = null;
size--;/ / modify the size
modCount++;/ / modify modCount
return element;// Returns the value of the deleted element
}
Copy the codeDeletion will also definitely modify modCount. Delete a Node by index and unlink the Node from the unlinked list. Delete by element: iterates through the list to see if the Node is present, and then unlinks it twice to allow null values.
To change the set
public E set(int index, E element) {
checkElementIndex(index); // Check for out-of-bounds [0,size]
Node<E> x = node(index);// Fetch the corresponding Node
E oldVal = x.item;// Save the old value for return
x.item = element;// Overwrite the old value with the new value
return oldVal;// Return the old value
}
Copy the codeModCount = modCount (index)
Check the get
- Query nodes based on index
public E get(int index) {
checkElementIndex(index);[0,size]
return node(index).item; // Call the node() method to fetch the node node,
}
Copy the code- Based on the node object, query subscript, also need to go through the linked list twice.
public int indexOf(Object o) {
int index = 0;
if (o == null) {// If the target object is null
// Iterate over the list
for(Node<E> x = first; x ! =null; x = x.next) {
if (x.item == null)
returnindex; index++; }}else {//// iterate through the linked list
for(Node<E> x = first; x ! =null; x = x.next) {
if (o.equals(x.item))
returnindex; index++; }}return -1;
}
Copy the code- Iterate through the list from end to end to find the node whose target element value is O
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
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 codeModCount cannot be modified
toArray()
Let’s also take a look at toArray(). This is a high-frequency API, after all
public Object[] toArray() {
// Create a new array and then iterate over the list, storing each element in the array, return
Object[] result = new Object[size];
int i = 0;
for(Node<E> x = first; x ! =null; x = x.next)
result[i++] = x.item;
return result;
}
Copy the codeConclusion:
LinkedList is a two-way list.
- Lists are added in batches by a for loop that iterates through the array and inserts nodes in turn. ArrayList is added in batches through system. arrayCopy. ModCount must be modified.
- When a node is obtained by subscript (Add select), the index is halved according to whether the index is in the first half or the second half to improve query efficiency
- Deletion will also definitely modify modCount. Delete a Node by index and unlink the Node from the unlinked list. Delete by element: iterates through the list to see if the Node is present, and then unlinks it twice to allow null values.
- Find Node based on index and replace the value. ModCount is not modified.
- Lookup itself is to find a Node based on index.
- So its CRUD operations are designed to find nodes by index.