链表理论基础

链表是什么？

链表是一种通过指针串联在一起的线性结构

每一个节点由两部分组成，一部分是「数据域」，一部分是「指针域」，最后一个节点的指针域指向 null

链表类型

单链表

​

双链表

每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

循环链表

循环链表，顾名思义，就是链表首尾相连。

链表存储方式

链表在内存中可不是连续分布的。

链表是通过「指针域的指针」链接在内存中各个节点，每个节点存放着下一个节点的内存地址。

链表的组成单位是 Node 对象

/* 链表节点类 */
class ListNode {
    int val;        // 节点值
    ListNode next;  // 指向下一节点的引用
    ListNode(int x) { val = x; }  // 构造函数
}

链表操作

头插节点

1. 记录头节点
2. 创建新节点，新节点的头节点为null
3. 新节点的 next 为 「步骤1」的头节点
4. 「步骤1」的前驱节点为 新节点

void linkFirst(E e) {
    final Node<E> f = first; // 头节点
    final Node<E> newNode = new Node<>(null, e, f); // 新节点，后驱节点是f
    first = newNode; // 现在头节点是新节点
    if (f == null) // 如果之前的头节点为null
        last = newNode; // 那么现在头节点和尾节点都是 新节点
    else
        f.prev = newNode; // 之间的头节点的前驱节点是新节点
    size++;
}

图片来自：bugstack.cn

尾插节点

void linkLast(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++;
}

图片来自：bugstack.cn

拆链操作

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;
    size--;
    return element;
}

图片来自：bugstack.cn

删除节点

public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

图片来自：bugstack.cn

链表性能分析

插入/删除为 $O(1)$

查询为$O(n)$

问题

• 描述一下链表的数据结构？
• Java 中 LinkedList 使用的是单向链表、双向链表还是循环链表？
• 链表中数据的插入、删除、获取元素，时间复杂度是多少？
• 什么场景下使用链表更合适？