Реализация циклического связанного списка (Java)

1. Введение в циклический связанный список

Круговой связанный список на самом деле является специальнымЕдиный список.

Хвостовой узел односвязного списка указывает на NULL, а хвостовой узел кругового связанного списка указывает на головной узел, образуя кольцо.

2. Вставьте

Вставка кругового связанного списка заключается в изменении указателя соседнего узла. Временная сложность O(1).

Отличие от односвязного списка заключается в том, что при вставке в конец кругового связанного списка вновь вставленный узел должен указывать на головной узел.

как показано на рисунке:

Переведено в код:

  /**
     * 尾部插入
     *
     * @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++;
    }

3. Удалить

Удаление циклического связанного списка такое же, как вставка, и удаление циклического связанного списка может быть завершено путем изменения направления указателя, а временная сложность составляет O (1).

как показано на рисунке:

Переводится в код как:

 /**
     * 删除数据域为指定值的元素
     *
     * @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 = temp.next;
        }
    }

4. Полный код

Node.java

/**
 * @author liyanan
 * @date 2020/1/2 13:44
 */
/**
 * 模拟结点
 */
public class Node {
    /**
     * 存储数据
     */
    public int data;
    /**
     * 指向下一个节点
     */
    public Node next;

    public Node() {
    }

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

CircleLinkedList.java

/**
 * 循环链表的实现（特殊的单链表）
 *
 * @author liyanan
 * @date 2020/1/2 13:16
 */
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;
        }
    }
    
    /**
     * 随机访问第 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();
    }
}