JAVA 数据结构链表操作循环链表

什么是链表

链表（Linked List）是一种常见的基础数据结构，它可以存储一个线性序列，但与数组不同的是，链表中的元素并不是在内存中连续存储的，而是通过指针将它们链接在一起。

链表由一系列节点组成，每个节点包含两部分：数据和指向下一节点的指针。最后一个节点的指针指向 NULL 表示链表的结尾。

链表常见的操作有：插入、删除、查找、遍历等。其中，插入和删除操作是链表的特点之一，因为链表中的元素并不是在内存中连续存储的，对于插入和删除操作并没有数组那样的位移操作，这也使得链表的插入和删除操作效率比数组高。而查找和遍历操作则需要使用指针进行相应的操作。

常见的链表类型

在链表的实现中，有两种常见的类型：单向链表和双向链表。它们的区别在于节点的指针个数不同，单向链表只有指向下一节点的指针，而双向链表有指向下一节点和前一节点的指针。

此外，在循环链表中，最后一个节点的指针不为 NULL，而是指向链表的头节点，这样链表的开头和结尾就可以随意切换，可以实现循环递归操作。

JAVA 中的链表实现

JAVA 中的链表可以通过自己的类来实现，也可以使用 JAVA 中提供的集合类来实现。对于后者，常见的链表类有 LinkedList 和 ArrayDeque。

LinkedList 类实现了 List 接口，它包含了双向链表的实现，同时还实现了 Queue 接口，可以当作队列来使用。

ArrayDeque 类同样实现了 Queue 接口，它使用数据结构双端队列来实现，操作效率比 LinkedList 更高。

以下为在 Java 中使用链表模拟循环队列的示例代码：

import java.util.LinkedList;
import java.util.Queue;

public class CircularQueue {
    private int size;

    private Queue<Integer> queue;

    public CircularQueue(int size) {
        this.size = size;
        this.queue = new LinkedList<>();
    }

    public boolean enQueue(int value) {
        if (queue.size() == size) {
            return false;
        }
        queue.add(value);
        return true;
    }

    public boolean deQueue() {
        if (queue.isEmpty()) {
            return false;
        }
        queue.remove();
        return true;
    }

    public int Front() {
        if (queue.isEmpty()) {
            return -1;
        }
        return queue.peek();
    }

    public int Rear() {
        if (queue.isEmpty()) {
            return -1;
        }
        return ((LinkedList<Integer>) queue).getLast();
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public boolean isFull() {
        return queue.size() == size;
    }
}

链表操作循环链表的示例

示例1：Java 实现循环链表

public class Node {
    int val;

    Node next;

    public Node(int data) {
        this.val = data;
    }
}

public class CircleLinkList {

    private Node head;

    public CircleLinkList(int num) {
        this.head = null;
        if (num > 0) {
            Node pre = null;
            for (int i = 1; i <= num; i++) {
                Node cur = new Node(i);
                if (head == null) {
                    head = cur;
                } else {
                    pre.next = cur;
                }
                pre = cur;
            }
            pre.next = head;
        }
    }

    public int size() {
        int size = 0;
        Node cur = head;
        while (cur != null && (cur.next != head || size == 0)) {
            size++;
            cur = cur.next;
        }
        return size;
    }

    public int get(int index) {
        Node cur = head;
        int count = 0;
        while (cur != null && (cur.next != head || count == 0)) {
            if (count == index) {
                return cur.val;
            }
            count++;
            cur = cur.next;
        }
        return -1;
    }

    public void visualize() {
        Node cur = head;
        while (cur != null && cur.next != head) {
            System.out.print(cur.val + "->");
            cur = cur.next;
        }
        if (cur != null) {
            System.out.print(cur.val);
        }
        System.out.println();
    }
}

以上代码实现了一个循环链表，通过构造方法创建了一个 num 个节点的循环链表。size() 方法用于获取循环链表的长度，get(int index) 方法用于获取循环链表中对应索引位置的元素，visualize() 方法用于将循环链表进行输出。

示例2：Java 实现链表加法

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int x) {
        val = x;
    }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

以上代码实现了两个链表的加法操作，将两个链表中的元素进行加法运算，得到结果链表。其中，l1 和 l2 为两个链表的头节点，head 和 tail 分别表示结果链表的头节点和尾节点，carry 表示进位，while 循环用于遍历链表进行加法运算。