单向循环链表
单向循环链表只需要将普通的单链表首尾相连即可实现。
基本操作：
- 判断列表是否为空：同单链表；
- 头部/尾部插入元素：由于循环链表的优势，这一步操作将十分简单，只需要在尾部结点后直接插入即可，要注意的是如果采用尾插法，需要改变尾部节点
- 弹出尾部元素：遍历即可
- 指定位置添加元素：需要提前识别插入的位置是否为头部和尾部
- 删除指定元素：需要判别删除的元素是否和尾部元素相同，如果相同则操作和'弹出尾部元素'操作类似，若不同则寻找元素，若元素不在链表中，需要提前识别异常。
Python实现：
class ListNode():def __init__(self, val, next=None):self.val = valself.next = nextclass OneWayCircularLinkedList():def __init__(self):self.rear = None# 判断链表是否为空def is_empty(self):return self.rear is None# 在链表头部插入元素def prepend(self, val):p = ListNode(val)if self.is_empty():p.next = pself.rear = pelse:p.next = self.rear.nextself.rear.next = p# 在链表尾部插入元素def append(self, val):p = ListNode(val)if self.is_empty():p = p.nextself.rear = pelse:p.next = self.rear.nextself.rear.next = pself.rear = self.rear.next# 计算链表长度def get_length(self):if self.is_empty():return 0cur = self.rearlength = 1while cur.next != self.rear:length += 1cur = cur.nextreturn length# 弹出尾部元素def pop_last(self):if self.is_empty():raise ValueError('self.rear 必须非空')# 链表只有一个元素时预先判断if self.rear.next == self.rear: output = self.rear.valself.rear = Nonereturn outputcur = self.rearwhile cur.next != self.rear:cur = cur.nextoutput = cur.next.valcur.next = cur.next.next # 删除尾部节点self.rear = curreturn output# 在指定位置添加元素def insert(self, position, element):p = ListNode(element)l = self.get_length()if position >= l or position < 0:raise ValueError('超出了链表长度范围！')# 判空if self.is_empty():if position > 0:raise ValueError('链表为空，且没有在位置0添加元素！')else:p.next = pself.rear = preturn# 分三种情况添加元素if position == 0:self.prepend(element)elif position == l - 1:self.append(element)else:cur = self.rearwhile position > 0:cur = cur.nextposition -= 1p.next = cur.nextcur.next = p# 删除指定元素def remove(self, element):if self.is_empty():raise ValueError('self.rear 必须非空')cur = self.rearflag = False # 标记是否链表含有指定元素if self.rear.val == element:flag = Trueif self.rear.next == self.rear: output = self.rear.valself.rear = Nonereturn outputelse:cur = self.rearwhile cur.next != self.rear:cur = cur.nextcur.next = cur.next.next # 删除尾部节点self.rear = curelse:while cur.next.val != element and cur.next != self.rear:cur = cur.nextif cur.next.val == element:flag = Trueif not flag:raise ValueError('链表中不存在该元素！')cur.next = cur.next.nextif __name__ == '__main__':def testfunction(node):nums = []cur = node.nextwhile cur != node:nums.append(cur.val)cur = cur.nextnums.append(cur.val)return numssample = OneWayCircularLinkedList()for i in range(8):sample.prepend(i)print(testfunction(sample.rear))sample.append(2)print(testfunction(sample.rear))print(sample.get_length())print(sample.pop_last())sample.insert(1, 10)print(testfunction(sample.rear))总结
不难发现，单向循环链表的优势在于头尾相连，此时尾端插入的效率较高。