This is the multi-page printable view of this section. Click here to print.

Return to the regular view of this page.

Java集合框架

1: LinkedList
2:

内容来源:

沉默王二 GitHub 上开源的知识库《Java 进阶之路》
JavaGuide
Geeksforgeeks
菜鸟教程

1 - LinkedList

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 &lt; 0 || index &gt;= 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 表示删除失败
}