LinkedList Source Analysis Notes
Summary
- Inherited from AbstractSequentialList Abstract class, implements List, Deque, Cloneable, Serializable interfaces
- Sets based on bidirectional linked list implementations can be used as implementations of bidirectional queues
- Random Access is not supported, Random Access interface is not implemented, and element lookup efficiency is low.
- The insertion and deletion operations are more efficient, there is no expansion operation and no need to reserve space.
Source code analysis
Field information
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { //Number of elements record transient int size = 0; //Header node pointer of linked list transient Node<E> first; //End Pointer of Link List transient Node<E> last; }
Internal Node Class
private static class Node<E> { E item; //Subsequent node pointer Node<E> next; //Precursor node pointer Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
Construction method
//Empty construction, nothing to do public LinkedList() { } //Add all elements of the incoming collection to the list by addAll() method public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
Internal Method - Find Elements Based on index
If index is in the first half of the list, it traverses from the head node of the list; in the second half, index is searched from the end node of the list to improve the efficiency of searching.
/** *Search Method for Improving Search Efficiency */ Node<E> node(int index) { // Judging whether index belongs to the first half of the list if (index < (size >> 1)) { Node<E> x = first; //Starting from the first node, go through the lookup one by one for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; //Starting from the tail node, go through the lookup one by one for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
Add a single element
/** *To add a single element, you just need to point the pointer of the successor node of the tail node to e. */ public boolean add(E e) { linkLast(e); return true; } /** *Insert an element at the end */ void linkLast(E e) { //Save the current tail node final Node<E> l = last; //Create a new node with a value of e, with the precursor pointer pointing to the current tail node and the successor pointing to null final Node<E> newNode = new Node<>(l, e, null); //Update tail node pointer last = newNode; //If the first node is currently inserted, the header node also points to newNode. if (l == null) first = newNode; //If not, update the successor pointer of the last tail node else l.next = newNode; size++; //Record the number of modifications modCount++; } /** *Adding elements at specified locations */ public void add(int index, E element) { //Judging whether index is legal 0 <= index <= size checkPositionIndex(index); //If index=size, it is equivalent to inserting nodes at the end of the list. if (index == size) linkLast(element); else linkBefore(element, node(index)); } void linkBefore(E e, Node<E> succ) { // Getting the precursor node of the target node final Node<E> pred = succ.prev; //Create a new node. The precursor pointer of the new node points to the precursor node of the original node, and the subsequent pointer points to the original node. final Node<E> newNode = new Node<>(pred, e, succ); //Update the precursor node of the original node, the precursor pointer of the precursor point of the original node points to the new node succ.prev = newNode; //To determine whether it is the first insert, the first insert needs to update the list header node pointer if (pred == null) first = newNode; else //Update the precursor node's, successor pointer pred.next = newNode; size++; modCount++; }
Insert node diagrams at specified locations:
Adding multiple elements
/** *Inserting multiple elements at an unspecified location (equivalent to inserting multiple elements at the end of the list) */ public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } /** *Insert multiple elements at index */ public boolean addAll(int index, Collection<? extends E> c) { //Judging whether index is legal 0 <= index <= size checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; //Determine the insertion location and get the information of the insertion node //pred represents the precursor node of the insertion location, succ represents the insertion location node Node<E> pred, succ; if (index == size) {//Insert at the end of the list succ = null; pred = last; } else {//Insert in the middle of the list succ = node(index);//Nodes that get the insertion position pred = succ.prev; } //Traverse to insert data, insert one by one for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null)//If there are no nodes in the list, the head node of the list needs to be updated. first = newNode; else pred.next = newNode; pred = newNode; } //Connect the inserted link list with the original link list after the insertion position if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }
Delete elements
//Delete nodes according to Subscripts public E remove(int index) { checkElementIndex(index);//Judging the Legitimacy of Subscription return unlink(node(index)); } E unlink(Node<E> x) { // assert x != null; //Gets the value of the node to be deleted, the precursor node, and the successor node final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //If the precursor node is null, it indicates that the node to be deleted is the list header node. if (prev == null) { first = next; } else { //To delete a node from a two-way linked list, you only need to point the successor pointer of the precursor node that needs to delete the node to its successor node. prev.next = next; //Disconnect the connection between the delete node precursor pointer and the linked list x.prev = null; } //The successor node is null, indicating that the end of the list is deleted if (next == null) { last = prev; } else { //Update the precursor pointer of the successor node of the deleted node next.prev = prev; //Disconnect the connection between delete node successor pointer and linked list x.next = null; } x.item = null; size--; modCount++; return element; }
Delete node diagrams:
Query element
public E get(int index) { checkElementIndex(index);//Judging the Legitimacy of Subscription return node(index).item;//Traversing the list, one by one, to find the subscript-compliant nodes }
Modify elements
public E set(int index, E element) { checkElementIndex(index);//Judging the Legitimacy of Subscription Node<E> x = node(index);//Modify worthwhile nodes according to subscript lookup needs E oldVal = x.item;//Save node values to return x.item = element;//Values that cover the original node return oldVal; }
summary
- In order to improve the speed of searching elements according to index, it will be judged whether index is located in the first half or the second half of the list, the first half starts from the head node of the list, and the second half starts from the tail node.
- When the number of elements in the internal list changes, modCount++, record the number of structural modifications
- Two-way linked list does not support random access. All index-related operations can only be traversed and searched one by one.
- The efficiency of inserting and deleting elements is high. It only needs to find the relevant nodes and modify the precursor and successor pointers of the relevant nodes.
- When adding elements in batches, toArray() is used to convert incoming collections into arrays, which are added in turn using loops.