Java 数据结构丨链表

基本概念

• 链表对应的英文名称是 Linked List，是一种物理存储单元上非连续、非顺序的数据结构，由若干个节点(node)组成。每个结点包括两个部分：一个是存储数据元素的数据域(data)，另一个是存储下一个结点地址的指针域(next)。

• 链表的第一个节点被称为头结点，最后一个节点被称为尾结点，尾结点的 next 指针指向一个空地址 NULL。

• 链表有很多种不同的类型：单向链表，双向链表以及循环链表......

• 不同于数组的顺序存储，链表在内存中是随机存储。

// 链表节点,变量data存放数据，指针next指向下一个节点
private static class Node{
     int data;
     Node next;
     Node(int data){
         this.data = data;
     }
}

基本操作

1. 查询

时间复杂度：O(n)。

/**
 * 链表操作：查找元素
 * @param index 查找的位置
 **/
public Node get(int index)throws Exception{
    if (index < 0 || index >= size){
        throw new IndexOutOfBoundsException("超出链表节点实际范围！");
    }
    Node temp = head;
    for(int i = 0; i < index; i++){
       temp = temp.next;
    }
    return temp;
}

2. 插入

时间复杂度：O(1)。

/**
 * 链表操作：插入元素
 * @param data 插入的元素
 * @param index 插入的位置
 * */
public void insert(int data, int index)throws Exception{
    if (index<0 || index>size){
        throw new IndexOutOfBoundsException("超出链表节点实际范围！！！");
    }
    Node insertedNode = new Node(data);
    if (size == 0){
        //空链表
        head = insertedNode;
        last = insertedNode;
    }else if (index == 0){
        //插入头部
        insertedNode.next = head;
        head = insertedNode;
    }else if (size == index){
        //插入尾部
        last.next = insertedNode;
        last = insertedNode;
    }else{
        //插入中间
        Node prevNode = get(index-1);
        //将新结点的 next指针指向原来旧结点的 next指针指向的内存地址
        insertedNode.next = prevNode.next;
        //将原来旧结点的 next指针指向新结点的内存地址
        prevNode.next = insertedNode;
    }
    size++;
}

3. 删除

时间复杂度：O(1)。

/**
  * 链表操作：删除元素
  * @param index 删除的位置
  **/
 public Node remove(int index)throws Exception{
     if (index<0 || index>=size){
         throw new IndexOutOfBoundsException("超出链表节点实际范围！！！");
     }
     Node removedNode = null;
     if (index == 0){
         //删除头部节点
         removedNode = head;
         head = head.next;
     }else if (index == size-1){
         //删除尾部节点
         Node prevNode = get(index-1);
         removedNode = prevNode.next;
         prevNode.next = null;
         last = prevNode;
     }else {
         //删除中间节点
         Node prevNode = get(index-1);
         Node nextNode = prevNode.next.next;
         removedNode = prevNode.next;
         //即 a>>b>>c，删除 b，只需要将 c赋值给 a.next即可
         prevNode.next = nextNode;
     }
     size--;
     return removedNode;
 }

循环链表

循环链表是一种特殊的单链表。它与单链表的唯一区别在于尾结点，循环链表的尾结点指针指向链表的头结点。当要处理的数据具有环形结构特点时，特别适合采用循环链表。例如：约瑟夫问题 （Java） - 掘金 ( juejin.cn) 。

public class CircleLinkedList {
    //指向循环链表的第一个结点
    private Node head;
    // 循环链表的长度
    private int length;
    public CircleLinkedList() {
        head = null;
        length = 0;
    }
    public Node getHead() {
        return head;
    }
    public int getLength() {
        return length;
    }

    /**
     * 尾部插入
     * @param newNode
     */
    public void insert(Node newNode) {
        if (head == null) {
            // 循环链表为空时，head 指向新的节点
            head = newNode;
        } else {
            Node temp = head;
            // 找到循环链表最后一个节点
            while (temp.next != head) {
                temp = temp.next;
            }
            // 插入新的节点
            temp.next = newNode;
        }
        // 循环链表新的结点指向 NULL
        newNode.next = head;
        // 循环链表长度加 1
        length++;
    }

    /**
     * 将新的结点插入到指定结点后
     * @param preNode 指定节点
     * @param newNode 新的节点
     */
    public void insert(Node preNode, Node newNode) {
        newNode.next = preNode.next;
        preNode.next = newNode;
        length++;
    }

