brief introduction

UML Diagram

Use examples

LinkedList list = new LinkedList<>();
//Newly added
list.add("a");
list.add("a");
list.add("b");
System.out.println(list);

//delete
list.remove("a");//Delete the first corresponding object
list.remove(0);//Delete elements marked 0
list.removeFirst();//Delete the first element
list.removeLast();//Delete the last element
System.out.println(list);

//modify
list.set(0,"c");//Modify elements with subscripts of 0
System.out.println(list);

//insert 
list.add(1,"a");//Can only be inserted in front, back or middle of an existing element
System.out.println(list);

//Obtain
list.get(0);//Obtain elements based on Subscripts
list.getFirst();//Get the first element
list.getLast();//Get the last element

//loop
//Ordinary cycle
for(int i=0;i<list.size();i++){
    System.out.println(list.get(i));
}
//foreach loop
for(Object o:list){
    System.out.println(o);
}
//Iterative cycle
Iterator iterator = list.iterator();
while (iterator.hasNext()){
    System.out.println(iterator.next());
}

Source code parsing

Initialization

node

//The Core Class of Linked List-Node
private static class Node<E> {
    //Node element
    E item;
    //Next Node Reference
    Node<E> next;
    //Last Node Reference
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Construction method

//Default size
transient int size = 0;
//First node
transient Node<E> first;
//Last node
transient Node<E> last;
//Parametric structure
public LinkedList() {
}
//Constructions with Initialized Sets
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

Analysis of addAll

public boolean addAll(int index, Collection<? extends E> c) {
    //Detect whether the boundary is crossed
    //Initialization does not cross the bounds. It is mainly used to increase the number of collections after initialization while modifying the collections at the same time, the cross-bounds exception will occur.
    checkPositionIndex(index);
    
    Object[] a = c.toArray();
    //Judging whether a set is empty
    int numNew = a.length;
    if (numNew == 0)
        return false;
    //
    Node<E> pred, succ;
    //If index==size, the list has only one node
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    //Loop collections into linked lists
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }
    
    //last is the same as the current node when it is a node
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    
    //Update the length of the linked list
    size += numNew;
    modCount++;
    return true;
}

Analysis of Common Functions

increase

//Increase the element by default to add nodes to the end of the list
public boolean add(E e) {
        linkLast(e);
        return true;
    }
void linkLast(E e) {
    //Get the end node of the list
    final Node<E> l = last;
    //Create a new node, refer to the last node as the previous node of the new node, and the element as the incoming element
    final Node<E> newNode = new Node<>(l, e, null);
    //The end of the list points to the latest node
    last = newNode;
    //If the original tail node is empty, it means that the header node of the list needs to be set for the empty list.
    //Otherwise, the next of the end node of the original list is pointed to the new node.
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    //Increase size
    size++;
    //Recording the number of modifications, mainly for set iteration, to ensure the accuracy of iteration data
    //If the set changes during iteration, an exception is thrown
    //throw new ConcurrentModificationException();
    modCount++;
}

delete

//Delete nodes according to Subscripts
public E remove(int index) {
    //Detecting whether subscripts are out of bounds
    checkElementIndex(index);
    return unlink(node(index));
}
//Get the node of index
Node<E> node(int index) {
    //If the subscript is less than half the length of the list, look ahead
    //Otherwise, look forward from behind the list
    if (index < (size >> 1)) {
        //The query method assigns values one by one from the table header until the subscript position is specified.
        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;
    }
}

//Delete the first node
public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
//Disconnect the first node
private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    //Set the next node of the current node as the first node
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

//Delete the last node
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}
//Disconnect the last node
private E unlinkLast(Node<E> l) {
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    //Set the last node to the previous node of the current node
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

Modify (replace) elements

//Modify an element
public E set(int index, E element) {
        //Detecting whether subscripts are out of bounds
        checkElementIndex(index);
        //Obtain nodes based on Subscripts
        Node<E> x = node(index);
        //Get the element of the node
        E oldVal = x.item;
        //Assign new elements
        x.item = element;
        return oldVal;
    }

Insert elements

//Insert the specified location element
public void add(int index, E element) {
    //Detecting whether subscripts are out of bounds
    checkPositionIndex(index);
    //Determine if the subscript is the last position and if it is inserted directly into the last node
    //Otherwise, the current index node is queried and the new node is placed before the original index node.
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
//Location before inserting index node
void linkBefore(E e, Node<E> succ) {
    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++;
}

Get elements

//Obtain elements based on Subscripts
public E get(int index) {
    //Detecting whether subscripts are out of bounds
    checkElementIndex(index);
    //Get the node according to the subscript, and then return the element of the node
    return node(index).item;
}

//Get the first element
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

//Get the last element
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

Clear all data

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    //Assign all data to null one by one to help gc recycle garbage
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    //Record clearance operations to ensure the accuracy of iterations
    modCount++;
}

summary

• Advantage
  1. Efficient insertion and removal of data 2. Easy use of linked lists as stack or queue scenarios 3. linkedlist does not need to be expanded relative to arraylist
• shortcoming
  1. It is inefficient to acquire elements according to randomness (acquired by subscripts)
  2. Low efficiency of batch adding collections

Other

In arraylist and linkedlist, there is a modifier transient. The attributes of this modifier can not be serialized by default. In order to reduce the waste of space, the jdk author implements two methods: write Object (Object Output Stream) and read Object (Object Input Stream). Manual serialization has useful attributes for storing data.

Reference resources

• Wikipedia https://zh.wikipedia.org/wiki/linked list

Please pay more attention to Wechat...