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).
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.
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)
.
#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!

The article discusses using Maven and Gradle for Java project management, build automation, and dependency resolution, comparing their approaches and optimization strategies.

The article discusses creating and using custom Java libraries (JAR files) with proper versioning and dependency management, using tools like Maven and Gradle.

The article discusses implementing multi-level caching in Java using Caffeine and Guava Cache to enhance application performance. It covers setup, integration, and performance benefits, along with configuration and eviction policy management best pra

The article discusses using JPA for object-relational mapping with advanced features like caching and lazy loading. It covers setup, entity mapping, and best practices for optimizing performance while highlighting potential pitfalls.[159 characters]

Java's classloading involves loading, linking, and initializing classes using a hierarchical system with Bootstrap, Extension, and Application classloaders. The parent delegation model ensures core classes are loaded first, affecting custom class loa


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

SublimeText3 English version
Recommended: Win version, supports code prompts!

mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

SublimeText3 Chinese version
Chinese version, very easy to use

SublimeText3 Mac version
God-level code editing software (SublimeText3)