数据结构进阶：链表原理与 Java 实现

数据结构进阶：链表原理与 Java 实现

1. ArrayList 的缺陷

通过源码可知，ArrayList 底层使用数组来存储元素。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // ...
    // 默认容量是 10
    private static final int DEFAULT_CAPACITY = 10;
    // ...
    // 数组：用来存储元素
    transient Object[] elementData;
    // non-private to simplify nested class access
    // 有效元素个数
    private int size;

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
        }
    }
    // ...
}

由于其底层是一段连续空间，当在 ArrayList 任意位置插入或者删除元素时，就需要将后续元素整体往前或者往后搬移，时间复杂度为 O(n)，效率比较低。因此 ArrayList 不适合做任意位置插入和删除比较多的场景。为此，Java 集合中引入了 LinkedList，即链表结构。

2. 链表

2.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。

链表的结构类似于火车车厢的连接方式。

实际中链表的结构非常多样，以下情况组合起来就有 8 种链表结构：

1. 单向或者双向
2. 带头或者不带头
3. 循环或者非循环

虽然有这么多的链表结构，但我们重点掌握两种：

• 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等。另外这种结构在笔试面试中出现很多。
• 无头双向链表：在 Java 的集合框架库中 LinkedList 底层实现就是无头双向循环链表。

2.2 链表的实现

定义一个接口：

public interface IList {
    // 头插法
    void addFirst(int data);
    // 尾插法
    void addLast(int data);
    // 任意位置插入，第一个数据节点为 0 号下标
    void addIndex(int index, int data);
    // 查找是否包含关键字 key 是否在单链表当中
    boolean contains(int key);
    // 删除第一次出现关键字为 key 的节点
    void remove(int key);
    // 删除所有值为 key 的节点
    void removeAllKey(int key);
    // 得到单链表的长度
    int size();
    // 清空单链表
    void clear();
    // 遍历单链表
    void display();
    // 创建单链表
    void create();
}

定义一个 MySingList 类：准备工作是 MySingList 要继承 IList 接口的所有方法。

public class MySingList implements IList {
    // 定义单链表节点
    static class ListNode {
        public int val;
        public ListNode next;
        // next 存的是下一个节点的地址，next 引用类型是 ListNode 类型的引用

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

    // 定义一个头结点
    public ListNode head;

创建一个单链表：

@Override
public void create() {
    ListNode listNode1 = new ListNode(11);
    ListNode listNode5 = new ListNode(22);
    ListNode listNode4 = new ListNode(33);
    ListNode listNode3 = new ListNode(44);
    ListNode listNode2 = new ListNode(55);
    
    listNode1.next = listNode2;
    listNode2.next = listNode3;
    listNode3.next = listNode4;
    listNode4.next = listNode5;
    
    this.head = listNode1; // 将插入的第一个节点定义为头节点
}

遍历这个单链表：

@Override
public void display() {
    // 定义一个 cur，让 cur 去走，head 不变，才能在遍历以后找到 head
    ListNode car = head;
    while (car != null) {
        System.out.println(car.val + " ");
        car = car.next; // 如何从当前位置走到下一个节点位置
    }
}

头插法：

// 头插法；时间复杂度：O(1)
@Override
public void addFirst(int data) {
    ListNode listNode = new ListNode(data);
    if (this.head == null) {
        this.head = listNode;
    } else {
        listNode.next = this.head;
        this.head = listNode;
    }
}

不同位置添加的时间复杂度不同，常见的错误观点是认为所有添加操作都是 O(1)。在尾部添加需要 O(n)，头部添加为 O(1)，在任意位置则平均为 O(n)。了解这些有助于优化链表操作的效率。

尾插法：

// 尾插法时间复杂度：O(n)
@Override
public void addLast(int data) {
    ListNode car = this.head;
    ListNode listNode = new ListNode(data);
    if (this.head == null) {
        this.head = listNode;
    } else {
        // 找到最后一个节点
        while (car.next != null) {
            car = car.next;
        }
        // car 现在指向最后一个节点
        car.next = listNode;
    }
}

在链表尾部添加（addLast()）需要从头遍历，时间复杂度为 O(n)。

任意位置插入，第一个数据节点为 0 号下标：

// 随便插入
private ListNode search(int index) {
    ListNode car = this.head;
    int count = 0;
    while (count != index - 1) {
        car = car.next;
        count++;
    }
    return car;
}

@Override
public void addIndex(int index, int data) {
    if (index < 0 || index > size()) {
        System.out.println("不合法");
        throw new IllegalArgumentException("插入元素下标异常" + data);
    }
    if (index == 0) {
        addFirst(data);
        return;
    }
    if (index == size()) {
        addLast(data);
        return;
    }
    ListNode car = search(index);
    ListNode node = new ListNode(data);
    node.next = car.next;
    car.next = node;
}

当在任意位置插入的时候，要考虑的情况有很多：

1. 当 index < 0 || index > size() 的时候，抛出一个异常
2. 当 index 为 0 的时候，头插法
3. 当 index 为 size() 的时候，尾插法
4. 正常的插入法

查找是否包含关键字 key 是否在单链表当中：

@Override
public boolean contains(int key) {
    ListNode car = this.head;
    while (car != null) {
        if (car.val == key) {
            return true;
        }
        car = car.next;
    }
    return false;
}

删除第一次出现关键字为 key 的节点：

@Override
public void remove(int key) {
    if (this.head == null) {
        System.out.println("无法删除");
        return;
    }
    if (this.head.val == key) {
        this.head = this.head.next;
        return;
    }
    ListNode car = searchPrev(key);
    if (car == null) {
        System.out.println("没有要删除的数字");
        return;
    } else {
        ListNode del = car.next; // 通过 car.next 找到 del 的位置
        car.next = del.next;     // 然后就可以自己看懂
    }
}

// 写一个方法，找到关键字看的前一个节点的地址
private ListNode searchPrev(int key) {
    ListNode car = this.head;
    while (car.next != null) {
        if (car.next.val == key) {
            return car;
        }
        car = car.next;
    }
    return null;
}

删除所有值为 key 的节点：

@Override
public void removeAllKey(int key) {
    if (this.head == null) {
        return;
    }
    ListNode prev = head;
    ListNode car = head.next;
    while (car != null) {
        if (car.val == key) {
            prev.next = car.next;
            car = car.next;
        } else {
            prev = car;
            car = car.next;
        }
    }
    if (head.val == key) {
        head = head.next;
    }
}

得到单链表的长度：

@Override
public int size() {
    ListNode car = head;
    int count = 0;
    while (car != null) {
        count++;
        car = car.next;
    }
    return count;
}

清空链表：

@Override
public void clear() {
    ListNode car = this.head;
    while (car != null) {
        ListNode carNext = car.next; // 定义一个变量把 car 的 next 记录下
        /* car.val=null; 如果是一个应用数据类型，那么才写这个，如果不是 car.next=null 就可以清除完毕 */
        car.next = null;
        car = carNext;
    }
    head = null; // 上面的循环走完，但是 head 还没有置空，要手动把 head 置空
}

3. 链表面试题

1. 删除链表中等于给定值 val 的所有节点。
2. 反转一个单链表。
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
4. 输入一个链表，输出该链表中倒数第 k 个结点。
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
6. 编写代码，以给定值 x 为基准将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的结点之前。

4. LinkedList 的使用

4.1 什么是 LinkedList

LinkedList 的底层是双向链表结构。由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。

在集合框架中，LinkedList 也实现了 List 接口。

【说明】

1. LinkedList 实现了 List 接口
2. LinkedList 的底层使用了双向链表
3. LinkedList 没有实现 RandomAccess 接口，因此 LinkedList 不支持随机访问
4. LinkedList 的任意位置插入和删除元素时效率比较高，时间复杂度为 O(1)
5. LinkedList 比较适合任意位置插入的场景

4.2 LinkedList 的使用

1. LinkedList 的构造

public static void main(String[] args) {
    // 构造一个空的 LinkedList
    List<Integer> list1 = new LinkedList<>();
    List<String> list2 = new java.util.ArrayList<>();
    list2.add("JavaSE");
    list2.add("JavaWeb");
    list2.add("JavaEE");
    // 使用 ArrayList 构造 LinkedList
    List<String> list3 = new LinkedList<>(list2);
}

LinkedList 的其他常用方法介绍

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    list.add(1); // add(elem): 表示尾插
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    System.out.println(list.size());
    System.out.println(list);
    
