之前，分析并采用python和C++实现了单链表：

机器学习入坑者：干货！单链表从原理到实现——附python和C++两个版本zhuanlan.zhihu.com

1、基本概念：

在单链表的基础上，人们设计了一种“循环性”单向链表，称之为“单向循环链表”。相比于单向链表，单向循环链表的最大特点是“尾结点指向头节点”。

2、单向链表VS单向循环链表——优势

对单向链表中任一个节点的访问都需要从头结点开始；而对单向循环链表从任意节点出发都能遍历整个列表，极大的增强了其灵活性。

3、单向链表VS单向循环链表——修改

（1）判断是否为空：

单向链表：如果头结点指向空，那么为空链表

单向循环链表：如果头结点指向自身，那么为空链表

（2）判断是否为尾结点

单向链表：指向空的节点为尾结点

单向循环链表：指向头结点的节点为尾结点

4、代码实现：

根据前面所述，单向循环链表和单向链表的在增、删、改、查各个函数的实现上差别很小，所以下面仅仅实现代表性的函数，其余函数请参考：

机器学习入坑者：干货！单链表从原理到实现——附python和C++两个版本zhuanlan.zhihu.com

python实现：

（1）节点类

单向循环链表的节点类的和单向链表一致，都仅包含数据域data和指针域pointer作为实例属性：

class Node:
    def __init__(self, data):
        """节点类"""
        self.data = data
        self.pointer = None

（2）链表类

初始化函数的目的是构建一个空链表，令头指针指向自身：

class SCLL:
    def __init__(self):
        """ 初始化函数"""
        self.head = Node(None)
        self.head.pointer = self.head

（3）判断是否为空：is_empty()函数

根据前面分析可知，需要判断头结点是否指向自身，从而确定是否为空：

def is_empty(self):
    """ 判断链表是否为空"""
    if self.head.pointer == self.head:
        return True

（4）头插法

在单向循环列表的表头进行元素插入时，需要判断是否为空链表；对于非空链表，先令新节点指向头结点的直接后继，然后令头结点指向新节点：

def add(self, data):
    """ 头插法"""
    node = Node(data)
    # 链表为空直接插入首位置
    if self.is_empty():
        self.head.pointer = node
        node.pointer = self.head
        return True
    # 链表不为空时
    else:
        node.pointer = self.head.pointer
        self.head.pointer = node
        return True

（5）遍历链表

针对空链表可返回None；针对非空链表即采用循环操作，结束条件当前位置是尾结点：

def traversal(self):
    """ 遍历链表"""
    if self.is_empty():
        return False
    else:
        counter = 1
        current =self.head.pointer
        # 当前指针不指向头结点时进行循环
        while(current != self.head):
            print(" Element {} is {} ".format(counter, current.data))
            counter += 1
            current = current.pointer
        return True

C++实现：

（1）节点类

单向循环列表的节点类在C++实现中依旧可与单向链表相同：

class Node{
public:
	int data;
	Node *pointer=NULL;
};

（2）链表类

依旧是遵循声明和实现分离的原则，首先定义构造函数和常用的几个链表操作函数：

class SingleLinkedList {
public:
	SingleLinkedList();
	bool isEmpty();
	void add(int data);
	void traversal();

private:
     Node *head;
};

（3）构造函数

创建头结点，并让头结点指向自身：

SingleLinkedList::SingleLinkedList() {
	head = new Node;
	head->data = ;
	head->pointer = head;
}

（4）判断是否为空：isEmpty()

bool SingleLinkedList::isEmpty() {
	// 头结点不指向任何结点，为空
	if (head->pointer == head) {
		return true;
	}
	else {
		return false;
	}
}

（5）头插法：add()

void SingleLinkedList::add(int data) {
	// 当原列表仅有头结点时，直接插入新节点即可
	if (isEmpty()) {
		head->pointer = new Node;
		head->pointer->pointer = head;
		head->pointer->data = data;
	}
	// 列表非空时
	else {
		// 临时存储头结点的直接后继
		Node *temp = head->pointer;
		head->pointer = new Node;
		head->pointer->data = data;
		head->pointer->pointer = temp;
	}
}

（6）遍历：traversal()

void SingleLinkedList::traversal() {
	// 链表为空，结束函数
	if(isEmpty()) {
		return;
	}
	else {
		Node *current;
		// 指向头结点的直接后继
		current = head->pointer;
		int counter = 1;
		// 遍历链表，输出每个节点的值
		while (current != head)
		{
			printf("Element in %d is %d \n", counter, current->data);
			counter++;
			current = current->pointer;
		}
	}
}

ITPub博客

数据结构——从单链表到单向循环链表