数据结构---链表

1. 简介

链表（Linked List）是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针（或引用）。链表的一个主要优点是能够高效地插入和删除元素，尤其是在数组中需要移动大量元素的情况下。

1.1 链表的基本操作

1. 插入：可以在链表的任意位置插入新节点。

2. 删除：可以从链表的任意位置删除节点。

3. 查找：遍历链表查找特定的节点。

4. 更新：修改链表中某个节点的值。

1.2 链表类型

链表有多种变体，每种类型在特定场景下有不同的应用。

• 单链表适用于简单的数据结构，头部插入和删除高效，适合实现栈、队列等数据结构。

• 双链表适用于需要频繁从两端或中间插入、删除节点的场景，适合实现双向队列、LRU缓存等。

• 循环链表适用于需要循环访问或周期性任务调度的场景，适合实现循环队列、约瑟夫问题等。

1.3 比较

2. 单链表

单链表是最基本的链表类型，它的每个节点只包含一个指向下一个节点的指针。每个节点包含两个部分：数据域和指针域（指向下一个节点的指针）。

特点：

• 只能从头到尾进行单向遍历。

• 插入和删除操作通常比较高效，尤其在头部插入删除时。

class SinglyLinkedList {
    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;

    // 插入元素
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }

    // 打印链表
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}

3. 双链表

双链表是每个节点都有两个指针，一个指向下一个节点，另一个指向前一个节点。相比于单链表，双链表允许在两端（头尾）插入或删除节点，操作更灵活。

特点：

• 可以在两个方向（前后）进行遍历。

• 删除节点时更加灵活，可以直接访问前驱节点。

• 每个节点需要更多的内存来存储两个指针。

class DoublyLinkedList {
    static class Node {
        int data;
        Node next;
        Node prev;

        Node(int data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    private Node head;

    // 插入元素
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.prev = temp;
        }
    }

    // 打印链表
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " <-> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}

4. 循环链表

循环链表是链表的变体，其中最后一个节点的指针指向头节点，形成一个环。循环链表可以是单向的（单循环链表）或双向的（双循环链表）。

特点：

• 可以从任意节点开始遍历，遍历过程中可以循环回到起点。

• 适合需要循环访问的场景，如实现循环队列、约瑟夫问题等。

4.1 单向循环链表

class CircularLinkedList {
    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;

    // 插入元素
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head; // 成环
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head; // 成环
        }
    }

    // 打印链表
    public void printList() {
        if (head == null) return;
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("(back to head)");
    }
}

4.2 双向循环链表

class CircularDoublyLinkedList {
    static class Node {
        int data;
        Node next;
        Node prev;

        Node(int data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    private Node head;

    // 插入元素
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
            newNode.prev = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.prev = temp;
            newNode.next = head;
            head.prev = newNode; // 将头节点的prev指针指向新节点
        }
    }

    // 打印链表
    public void printList() {
        if (head == null) return;
        Node temp = head;
        do {
            System.out.print(temp.data + " <-> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("(back to head)");
    }
}

不积跬步，无以至千里 --- xiaokai