单向循环链表CircularLinkedList

发表于 | 分类于 | 阅读次数 ℃
本文字数： 1.2k | 阅读时长 ≈ 1 分钟

单向循环链表与普通单链表类似，唯一的区别是单向循环链表的尾结点指向头结点，而普通单链表的尾结点指向None。

此处我们同样保持和普通单链表一样的“核心单元”：Node类

1
2
3
4
5
6
7
#-*-coding:utf-8-*-

class Node(object):

    def __init__(self, data, next_node=None):
        self.data = data
        self._next = next_node

构建单向循环链表CircularLinkedList类：

1
2
3
4
class CircularLinkedList(object):

	def __init__(self, node=None):
		self._head = None

在头部添加一个新结点

开篇已经提到，单向循环链表与普通单链表的不同之处在于尾结点也要指向头结点。所以在头部添加新结点需要有3步：
1.新结点new_node的_next指针指向原来_head结点
2.将_head指向新结点new_node
3.将尾结点的_next指针指向新结点new_node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def insert_new_value_to_head(self, value):
	new_node = Node(value)
	if self._head == None:
		self._head = new_node
		new_node._next = new_node
	else:
		current = self._head
		while current._next != self._head:
			# 让指针走到最后一个结点
			current = current._next

		new_node._next = self._head
		self._head = new_node
		current._next = new_node

在尾部添加一个新结点

1.新结点new_node(现在的尾结点)指向_head
2.原来尾结点指向的是_head结点，现在指向new_node

1
2
3
4
5
6
7
8
9
10
11
12
def insert_new_value_to_end(self, value):
	new_node = Node(value)
	if self._head == None:
		self._head = new_node
		new_node._next = new_node
	else:
		current = self._head
		while current._next != self._head:
			current = current._next

		new_node._next = self._head
		current._next = new_node