线性表——单向循环链表

1、单向循环链表（SingleCircleLinkedList）

单向循环链表与单向链表的唯一区别是：单向循环链表尾节点的next指向头节点，构成了一个循环。

注：

• 循环链表虽然首尾相连，但并不表示该链表没有头节点和尾结点。
• 循环链表的头节点是第一个添加的节点，并不是环中的任意节点都可能是头节点。

2、单向循环链表的设计

（1）类的结构设计

在编程之前，我们需要先对单向循环链表类（SingleCircleLinkedList）的结构进行设计。

单向循环链表类所需要的成员与单向链表类完全一样，主要包括：

• 链表存放元素的数量。

  private int size;

  size = 元素（Element）数目 = 节点（Node）数目。

• 第一个节点的引用。

  private Node<E> first;

  first指向链表的第一个节点。

• 内部静态节点（Node）类。

  由于该节点类仅供链表类使用，因此，需将该节点类定义为链表类的内部类。该类的成员包括：

  • 该节点内部的泛型元素

    E element;

    泛型元素既可以是基本数据类型，也可以是类的对象。

  • 下一个节点的引用

    Node<E> next;

    next指向链表的下一个节点。

  • 构造函数

  • 析构函数（Java语言没有）

    **注：**内部类的成员可以不写访问权限。

• 接口函数

**注：**因为链表不需要预先分配内存，所以SingleCircleLinkedList不用写构造函数。

（2）接口设计

单向循环链表的接口也与单向链表完全一样，主要包括：

• int size(); //元素的数量
• boolean isEmpty(); //是否为空
• boolean contains(E element); //是否包含某元素
• E get(int index); //获取index位置对应的元素
• E set(int index, E element); //设置index位置的元素（覆盖）
• void add(E element); //添加元素到尾部
• void add(int index, E element); //在index位置添加元素
• E remove(int index); //删除index位置对应的元素
• int indexOf(E element); //查看元素的位置
• void clear(); //清除所有元素

**注：**接口是供别人在外部通过对象调用的，所以要设计成公有（public）成员。

3、单向循环链表的实现

3.1、编程实现

在单向链表项目的基础上：

①再新建一个名称为SingleCircleLinkedList（包名为：com.atangbiji）的类，用来自己实现单向循环链表；

②仍然使用名称为Main（包名为：com.atangbiji）的类，来调用（测试）自己封装的单向循环链表。

③接口实现，我们这里直接考虑链表元素均为泛型的情况。

（1）定义私有成员变量和内部静态节点（Node）类

SingleCircleLinkedList.java文件：

package com.atangbiji;

public class SingleCircleLinkedList<E> {
	private int size;	//链表存放元素的数量
	private Node<E> first;	//第一个节点的引用
	
	//内部静态节点类
	private static class Node<E> {
		E element;	//该节点内部的泛型元素
		Node<E> next;	//下一个节点的引用
		
		//构造函数
		public Node(E element, Node<E> next) {
			this.element = element;
			this.next = next;
		}
	}
}

（2）实现size()接口

SingleCircleLinkedList.java文件：

/*
 * 元素的数量
 * @param
 * @return 
 * */
public int size() {
	return size;	//直接返程size成员变量即可
}

（3）实现isEmpty()接口

SingleCircleLinkedList.java文件：

/*
 * 是否为空
 * @param
 * @return 
 * */
public boolean isEmpty() {
	return size == 0;	//size为0为空，否则不为空
}

（4）实现get(int index)接口

• 获取索引为index的节点对象

  为了方便获取任意节点，我们定义一个私有方法Node用来获取索引为index的节点。

  SingleCircleLinkedList.java文件：

  /*
   * 获取索引为index的节点对象
   * @param: index
   * @return：索引为index的节点对象
   * */
  private Node<E> node(int index) {
  	//判断索引是否越界
  	if (index < 0 || index >= size) {
  		throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);//抛出异常
  	}
  	//从前向后找到第index个节点
  	Node<E> node = first;
  	for (int i = 0; i < index; i++) {
  		node = node.next;
  	}
  	return node;
  }

• 获取节点元素

  获取单向循环链表索引为index的元素，只需：

  ①首先从链表中获取索引为index的节点对象；
  
  ②再从该节点对象中获取其中的元素即可。

  SingleCircleLinkedList.java文件：

  /*
   * 获取index位置对应的元素
   * @param: index
   * @return 
   * */
  public E get(int index) {
  	return node(index).element;
  }

（5）实现set(int index, E element)接口

类似地，设置单向循环链表索引为index的元素，只需：

①首先从链表中获取索引为index的节点对象;

②再设置该节点对象中的元素即可。

SingleCircleLinkedList.java文件：

/*
 * 设置index位置的元素（覆盖）
 * @param: index
 * @param: element
 * @return: 原来的元素
 * */
