LinkedList set source code analysis


The linked list structure should be clear to everyone. LinkedList is implemented based on two-way linked list. The previous article briefly analyzed ArrayList, which is implemented based on array; This article will make a simple analysis of LinkedList. As long as you understand the structure of the linked list, the source code looks very simple, just the binding and unbinding operation between nodes.

1, Data and linked list

The two-way linked list has three important attributes: node (data node), PRED (previous node) and next (next node). It is linked together through the association relationship between nodes. The advantage of this is that it increases, deletes and traverses faster, but its random search is slower than the array. The search for an element in a normal array is calculated through binary search, Faster query efficiency; The linked list can only traverse from the beginning to the end to find the corresponding elements.

2, LinkedList

LinkedList is implemented based on a two-way linked list. A Node class is defined inside it to represent the nodes of the linked list.

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

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

Core attribute

There is a Node class inside the LinkedList, which is a Node in the linked list. Needless to say, it is basically clear to those who understand the basic data structure.
Core properties of LinkedList:

  • size: also records the length of internal elements of LinkedList.
  • First: the first element.
  • Last: the last element.

Core method

Construction method

The construction method of LinkedList does not specify the size, because its implementation is a linked list without specifying the size.
Let's not talk about parameterless construction. There's nothing. Let's take a look at the construction method of passing Collection.

public LinkedList(Collection<? extends E> c) {
* The core method is addAll, which converts the contents of other types of collections into linked list form
public boolean addAll(int index, Collection<? extends E> c) {
	//Convert collection to array
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
	//Find the corresponding node
    Node<E> pred, succ;
    if (index == size) { //At first, the size and index are the same, both 0
        succ = null;
        pred = last;
    } else {  //Don't go here at the beginning. You can only go here when there is data in the linked list
        succ = node(index); //Find the corresponding index of the node
        pred = succ.prev;
	//Loop through
    for (Object o : a) {
        E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null) //For the first time, pred is empty, and the head node is the created node
            first = newNode;
        else	//Sets the link point between nodes
   = newNode;
        pred = newNode; //Assign the intermediate value again
    //Assign the last node as the last node after traversal
    if (succ == null) {
        last = pred;
    } else { //Establish the link between the two linked lists = succ; 
        succ.prev = pred;
    size += numNew; //size is set to the common length of the two linked lists
    return true;
* Node lookup
Node<E> node(int index) {
	//If the passed in index is less than the length of the current linked list / 2, search from left to right
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x =;
        return x;
     //If the passed in index is greater than the length of the current linked list / 2, search from right to left
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;

add() method

public boolean add(E e) {
    return true;
//Hang the added node at the end of the linked list
void 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 = newNode;

get() method

Directly return the element bound by the subscript node

public E get(int index) {
     return node(index).item;

remove() method

The remove() method of LinkedList also has subscript removal and object removal
Subscript removal:

public E remove(int index) {
    //Find the element at the subscript position and unlink it
    return unlink(node(index));

Object removal, first traverse to find the corresponding element, and then unlink:

public boolean remove(Object o) {
   if (o == null) {
        for (Node<E> x = first; x != null; x = {
            if (x.item == null) {
                return true;
    } else {
        for (Node<E> x = first; x != null; x = {
            if (o.equals(x.item)) {
                return true;
    return false;

Take a look at the method of unlinking:

E unlink(Node<E> x) {
	//Gets the element in x, the previous node and the next node
    final E element = x.item;
    final Node<E> next =;
    final Node<E> prev = x.prev;
    //If the previous node is empty, then x is the head node, and set the next node as the head node; If the previous node is not empty, bind the previous node and the next node together
    if (prev == null) {
        first = next;
    } else { = next;
        x.prev = null;
     //If the next node is empty, then x is the tail node. Set the previous node as the tail node; If the next node is not empty, bind the previous node and the next node together
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev; = null;
	//If the reference of the X element position is set to null, and the links between the upper and lower nodes of X are also disconnected and set to null, then x is completely released and will be recycled during garbage collection
    x.item = null;
    return element;

The size() method is also omitted. Although the linked list has no length, there is a size inside the LinkedList, which always records how many elements are currently stored.

Keywords: Java source code list

Added by DonnieDarko on Mon, 07 Mar 2022 14:21:56 +0200