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!

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

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

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

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

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

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

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

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


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

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
Powerful PHP integrated development environment

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

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools
