编程知识 cdmana.com

Analysis of Java LinkedList source code from the perspective of interview

notes : In this series of articles jdk All versions are java8

LinkedList The class diagram is as follows :

LinkedList The bottom layer is realized by bidirectional linked list . A linked list is like a train , Each car contains a car and a connection point to the next car . Each node in a bidirectional linked list not only has a pointer to the next node , And a pointer to the previous node .
stay LinkedList There is one in the source code Node Static class , Source code is as follows :

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;
        this.next = next;
        this.prev = prev;
    }
}

One Node The node consists of three parts , Namely

  • item: data

  • next: Pointer to the next node

  • prev: Pointer to the previous node

LinkedList The main variables are as follows :

//  The number of elements in the set 
transient int size = 0;

/**
  *  Pointer to the first node .
  * Invariant: (first == null && last == null) ||
  *            (first.prev == null && first.item != null)
  */
transient Node<E> first;

/**
  *  Pointer to the tail node .
  * Invariant: (first == null && last == null) ||
  *            (last.next == null && last.item != null)
  */
transient Node<E> last;

One 、 Additive elements

LinkedList Supports adding elements at any node location , It not only provides a collection of commonly used add() Method , It also provides addFirst() and addLast(),add() Method is called by default addLast() Method , In other words, the default is to insert elements at the end of the list .

add() Method source code :

public boolean add(E e) {
    linkLast(e);
    return true;
}

1.1 Tail-insert element

linkLast() Source code is as follows :

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
        l.next = newNode;
    size++;
    modCount++;
}

Let's draw a diagram to show how to insert elements to the end of a list :

If there are no elements in the list

Corresponding to if sentence , If there is no element, the new node is the only element in the linked list , It is the first node , It's the tail node again , The pointer to the previous element and the pointer to the next element are both null. Note here head Node is not the first node ,head The node just identifies the address of the list .

If there are elements in the list

Corresponding to the source code else sentence . First, treat the new element as Last node , Then put the original Last Node next Point to a new node .

else
    l.next = newNode;

A picture is better than a foreword , Do you understand everything by drawing a picture .

1.2 Header insert element

linkFirst() Source code is as follows :

private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

Or according to the above figure to interpret the source code , First assign the first node to the intermediate variable f, New nodes newNode Assign a value to first node . If the list has no elements , be Last Nodes and First The nodes are all newly inserted nodes newNode, otherwise , The original First The head pointer of the node points to the new node .

Two 、 Remove elements

LinkedList The deletion method provided is based on Indexes and Elements Delete , In addition, it also provides methods to delete the first and last elements , Here we only analyze the method of deleting according to the index .

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

checkElementIndex(index) Method is used to determine whether the index value transmitted is legal , Illegal throw array out of bounds exception . Let's focus on unlink(node(index)) Method is how to delete elements .

node(index) Method source code :

node(index) The method is to get the node of the index position according to the index

Node<E> node(int index) {
    // assert isElementIndex(index);
    //  If you specify a subscript  <  Half the number of elements , It starts from the first node 
    //  otherwise , Starting from the tail node 
    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;
    }
}

unlink(Node<E> x) Source code is as follows :

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

Draw a picture to analyze how the deletion works :

  1. Suppose you delete the first element : Then it's prev==NULL, We need to put the last element of his ( In the picture second) As the first element

  2. Suppose you delete the last element , Then it's next==null, We need to put his previous element ( In the picture second) As the last element

  3. If it's any element in the middle , Then you need to put the next The pointer points to its next element , At the same time, it will be the next element of prev Pointer to its previous element .

3、 ... and 、 summary

LinkedList The bottom layer is realized by bidirectional linked list , Because it's a linked list , It's not just storing data , And store the pointer , So memory overhead is higher than ArrayList Big , Deleting elements does not require moving other elements , Just change the direction of the pointer , So deleting is more efficient , And it didn't come true RandomAccess Interface , So using iterators to traverse is better than for Cycles are more efficient .LinkedList It also supports inserting duplicate and null values , It's also thread unsafe .

 Recommended reading 
 I talked about Gao recently P, I'm in a panic 
 Ten year old farmers , I'll teach you how to write a resume on the spot 
 To show you the technical article , We broke our hearts ...
 Programming · thinking · In the workplace 
 Welcome to scan 

版权声明
本文为[singwhatiwanna]所创,转载请带上原文链接,感谢
https://cdmana.com/2020/12/20201224105612949U.html

Scroll to Top