707. 设计链表

1. 题目简介

难度：中等，原题链接：707. 设计链表。

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回 -1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index, val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。
• deleteAtIndex(index)：删除下标为 index 的节点；下标无效时不作修改。

2. 问题分析

按下标读取、插入和删除，都要先分清当前长度与合法位置。读取和删除的下标范围是 [0, 长度)；插入还允许下标等于长度，表示追加到末尾。题目约束保证 0 <= index，因此不需要处理负下标。

链式存储用节点的 next 连接元素，插入、删除时修改链接；数组存储用下标定位元素，中间插入、删除时需要搬移后续元素。下面先给出单链表实现，再用动态数组实现同一组列表操作作对照。Java 的 LinkedList 和 ArrayList 分别采用链式和动态数组存储，下面的代码用于说明这两种存储方式。

3. 代码实现

3.1 单链表实现

用虚拟头节点 root 统一头部与中间位置的操作，实际第一个元素是 root.next，size 记录元素数量。读取时定位目标节点；插入或删除时，定位目标位置的前驱。

getAtIndex(-1) 返回 root，因此头部操作也可以通过 getAtIndex(index - 1) 找到前驱。插入时先让新节点指向原来的后继，再让前驱指向新节点；删除时则让前驱直接跳过目标节点。每次成功插入或删除后，都要同步更新 size。

class MyLinkedList {

    private class ListNode {
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    private ListNode root;
    private int size;

    public MyLinkedList() {
        root = new ListNode(-1, null);

    }

    public int get(int index) {
        ListNode node = getAtIndex(index);
        return node == null ? -1 : node.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        ListNode prev = getAtIndex(index - 1);
        if (prev == null) {
            return;
        }
        ListNode add = new ListNode(val, prev.next);
        prev.next = add;
        size++;
    }

    private ListNode getAtIndex(int index) {
        if (index > size) {
            return null;
        }
        if (index == -1) {
            return root;
        }
        ListNode walk = root;
        for (int i = 0; i <= index; i++) {
            walk = walk.next;
        }
        return walk;
    }

    public void deleteAtIndex(int index) {
        if (index >= size) {
            return;
        }
        ListNode prev = getAtIndex(index - 1);
        if (prev == null) {
            return;
        }
        prev.next = prev.next.next;
        size--;
    }
}

3.2 动态数组实现

category 保存元素，len 是当前元素数量，size 是数组容量。这两个数不同：例如容量为 8、已有 3 个元素时，只有下标 0 到 2 存着有效内容。

插入前，如果容量已满，就申请两倍容量的新数组并复制已有元素。之后把插入位置及其后面的元素从后往前右移一格，再写入新值。删除则从删除位置开始，把后面的元素依次左移一格，最后减少 len。移动方向保证尚未复制的值不会提前被覆盖。

class MyLinkedList {
    
    private int[] category;

    private int len;

    private int size;


    public MyLinkedList() {
        size = 8;
        len = 0;
        category = new int[size];
    }
    
    public int get(int index) {
        return index < len ? category[index] : -1;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(len, val);
    }
    
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > len) {
            return;
        }
        if (len == size) {
            size *= 2;
            int[] newCategory = new int[size];
            for (int i = 0; i < len; i++) {
                newCategory[i] = category[i];
            }
            category = newCategory;
        }
        for (int i = len; i > index; i--) {
            category[i] = category[i - 1];
        }
        category[index] = val;
        len++;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= len) {
            return;
        }
        for (int i = index; i < len - 1; i++) {
            category[i] = category[i + 1];
        }
        len--;
    }
}

4. 复杂度分析

设当前元素数量为 n。要分析一次完整操作的成本，必须把定位节点、移动元素和扩容都算进去：

操作	上面的单链表实现	上面的动态数组实现
按下标读取	O(n)，需要沿 next 查找	O(1)，直接访问数组下标
头部插入	O(1)，前驱就是 root	O(n)，已有元素全部右移
尾部插入	O(n)，没有尾指针，需要查找末尾	均摊 O(1)，发生扩容的一次为 O(n)
任意下标插入或删除	O(n)，先找到前驱，再以 O(1) 修改链接	O(n)，需要搬移后续元素

链表的 O(1) 插入、删除，是指已经拿到前驱后的链接修改，不代表按下标操作的总成本。两种实现都需要 O(n) 空间保存元素；动态数组扩容时还会暂时同时持有新旧数组。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明