Java 数据结构与算法系列精讲之环形链表

概述

从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.

链表

链表 (Linked List) 是一种递归的动态数据结构. 链表以线性表的形式, 在每一个节点存放下一个节点的指针. 链表解决了数组需要先知道数据大小的缺点, 增加了节点的指针域, 空间开销较大.

链表包括三类:

• 单向链表

• 双向链表

• 循环链表

环形链表

环形链表 (Circular Linked List) 将单链表最后一个节点指向头节点, 即为环形链表. 如图:

环形链表实现

Node 类

// Node类
private class Node<E> {

public E e;  // 元素
   private Node next;  // 下一个节点

// 构造
   public Node(E e) {
       this.e = e;
       this.next = null;
   }

@Override
   public String toString() {
       return e.toString();
   }
}

insert 方法

// 插入数据
public void insert(E e) {

// 创建节点
   Node node = new Node(e);

if (size == 0) {
       head = node;
       head.next = head;
       tail = head;
   } else {
       tail.next = node;
       node.next = tail;
       tail = node;
   }

size ++;
}

remove 方法

// 删除元素
public void remove(int index) {

// 检查索引是否越界
   if (index < 0 || index > size) {
       throw new RuntimeException("Invalid Index");
   }

// 获取index前一个节点
   Node prev = head;
   for (int i = 0; i < index - 1; i++) {
       prev = prev.next;
   }

// 删除数据
   Node retNode = prev.next;
   prev.next = retNode.next;

size --;
}

main

// main
public static void main(String[] args) {

// 创建循环链表
   CircularLinkedList<Integer> circularLinkedList = new CircularLinkedList<>();

// 插入
   for (int i = 0; i < 5; i++) {
       circularLinkedList.insert(i);
       System.out.println(circularLinkedList);
   }

// 删除
   for (int i = 0; i < 2; i++) {
       circularLinkedList.remove(0);
       System.out.println(circularLinkedList);
   }
}

输出结果:

0
0->1
0->1->2
0->1->2->3
0->1->2->3->4
0->2->3->4
0->3->4

完整代码

public class CircularLinkedList<E> {

// Node类
   private class Node<E> {

public E e;  // 元素
       private Node next;  // 下一个节点

// 构造
       public Node(E e) {
           this.e = e;
           this.next = null;
       }

@Override
       public String toString() {
           return e.toString();
       }
   }

// 头节点和尾节点
   private Node head = null;
   private Node tail = null;
   private int size;  // 链表大小

// 构造函数
   public CircularLinkedList() {
       head = new Node(null);
       size = 0;
   }

// 插入数据
   public void insert(E e) {

// 创建节点
       Node node = new Node(e);

if (size == 0) {
           head = node;
           head.next = head;
           tail = head;
       } else {
           tail.next = node;
           node.next = tail;
           tail = node;
       }

size ++;
   }

// 删除元素
   public void remove(int index) {

// 检查索引是否越界
       if (index < 0 || index > size) {
           throw new RuntimeException("Invalid Index");
       }

// 获取index前一个节点
       Node prev = head;
       for (int i = 0; i < index - 1; i++) {
           prev = prev.next;
       }

// 删除数据
       Node retNode = prev.next;
       prev.next = retNode.next;

size --;
   }

// 链表是否为空
   public boolean isEmpty() {
       return size == 0;
   }

@Override
   public String toString() {

StringBuilder builder = new StringBuilder();
       Node cur = head;
       while (cur != tail) {
           builder.append(cur + "->");
           cur = cur.next;
       }
       builder.append(cur);

return builder.toString();
   }

// main
   public static void main(String[] args) {

// 创建循环链表
       CircularLinkedList<Integer> circularLinkedList = new CircularLinkedList<>();

// 插入
       for (int i = 0; i < 5; i++) {
           circularLinkedList.insert(i);
           System.out.println(circularLinkedList);
       }

// 删除
       for (int i = 0; i < 2; i++) {
           circularLinkedList.remove(0);
           System.out.println(circularLinkedList);
       }
   }
}

来源：https://iamarookie.blog.csdn.net/article/details/121904108