线性表——双向循环链表

1、双向循环链表（DoubleCircleLinkedList）

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

注：

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

2、双向循环链表的设计

（1）类的结构设计

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

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

• 链表存放元素的数量。

  private int size;

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

• 第一个节点的引用。

  private Node<E> first;

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

• 最后一个节点的引用。

  private Node<E> last;

  last指向链表的最后一个（尾）节点。

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

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

  • 上一个节点的引用

    Node<E> prev;

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

  • 该节点内部的泛型元素

    E element;

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

  • 下一个节点的引用

    Node<E> next;

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

  • 构造函数

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

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

（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、编程实现

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

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

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

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

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

DoubleCircleLinkedList.java文件：

package com.atangbiji;

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

（2）实现size()接口

DoubleCircleLinkedList.java文件：

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

（3）实现isEmpty()接口

DoubleCircleLinkedList.java文件：

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

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

• 取索引为index的节点对象

为了方便获取任意节点，我们定义一个私有方法Node用来获取索引为index的节点。当index<size/2时，从前向后找；当index>=size/2时，从后向前找。

DoubleCircleLinkedList.java文件：

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

获取链表索引为index的元素，只需：

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

②再从该节点对象中获取其中的元素即可。

DoubleCircleLinkedList.java文件：

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

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

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

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

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

DoubleCircleLinkedList.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)接口类似，这里不再赘述。

DoubleCircleLinkedList.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，则说明该元素存在。

DoubleCircleLinkedList.java文件：

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

（8）实现clear()接口

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

DoubleCircleLinkedList.java文件：

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

注：将第一个节点和最后一个结点的引用设为空（null）后，虽然各节点还在被循环引用。但JVM的内存处理机制是：没有被“GC Root对象”引用的对象就会被当做垃圾清除。

GC Root对象主要包括：被栈指针（局部变量）指向的对象等多种对象。当我们在调用接口时，我们所使用的DoubleCircleLinkedList对象就是一种GC Root对象。所以，Java中，将第一个节点和最后一个结点的引用设为空（null），即可实现所有节点的内存释放。

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

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

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

①找到被删除节点；

②获取被删除节点的前一节点和后一节点；

③让前一节点的next直接指向后一节点，让后一节点的prev直接指向前一节点；

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

此时，被删除节点便没有被任何“GC Root对象”引用，进而被当做垃圾清除。

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

• 删除一般节点：

  

• 删除头节点或尾节点：

  

• 当size=1时：

  

  **注：**当删除双向循环链表中唯一存在的元素时，直接让first和last都指向空（null）即可。

DoubleCircleLinkedList.java文件：

/*
	  *  删除index位置对应的元素
	 * @param: index
	 * @return: 被删除的元素
	 * */
	public E remove(int index) {
		
		//1、找到被删除节点
		Node<E> removeNode = node(index);
		//2、获取被删除节点的前一节点和后一节点
		Node<E> prevNode = removeNode.prev;
		Node<E> nextNode = removeNode.next;
		//3、让前一节点的next直接指向后一节点，让后一节点的prev直接指向前一节点
		
		
		if (1 == size) {
			//当删除双向循环链表中唯一存在的元素时
			first = null;
			last = null;
			
		} else if (0 == index) {
			
			//若删除的是头节点
			nextNode.prev = last;
			last.next = nextNode;
			first = nextNode;
			
		}else if ((size - 1) == index) {
			
			//若删除的是尾节点
			prevNode.next = first;
			first.prev = prevNode;
			last = prevNode;
			
		}else {
			
			//若删除的为中间节点
			prevNode.next = nextNode;
			nextNode.prev = prevNode;
			
		}
		
		//4、链表存放元素的数量-1
		size--;
		
		return removeNode.element;
	}

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

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

①创建一个新节点；

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

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

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

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

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

• 添加一般节点：

  

• 添加头节点（index=0）：

  

• 添加尾节点（index=size）：

  

• 当size=0时：

  

DoubleCircleLinkedList.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 (size == 0) {
		//1、创建一个新节点
		Node<E> newNode = new Node<E>(null,element,null);
		
		//2、首节点和尾节点均指向新节点
		first = newNode;
		last = newNode;
		
		//3、再将新结点分别与前一节点和后一节点相连
		newNode.next = newNode;
		newNode.prev = newNode;
		
	} else if (size == index) {
		//1、创建一个新节点
		Node<E> newNode = new Node<E>(null,element,null);
			
		//2、分别获取新节点的前一节点和后一节点
		Node<E> nextNode = first;//获取新节点的后一结点（即：index节点）
		Node<E> prevNode = last;//获取新节点的前一结点（即：index结点的前一结点）
			
		//3、再将新结点分别与前一节点和后一节点相连
		newNode.next = nextNode;
		prevNode.next = newNode;
			
		newNode.prev = prevNode;
		nextNode.prev = newNode;
		last = newNode;
		
	} else if (0 == index) {
		//1、创建一个新节点
		Node<E> newNode = new Node<E>(null,element,null);
			
		//2、分别获取新节点的前一节点和后一节点
		Node<E> nextNode = first;//获取新节点的后一结点（即：index节点）
		Node<E> prevNode = last;//获取新节点的前一结点（即：index结点的前一结点）
			
		//3、再将新结点分别与前一节点和后一节点相连
		newNode.next = nextNode;
		prevNode.next = newNode;
		first = newNode;
			
		newNode.prev = prevNode;
		nextNode.prev = newNode;
		
	} else {
		//1、创建一个新节点
		Node<E> newNode = new Node<E>(null,element,null);
			
		//2、分别获取新节点的前一节点和后一节点
		Node<E> nextNode = node(index);//获取新节点的后一结点（即：index节点）
		Node<E> prevNode = nextNode.prev;//获取新节点的前一结点（即：index结点的前一结点）
			
		//3、再将新结点分别与前一节点和后一节点相连
		newNode.next = nextNode;
		prevNode.next = newNode;
			
		newNode.prev = prevNode;
		nextNode.prev = newNode;
	}
	//4、链表存放元素的数量+1
	size++;
}

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

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

DoubleCircleLinkedList.java文件：

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

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

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

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

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

DoubleCircleLinkedList.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++) {
		//若首节点指向null，则只打印本节点；否则输出上一节点
		if (node.prev != null) {
			string.append(node.prev.element).append("<-");
		}
		
		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文件）中新建一个DoubleCircleLinkedList对象，用来测试自己封装的单向循环链表。这里仅以添加和删除元素接口为例进行测试，其它接口的测试方法与此类似，这里不再赘述。

Main.java文件：

package com.atangbiji;

public class Main {
	public static void main(String[] args) {
		DoubleCircleLinkedList<Integer> linkedList = new DoubleCircleLinkedList <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/23/DoubleCircleLinkedList/
博主最新文章在个人博客 http://www.atangbiji.com/ 发布。