public E set(int index, E element) {
	//从链表中获取索引为index的节点对象
	Node<E> node = node(index);
	E old = node.element;
	//设置该节点对象中的元素
	node.element = element;
	
	return old;
}

（6）实现indexOf(E element)接口

只需遍历链表中的元素，判断链表中是否存在该元素即可。若存在，返回索引。若不存在，返回-1。

链表的indexOf(E element)接口与动态数组的indexOf(E element)接口类似，这里不再赘述。

SingleCircleLinkedList.java文件：

private static final int ELEMENT_NOT_FOUND = -1; //未找到
/*
 * 查看元素的位置
 * @param: element
 * @return: 元素的位置
 * */
public int indexOf(E element) {
	//若元素为空（null）
	if (element == null) {
		//遍历链表
		Node<E> node = first;
		for (int i = 0; i < size; i++) {
			// node.element可以是null，也可以不是null。
			if (node.element == null) {
				return i;
			}
			node = node.next;
		}
	}else {
		//若元素不为空（null）。
		//遍历链表
		Node<E> node = first;
		for (int i = 0; i < size; i++) {
			// node.element可以是null，也可以不是null。
			if(element.equals(node.element))
			{
				return i;
			}
			node = node.next;
		}
	}
	return ELEMENT_NOT_FOUND;
}

（7）实现contains(E element)接口

在链表中查找该元素，若返回不为-1，则说明该元素存在。

SingleCircleLinkedList.java文件：

/*
 * 是否包含某元素
 * @param: element
 * @return 
 * */
public boolean contains(E element) {
	return indexOf(element) != ELEMENT_NOT_FOUND;
}

（8）实现clear()接口

清空链表只需将所有节点的内存释放，同时将size置为0即可。

SingleCircleLinkedList.java文件：

/*
 * 清除所有元素
 * @param
 * @return
 * */
public void clear() {
	first = null;	//将第一个节点的引用设为空（null），即可实现所有节点的内存释放。
	size = 0;
}

注：Java中，将第一个节点的引用设为空（null），即可实现所有节点的内存释放。

**附：**为了证明该方法的确释放了所有节点的内存，我们同样可以在内部静态节点（Node）类中重写Java中自带的finalize()方法进行测试。测试过程与动态数组泛化后的clear()接口测试方法类似，这里不再赘述。

（9）实现remove(int index)接口

与单向链表一样，删除单向循环链表中某一节点的元素只需：

①获取被删除节点的前一节点；

②断开被删除节点与前一节点的连接，并直接将其前一节点与后一节点相连；

③链表存放元素的数量-1。

注意分析头节点（index=0）和size=1的情况。

**注：**由于node(int index)方法中也用到了first，所以当index==0时，我们要在first指向新节点之前先获取尾节点。否则，再通过node(size -1)获取尾节点，可能会越界。

• 删除一般节点：

  

• 当index=0时：

  

• 当size=1时：

  

SingleCircleLinkedList.java文件：

/*
 * 删除index位置对应的元素
 * @param: index
 * @return: 被删除的元素
 * */
public E remove(int index) {
	//被删除结点
	Node<E> removeNode = node(index);
	
	if (1 == size) {
		//当删除单向循环链表中唯一存在的元素时，直接让first指向空（null）即可
		first = null;
		
	} else if (0 == index) {
		//1、获取被删除节点的前一节点
		Node<E> prevNode = node(size -1);
		
		//2、断开被删除节点与前一节点的连接，并直接将其前一结点与后一节点相连
		prevNode.next = removeNode.next;
		
		//若要删除链表中的第一个元素，直接将first指向第二个元素
		first = removeNode.next;
	} else {
		//1、获取被删除节点的前一节点
		Node<E> prevNode = node(index - 1);
		//2、断开被删除节点与前一节点的连接，并直接将其前一结点与后一节点相连
		prevNode.next = removeNode.next;
	}
	
	//3、链表存放元素的数量-1
	size--;
	
	return removeNode.element;
}

（10）实现add(int index,E element)接口

链表添加新元素不用考虑是否需要扩容的问题。与单向链表一样，单向循环链表在index处添加新元素只需：

①创建一个新节点；

②分别获取新节点的前一节点和后一节点；

③断开index结点与前一结点的连接，并将新节点分别与前一节点和后一节点相连；

④链表存放元素的数量+1。

由于单向循环链表只是尾节点的next要指向首节点。所以，一般情况下，单向循环链表的插入元素操作和单向链表的插入元素操作没有任何变化。只当在头部和size=0时插入元素两者才有区别。

注意分析头节点（index=0）和size=0的情况。

**注：**由于node(int index)方法中也用到了first，所以当index==0时，我们要在first指向新节点之前先获取尾节点。否则，再通过node(size -1)获取尾节点，可能会越界。

• 添加一般节点：

  

• 当index=0时：

  

