人生设计师
这是系列文章，每篇文章末尾均附有源代码地址。目的是通过模拟集合框架的简单实现，从而对常用的数据结构和
java集合有个大概的了解。当然实现没有java集合的实现那么复杂，功能也没有那么强大，但是可以通过这些简单的实现窥探到底层的一些共性原理。
一. 什么是循环单链表?
循环单链表是指单链表的最后一个结点的next域指向单链表的头结点head，使单链表成为环形结构。设rear是单链表的尾结点，rear.next=head使得一条单链表成为循环单链表，如下图所示：
当head.next==head满足时，循环单链表为空，如下图所示：
二. 循环单链表的实现
1.定义循环单链表
循环单链表类CircularSinglyLinkedList继承带头结点的单链表类HeadSinglyLinkedList，二者相同的方法不再介绍，请参见之前的文章自己实现集合框架(五):带头结点单链表的实现，只是在尾插入元素，尾移除元素和清空元素的时候会有不一样的地方，也就是需要把尾结点的next域指向head结点，CircularSinglyLinkedList类定义如下所示：
package org.light4j.dataStructure.linearList.linkList.circular;
import org.light4j.dataStructure.linearList.linkList.Node;
import org.light4j.dataStructure.linearList.linkList.head.HeadSinglyLinkedList;
/**
* <p>
* 循环单链表类
* </p>
*
* @author longjiazuo
*
* @param <E>
*/
public class CircularSinglyLinkedList<E> extends HeadSinglyLinkedList<E> {
/**
* 构造空单链表
*/
public CircularSinglyLinkedList() {
this.head = new Node<E>(null);
this.rear = this.head;
this.head.next = this.head;
this.n = 0;
}
}
2. 循环单链表的插入
/**
* 在指定位置插入非空的指针对象
*/
@Override
public boolean add(int index, E element) {
if (element == null) {// 不允许插入非空元素
return false;
}
if (index >= this.n) {// 尾插入,插入在最后
this.add(element);
} else {
Node<E> p = this.head;
int i = 0;
while (p.next != null && i < index) {
i++;
p = p.next;
}
// 下面操作可以包含头插入和中间插入
Node<E> q = new Node<E>(element);
q.next = p.next;
p.next = q;// 将q结点插入到p结点之后
this.n++;
return true;
}
return false;
}
/**
* 在单链表的最后插入元素对象,时间复杂度是O(1)
*/
@Override
public boolean add(E element) {
if (element == null) {// 不允许插入非空元素
return false;
}
this.rear.next = new Node<E>(element);// 尾插入
this.rear = this.rear.next;// 移动尾指针
this.rear.next = this.head;//把尾结点的next域指向head结点
this.n++;// 链表长度增加
return true;
}
代码解释
① 在尾插入的时候，需要把尾结点的
next域指向head结点：this.rear.next = this.head;
3. 循环单链表的移除
/**
* 移除索引index处的结点,操作成功返回被移除的对象,失败则返回null
*/
@Override
public E remove(int index) {
E old = null;
if (index >= 0) {// 头删除,中间删除,尾删除
Node<E> p = this.head;
int i = 0;
while (p.next != null && i < index) {// 从头结点开始遍历,定位到待删除结点的前驱结点
i++;
p = p.next;
}
if (p.next != null) {
old = p.next.data;
if (p.next == this.rear) {// 如果p结点的后一个结点是尾结点,则移除之后尾结点指针前移
this.rear = p;
this.rear.next = this.head;//把尾结点的next域指向head结点
}
p.next = p.next.next;// 删除p结点的后继结点
this.n--;// 链表长度减少
return old;
}
}
return old;
}
代码解释
① 在尾移除的时候，需要把尾结点的
next域指向head结点：this.rear.next = this.head;
4. 清空循环单链表
@Override
public void clear() {
this.head.next = this.head;
this.n = 0;
}
代码解释
① 清空循环单链表，需要执行
this.head.next = this.head;
5. 重写toString()方法
由于循环单链表的最后一个结点的next域不为空，需要重写toString()，代码如下：
@Override
public String toString() {// 返回所有元素值对应的字符串
String str = "(";
Node<E> p = this.head.next;
while (p.data != null) {
str += p.data.toString();
p = p.next;
if (p != null) {
str += ", ";
}
}
return str + ")";
}
三.测试
测试代码如下所示：
package org.light4j.dataStructure.linearList.linkList.circular;
import org.light4j.dataStructure.linearList.LList;
public class Test {
public static void main(String[] args) {
LList<String> list = new CircularSinglyLinkedList<String>();
for (int i = 0; i < 10; i++) {
list.add(0, new String((char) ('A' + i) + ""));
}
System.out.println(list.toString());
System.out.println(list.get(1));//获取第一个元素
list.remove(0);// 移除第一个元素
System.out.println(list.toString());
}
}
运行效果如下图所示：
四.源代码示例
公众号ID：longjiazuoA
未经允许不得转载：人生设计师 » 自己实现集合框架(七):循环单链表的实现