【数据结构】线性表 ④ ( 循环链表 / 单循环链表 | 代码示例 - 使用 Java 实现单循环链表 )

韩曙亮

发布于 2023-10-11 16:50:56

2590

发布于 2023-10-11 16:50:56

文章被收录于专栏：韩曙亮的移动开发专栏

一、循环链表 ( 单循环链表 )

在单链表中 ,

将最后一个节点的指针指向第一个节点 , 形成一个闭环 ,

上述头尾相连的单链表称为 " 单循环链表 " ,

简称为 " 循环链表 " ;

在循环链表中 , 没有明确的第一个节点或最后一个节点 ;

循环链表可以模拟环形结构数据 , 如 : 循环队列 ;

二、代码示例 - 使用 Java 实现单循环链表

在下面的代码中 ,

定义节点类 : Node 是循环链表中的节点 , 每个节点都包含 data 数据和指向下一个节点的指针 next ;
定义应用类 : CircularLinkedList 类中 , 定义了单链表的首元素 , 借助该元素 , 可以访问所有的链表数据 ;
新增节点 : 调用 CircularLinkedList#append 函数 , 可以新增一个节点 ,
- 先创建一个新节点 newNode , 然后判断链表首元素 head 是否为空 , 链表首元素为空 , 即链表为空 ;
  - 如果链表为空 , 我们将头指针 head 指向新节点 , 并将新节点的 next 指针指向自身，以形成循环。
  - 如果链表非空 , 我们遍历链表找到最后一个节点 , 并将其 next 指针指向新节点 , 再将新节点的next指针指向头节点 ;

使用 Java 语言实现单循环链表 :

public class Node {
    public int data;
    public Node next;

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

public class CircularLinkedList {
    private Node head;

    public CircularLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
            head.next = head;
        } else {
            Node lastNode = head;
            while (lastNode.next != head) {
                lastNode = lastNode.next;
            }
            lastNode.next = newNode;
            newNode.next = head;
        }
    }

    public void printList() {
        if (head == null) {
            System.out.println("Circular Linked List is empty.");
            return;
        }

        Node current = head;
        do {
            System.out.print(current.data + " ");
            current = current.next;
        } while (current != head);
    }

    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        cll.append(1);
        cll.append(2);
        cll.append(3);
        cll.append(4);

        cll.printList();
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-05-19，如有侵权请联系 cloudcommunity@tencent.com 删除

java