数组链表

February 6, 2025

1. 动态数组

动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩缩容，并把增删查改操作进行了封装。

// 创建动态数组
// 不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容
ArrayList<Integer> arr = new ArrayList<>();

for (int i = 0; i < 10; i++) {
    // 在末尾追加元素，时间复杂度 O(1)
    arr.add(i);
}

// 在中间插入元素，时间复杂度 O(N)
// 在索引 2 的位置插入元素 666
arr.add(2, 666);

// 在头部插入元素，时间复杂度 O(N)
arr.add(0, -1);

// 删除末尾元素，时间复杂度 O(1)
arr.remove(arr.size() - 1);

// 删除中间元素，时间复杂度 O(N)
// 删除索引 2 的元素
arr.remove(2);

// 根据索引查询元素，时间复杂度 O(1)
int a = arr.get(0);

// 根据索引修改元素，时间复杂度 O(1)
arr.set(0, 100);

// 根据元素值查找索引，时间复杂度 O(N)
int index = arr.indexOf(666);

2. 链表

在实际的编程语言中，我们使用的链表节点定义如下：

class Node<E> {
    E val;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.val = element;
        this.next = next;
        this.prev = prev;
    }
}

[!NOTE]
1、编程语言标准库一般都会提供泛型，即你可以指定 val 字段为任意类型，而力扣的单链表节点的 val 字段只有 int 类型。
2、编程语言标准库一般使用的都是双链表而非单链表。单链表节点只有一个 next 指针，指向下一个节点；而双链表节点有两个指针，prev 指向前一个节点，next 指向下一个节点。
有了 prev 前驱指针，链表支持双向遍历，但由于要多维护一个指针，增删查改时会稍微复杂一些。

几个关键点

关键点一、同时持有头尾节点的引用

关键点二、虚拟头尾节点

在创建双链表时就创建一个虚拟头节点和一个虚拟尾节点，无论双链表是否为空，这两个节点都存在 —— 这样就不会出现空指针的问题，可以避免很多边界情况的处理。

假设虚拟头尾节点分别是 dummyHead 和 dummyTail，那么一条空的双链表长这样：

dummyHead <-> dummyTail

如果你添加 1,2,3 几个元素，那么链表长这样：

dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail

有了头尾虚拟节点，无论链表是否为空，都只需要考虑在中间插入元素的情况就可以了，这样代码会简洁很多。

虚拟节点是内部实现数据结构的技巧，对外是不可见的。比如按照索引获取元素的 get(index)方法，都是从真实节点开始计算索引，而不是从虚拟节点开始计算。

关键点三、内存泄露？

Java 的垃圾回收的判断机制是看这个对象是否被别人引用，而并不关心这个对象是否还引用着别人。

不过删除节点时，最好还是把被删除节点的指针都置为 null，可能避免一些潜在的问题。

Algorithm