• 当size=0时：

  

  SingleCircleLinkedList.java文件：

  /*
   * 在index位置添加元素
   * @param: index
   * @param: element
   * @return
   * */
  public void add(int index,E element) {
  	//判断索引是否越界
  	if (index < 0 || index > size) {
  		throw new IndexOutOfBoundsException("索引出错，Index = " + index +"; Size =" + size);//抛出异常
  	}
  	if (0 == size) {
  		
  		//1、创建一个新结点
  		Node<E> newNode = new Node<E>(element,null);
  		
  		//2、分别获取新节点的前一节点和后一节点
  		first = newNode;
  		newNode.next = newNode;
  		
  	}else if (0 == index) {
  			
  		//1、创建一个新结点
  		Node<E> newNode = new Node<E>(element,null);
  			
  		//2、分别获取新节点的前一节点和后一节点
  		Node<E> preNode = node(size - 1);//获取新节点的前一结点（即：index结点的前一结点）
  		Node<E> nextNode = first;//获取新节点的后一结点（即：index节点）
  			
  		//3、断开index结点与前一结点的连接，并将新节点分别与前一节点和后一节点相连
  		first = newNode;
  		newNode.next = nextNode;
  		
  		//让最后一个节点指向新的头节点
  		preNode.next = newNode;
  		
  	} else {
  		
  		//1、创建一个新结点
  		Node<E> newNode = new Node<E>(element,null);
  		
  		//2、分别获取新节点的前一节点和后一节点
  		Node<E> preNode = node(index - 1);//获取新节点的前一结点（即：index结点的前一结点）
  		Node<E> nextNode = preNode.next;//获取新节点的后一结点（即：index节点）
  		
  		//3、断开index结点与前一结点的连接，并将新节点分别与前一节点和后一节点相连
  		preNode.next = newNode;
  		newNode.next = nextNode;
  	}
  	//4、链表存放元素的数量+1
  	size++;
  }

（11）实现add(E element)接口

add(E element)接口是add(int index,E element)接口的特例。我们只需在size处添加新元素即可。

SingleCircleLinkedList.java文件：

/*
 * 添加元素到尾部
 * @param: element
 * @return 
 * */
public void add(E element) {
	add(size,element);
}

（12）打印链表中的所有元素

同动态数组一样，为了打印对象链表中的所有元素，我们可以通过重写（也称覆盖）toString()方法，并在其中完成字符串的拼接的方式即可实现。

为了更加直观地展现单向循环链表，我们在输出各节点元素时打印**“该节点元素→下一节点元素”**。

注：Java中字符串拼接建议使用StringBuilder类。

SingleCircleLinkedList.java文件：

/*
 * 打印链表中的所有元素：重载toString()函数
 * @param
 * @return 链表元素
 * */
@Override
public String toString() {
	//新建StringBuilder
	StringBuilder string = new StringBuilder();
	
	//拼接字符串
	string.append("单向循环链表 size = ").append(size).append("; [");
	Node<E> node = first;
	for (int i = 0; i < size; i++) {
		string.append(node.element);
		//若尾节点指向null，则只打印本节点；否则输出下一节点
		if (node.next != null) {
			string.append("->").append(node.next.element);
		}
		
		if (i != size - 1) {
			string.append(", ");
		}
		
		node = node.next;
	}
	string.append("]");
	
	return string.toString();
}

3.2、接口测试

单向循环链表同样要注意边界测试，如：当index为0、size - 1、size时的情况。

在Main类（Main.java文件）中新建一个SingleCircleLinkedList对象，用来测试自己封装的单向循环链表。这里仅以添加和删除元素接口为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

package com.atangbiji;

public class Main {
	public static void main(String[] args) {
		SingleCircleLinkedList<Integer> linkedList = new SingleCircleLinkedList <Integer>();
		
		linkedList.add(11);
		linkedList.add(22);
		linkedList.add(33);
		linkedList.add(44);
		linkedList.add(linkedList.size() - 1,null);
		linkedList.add(55);
		linkedList.add(linkedList.size(),66);
		linkedList.add(0,0);
		linkedList.add(0,null);
		
		System.out.println(linkedList);
		
		linkedList.remove(linkedList.size() - 1);
		System.out.println(linkedList);
		
		linkedList.remove(5);
		System.out.println(linkedList);
		
		int linkedListSize = linkedList.size();
		
		for (int i = 0; i < linkedListSize; i++) {
			linkedList.remove(0);
			System.out.println(linkedList);
		}

	}
}

运行该程序，输出结果为：

（本讲完，系列博文持续更新中…… ）

参考文献：
[1] 《恋上数据结构与算法》，小码哥MJ
[2] 《数据结构与算法》，邓俊辉

附：如何获取源代码？

关注 “阿汤笔迹” 微信公众号，在后台回复关键词 “数据结构与算法设计与实现” ，即可获取项目源代码。

原文地址：http://www.atangbiji.com/2023/07/22/SingleCircleLinkedList/
博主最新文章在个人博客 http://www.atangbiji.com/ 发布。