search
HomeJavajavaTutorialJava LinkedList source code analysis (picture)

Overall introduction

LinkedList implements both the List interface and the Deque interface, which means that it can be regarded as both a sequential container and a queue(Queue), and can also be regarded as a stack. From this point of view, LinkedList is simply an all-around champion. When you need to use a stack or queue, the first thing you should consider is LinkedList. Because Java has officially stated that it is not recommended to use the Stack class, and it is recommended to use LinkedList. What is even more regrettable is that there is no class called Queue in Java (it is an interface name).

Java LinkedList source code analysis (picture)

The bottom layer of LinkedList is implemented through a doubly linked list. This section will focus on the maintenance process of the doubly linked list when inserting and deleting elements, that is, the solution between Function related to the List interface, while the knowledge related to Queue, Stack and Deque will be discussed in the next section. Each node of a doubly linked list is represented by the inner class Node. LinkedList references through first and last to point to the first and last elements of the linked list respectively. Note that there is no so-called dummy variable here. When the linked list is empty, first and last both point to <a href="http://www.php.cn/wiki/62.html" target="_blank">null</a>.

//Node内部类
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;
    }
}

The implementation of LinkedList determines that all operations related to subscripts are linear time, and deleting elements at the beginning or end only requires constant time. In order to pursue efficiency, LinkedList does not implement synchronization (synchronized). If concurrent access by multiple threads is required, you can first use the Collections.synchronizedList() method to wrap it.

Method Analysis

add()

add() method has two versions, one is add(E e), this method is in LinkedList Insert elements at the end, because last points to the end of the linked list, and inserting elements at the end takes constant time. You only need to simply modify a few related references; the other is add(int index, E element). This method is to insert an element at the specified table below. You need to first find the specific position through linear search, and then Modify the relevant references to complete the insertion operation.

Java LinkedList source code analysis (picture)

Combined with the above picture, we can see that the logic of add(E e) is very simple. The logic of

//add(E e)
public boolean add(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++;
    return true;
}

add(int index, E element) is slightly complicated and can be divided into two parts. 1. First find the location to be inserted according to the index; 2. Modify the reference and complete the insertion. operate.

//add(int index, E element)
public void add(int index, E element) {
    checkPositionIndex(index);//index >= 0 && index <= size;
    if (index == size)//插入位置是末尾,包括列表为空的情况
        add(element);
    else{
        Node<E> succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用,完成插入操作。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

The node(int index) function in the above code is a little tricky, because the linked list is bidirectional, you can search from the beginning to the back, or you can search from the end to the front. The specific direction to look for depends on the condition index > 1), that is, whether the index is close to the front end or the back end.

remove()

remove()The method also has two versions, one is to delete the first element that is equal to the specified elementremove(<a href="http://www.php.cn/wiki/60.html" target="_blank"> Object</a> o), the other is to delete the element at the specified index remove(int index).

Java LinkedList source code analysis (picture)

#Both deletion operations require 1. First finding the reference of the element to be deleted, 2. Modifying the relevant reference to complete the deletion operation. When looking for a reference to a deleted element, remove(Object o) calls the element's equals method, while remove(int index) uses the subscript Counting, both ways has linear time complexity. In step 2, both revome() methods are completed through the unlink(Node<e> x)</e> method. Here you need to consider the boundary case when the deleted element is the first or last one.

//unlink(Node<E> x),删除一个Node
E unlink(Node<E> x) {
    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;//let GC work
    size--;
    return element;
}

get()

get(int index)Get the reference to the element at the specified index by calling the node(int index mentioned above ) method implementation.

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}

set()

set(int index, E element)The method modifies the element at the specified subscript to the specified value, and also first passes the node (int index)Find the reference corresponding to the element in the table below, and then modify the value of item in Node.

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;//替换新值
    return oldVal;
}

The above is the detailed content of Java LinkedList source code analysis (picture). For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
带你搞懂Java结构化数据处理开源库SPL带你搞懂Java结构化数据处理开源库SPLMay 24, 2022 pm 01:34 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

Java集合框架之PriorityQueue优先级队列Java集合框架之PriorityQueue优先级队列Jun 09, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

完全掌握Java锁(图文解析)完全掌握Java锁(图文解析)Jun 14, 2022 am 11:47 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

一起聊聊Java多线程之线程安全问题一起聊聊Java多线程之线程安全问题Apr 21, 2022 pm 06:17 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

详细解析Java的this和super关键字详细解析Java的this和super关键字Apr 30, 2022 am 09:00 AM

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

Java基础归纳之枚举Java基础归纳之枚举May 26, 2022 am 11:50 AM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

java中封装是什么java中封装是什么May 16, 2019 pm 06:08 PM

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

归纳整理JAVA装饰器模式(实例详解)归纳整理JAVA装饰器模式(实例详解)May 05, 2022 pm 06:48 PM

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools