Java数据结构与算法系列精讲之环形链表
短信预约 -IT技能 免费直播动态提醒
概述
从今天开始, 小白我将带大家开启 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);
}
}
}
到此这篇关于Java 数据结构与算法系列精讲之环形链表的文章就介绍到这了,更多相关Java 环形链表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
