内容来源:
- 沉默王二 GitHub 上开源的知识库《Java 进阶之路》
- JavaGuide
- Geeksforgeeks
- 菜鸟教程
This is the multi-page printable view of this section. Click here to print.
内容来源:
LinkedList
是基于双向链表的数据结构, 实现队列和列表接口的所有方法, 允许存放任意类型元素链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的地址。
链表可分为单向链表和双向链表。
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。
单向链表
双向链表
Doubly-linked list implementation of the List
and Deque
interfaces. Implements all optional list operations, and permits all elements (including null
).
LinkedList
是基于双向链表的数据结构, 实现队列和列表接口的所有方法, 允许存放任意类型元素
以下情况使用 LinkedList :
- 你需要通过循环迭代来访问列表中的某些元素。
- 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, Serializable
使用之前:
LinkedList
类位于 java.util
包中,使用前需要引入它Queue
接口, 可以作为队列使用List
接口, 可进行列表的相关操作Cloneable
允许克隆Serializable
可以序列化新建实例
// 引入 LinkedList 类
import java.util.LinkedList;
public class RunoobTest {
public static void main(String[] args) {
LinkedList<String> sites = new LinkedList<String>();
sites.add("Google");
sites.add("Runoob");
sites.add("Taobao");
sites.add("Weibo");
System.out.println(sites);
}
}
开头添加元素
sites.addFirst()
结尾添加元素
注意 默认的
add()
方法就是在结尾添加
sites.addLast()
开头删除元素
sites.removedFirst()
结尾删除元素
sites.removedLast()
获取元素
sites.getFirst()
sites.getLast()
获取链表长度
sites.size()
和链表定位类似的是 ArrayList
基于动态数组的列表
相比之下链表有以下优点
链表大致分为三种
LinkedList
解析链表的核心是 Node
这是一个内部静态类, 定义存储数据单位的结构
/**
* 链表中的节点类。
*/
private static class Node<E> {
E item; // 节点中存储的元素
Node<E> next; // 指向下一个节点的指针
Node<E> prev; // 指向上一个节点的指针
/**
* 构造一个新的节点。
*
* @param prev 前一个节点
* @param element 节点中要存储的元素
* @param next 后一个节点
*/
Node(Node<E> prev, E element, Node<E> next) {
this.item = element; // 存储元素
this.next = next; // 设置下一个节点
this.prev = prev; // 设置上一个节点
}
}
LinkedList
内部使用双向链表实现
/**
* 将指定的元素添加到列表的尾部。
*
* @param e 要添加到列表的元素
* @return 始终为 true(根据 Java 集合框架规范)
*/
public boolean add(E e) {
linkLast(e); // 在列表的尾部添加元素
return true; // 添加元素成功,返回 true
}
//todo
remove()
:删除第一个节点remove(int)
:删除指定位置的节点remove(Object)
:删除指定元素的节点removeFirst()
:删除第一个节点removeLast()
:删除最后一个节点/**
* 删除指定位置上的元素。
*
* @param index 要删除的元素的索引
* @return 从列表中删除的元素
* @throws IndexOutOfBoundsException 如果索引越界(index < 0 || index >= size())
*/
public E remove(int index) {
checkElementIndex(index); // 检查索引是否越界
return unlink(node(index)); // 删除指定位置的节点,并返回节点的元素
}
/**
* 获取链表中指定位置的节点。
*
* @param index 节点的位置(从 0 开始)
* @return 指定位置的节点
* @throws IndexOutOfBoundsException 如果索引超出范围(index < 0 || index >= size())
*/
Node<E> node(int index) {
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()
方法
大致思路是
删除一共涉及三个节点, 前驱节点, 删除节点, 后驱节点 这是因为一旦节点被删除, 链表就断掉了, 需要重新连接前驱和后驱 拿到这三个节点, 首先进行特殊情况判断
/**
* 从链表中删除指定节点。
*
* @param x 要删除的节点
* @return 从链表中删除的节点的元素
*/
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; // 将链表的头节点设置为要删除节点的下一个节点
//在这种情况下,不能执行 prev.next = next,因为 prev 是 null,会导致空指针异常
} else {
prev.next = next; // 将要删除节点的上一个节点指向要删除节点的下一个节点
x.prev = null; // 将要删除节点的上一个节点设置为空
}
if (next == null) { // 如果要删除节点是最后一个节点
last = prev; // 将链表的尾节点设置为要删除节点的上一个节点
//在这种情况下,不能执行 next.prev = prev,因为 next 是 null,会导致空指针异常
} else {
next.prev = prev; // 将要删除节点的下一个节点指向要删除节点的上一个节点
x.next = null; // 将要删除节点的下一个节点设置为空
}
x.item = null; // 将要删除节点的元素设置为空
size--; // 减少链表的元素个数
return element; // 返回被删除节点的元素
}
remove(Object)
内部也调用了 unlink 方法,只不过在此之前要先找到元素所在的节点:
/**
* 从链表中删除指定元素。
*
* @param o 要从链表中删除的元素
* @return 如果链表包含指定元素,则返回 true;否则返回 false
*/
public boolean remove(Object o) {
if (o == null) { // 如果要删除的元素为 null
for (Node<E> x = first; x != null; x = x.next) { // 遍历链表
if (x.item == null) { // 如果节点的元素为 null
unlink(x); // 删除节点
return true; // 返回 true 表示删除成功
}
}
} else { // 如果要删除的元素不为 null
for (Node<E> x = first; x != null; x = x.next) { // 遍历链表
if (o.equals(x.item)) { // 如果节点的元素等于要删除的元素
unlink(x); // 删除节点
return true; // 返回 true 表示删除成功
}
}
}
return false; // 如果链表中不包含要删除的元素,则返回 false 表示删除失败
}