    // 在起始位置插入 0
    list.add(0, 0);
    // add(index, elem): 在 index 位置插入元素 elem
    System.out.println(list);
    
    list.remove(); // remove(): 删除第一个元素，内部调用的是 removeFirst()
    list.removeFirst(); // removeFirst(): 删除第一个元素
    list.removeLast(); // removeLast(): 删除最后元素
    list.remove(1); // remove(index): 删除 index 位置的元素
    System.out.println(list);
    
    // contains(elem): 检测 elem 元素是否存在，如果存在返回 true，否则返回 false
    if (!list.contains(1)) {
        list.add(0, 1);
        list.add(1);
        System.out.println(list);
        System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个 elem 的位置
        System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个 1 的位置
    }
    
    int elem = list.get(0); // get(index): 获取指定位置元素
    list.set(0, 100);       // set(index, elem): 将 index 位置的元素设置为 elem
    System.out.println(list);
    
    // subList(from, to): 用 list 中 [from, to) 之间的元素构造一个新的 LinkedList 返回
    List<Integer> copy = list.subList(0, 3);
    System.out.println(list);
    System.out.println(copy);
    
    list.clear(); // 将 list 中元素清空
    System.out.println(list.size());
}

3. LinkedList 的遍历

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    System.out.println(list.size());
    
    // foreach 遍历
    for (int e : list) {
        System.out.print(e + " ");
    }
    System.out.println();
    
    // 使用迭代器遍历---正向遍历
    ListIterator<Integer> it = list.listIterator();
    while (it.hasNext()) {
        System.out.print(it.next() + " ");
    }
    System.out.println();
    
    // 使用反向迭代器---反向遍历
    ListIterator<Integer> rit = list.listIterator(list.size());
    while (rit.hasPrevious()) {
        System.out.print(rit.previous() + " ");
    }
    System.out.println();
}

5. ArrayList 和 LinkedList 的区别

特性	ArrayList	LinkedList
底层结构	动态数组	双向链表
内存分配	连续内存	离散内存
随机访问	支持 (O(1))	不支持 (O(n))
插入/删除	慢 (需移动元素)	快 (O(1), 仅修改指针)
内存占用	较小	较大 (每个节点需额外指针)
线程安全	否	否

总结来说，如果需要频繁随机访问，选择 ArrayList；如果需要频繁在中间插入或删除，选择 LinkedList。