    /**
     * 删除数据域为指定值的元素
     * @param e
     */
    public void del(int e) {
        Node temp = head;
        while (length >= 0) {
            // 找到数据域为 e 的结点
            if (temp.data == e) {
                if (temp.next == head) {
                    // 第一个节点
                    head = null;
                } else {
                    // 最后一个节点
                    temp.next = temp.next.next;
                }
                // 循环链表长度减 1
                length--;
                return;
            }
            // 找到下一个结点
            temp = temp.next;
        }
    }

    /**
     * 给定被删除元素的前一个结点，删除指定元素
     * @param preNode
     */
    public Node del(Node preNode) {
        Node delNode = preNode.next;
        if (delNode == head) {
            // 维护 head 的指向
            head = head.next;
        }
        // 删除
        preNode.next = preNode.next.next;
        length--;
        return delNode;
    }

    /**
     * 随机访问第 k 个结点
     * @param k
     * @return
     */
    public Node find(int k) {
        if (k <= 0) {
            throw new RuntimeException("输入的参数 k 必须大于 0");
        }
        int cnt = 1;
        Node temp = head;
        // 找到第 k 个元素
        while (cnt != k) {
            temp = temp.next;
            cnt++;
        }
        return temp;
    }

    /**
     * 打印循环链表所有有效节点
     * @return
     */
    public String printCircleLinkedList() {
        StringBuilder sb = new StringBuilder();
        int cnt = 0;
        Node temp = head;
        while (head != null && cnt < getLength()) {
            sb.append(temp.data);
            sb.append(" -> ");
            temp = temp.next;
            cnt++;
        }
        sb.append(", length = ");
        sb.append(length);
        return sb.toString();
    }
}

双向链表

双向链表它的每一个节点除了有数据(data)、后继指针(next)，还有前驱指针(prev)——指向前一个节点的指针。由于多了一个前驱指针,所以双向链表要更占内存，但它的效率更高,也更加实用（支持双向遍历），可以说是“空间换时间”了。 删除情况：

1. 删除节点中含有特定值的节点；

2. 删除给定指针指向的节点。

对于第 1 种情况，无论是单向链表还是双向链表，都需要从头节点开始遍历查找，查找到后，再执行删除操作。 对于第 2 种情况，因为双向链表中拥有前驱指针，只需要 O(1) 的时间复杂度；而单向链表为了找到前驱节点需要遍历，则需要 O(n)。同理，对于“在某个指定节点前插入一个节点”这种情况，双向链表也是 O(1)，单向链表也是 O(n)。除此之外，对于一个有序链表，双向链表的按值查询的效率也比单向链表高一些。

双向循环链表

“缝合怪”：循环链表+双向链表（双向链表首尾相接）。

优劣

• 相较于数组，链表的内存空间消耗更大，用于储存结点指针信息。

• 链表可以克服数组需要预先知道数据大小的缺点，充分利用计算机内存空间，实现灵活的内存动态管理。但是（单向）链表失去了数组根据下标随机读取的优点，想要找到某节点Z只能通过前一个节点Y的 next 指针来寻找，而想要找到节点 Y，又必须通过Y节点的前一个节点X的 next 指针来寻找...要找一个某一节点，必须要从头开始遍历，十分麻烦。链表的随机访问的性能没有数组好，需要O(n)的时间复杂度。

• 数组在进行插入、删除操作时，为了保持内存数据的连续性，需要搬移大量数据，所以时间复杂度为O(n)；而由于不必须按顺序存储，链表在纯粹的插入、删除操作的时候可以达到O(1)；而如果考虑插入、删除操作之前需要遍历查找到元素，那么删除“特定值”操作也需要 O(n)。

• 由于链表的每个结点在内存里都是随机分布的，只是通过指针联系在一起，所以这些结点的地址并不相邻，无法利用 程序的局部性原理 来提前加载到缓存中来提升程序性能。所以，链表的查找、读取性能不及数组。如果数据以查找为主，很少涉及到增加和删除操作，那么选择数组，如果涉及到频繁的插入和删除，或元素所需分配空间过大，那么倾向于选择链表。

应用场景

单链表：

1. 撤销和回退功能。

2. 实现 LRU 缓存淘汰算法。

3. 判断某个字符串是否为回文字符串。

4. 实现图、HashMap等一些高级数据结构。

循环链表：

1. 约瑟夫问题。

2. 操作系统的分时问题。

3. 键盘的缓冲，网络收发数据包的缓冲。

参考

1. 【系统设计】LRU缓存 ( qq.com)

2. 超详细：从认识链表到学会反转链表 ( qq.com)

3. 链表练习 - 掘金 ( juejin.cn)