双向循环链表DoubleCircularLinkedList

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

双向循环链表和双向链表类似，不同的地方在于双向循环链表尾结点的后继指针指向头结点，而头结点的前驱指针指向尾结点。

结点Node类：

1
2
3
4
5
class Node(object):
	def __init__(self, data, _prev=None, _next=None):
		self.data = data
		self._prev = _prev
		self._next = _next

双向循环链表类：

1
2
3
class DoubleCircularLinkedList(object):
	def __init__(self, node=None):
		self._head = node

在头部插入新结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def insert_new_value_to_head(self, value):
	new_node = Node(value)
	current = self._head

	if current == None:
		new_node._next = new_node
		new_node._prev = new_node
		self._head = new_node
	else:
		# self._head._prev # 指向尾结点
		# 先记录尾结点
		tail = self._head._prev
		# 新结点后继指向头结点的位置
		new_node._next = self._head
		# 头结点前驱指向新结点
		self._head._prev = new_node
		# 新结点的前驱指向尾结点
		new_node._prev = tail
		# 尾结点的后继指向新结点
		tail._next = new_node
		# 更新头结点
		self._head = new_node

给定结点后插入新结点：

1
2
3
4
5
6
def insert_new_value_after_target_node(self, value, node):
	new_node = Node(value)
	new_node._next = node._next
	node._next._prev = new_node
	new_node._prev = node
	node._next = new_node

给定结点前插入新结点：

1
2
3
4
5
6
7
8
9
10
11
12
def insert_new_value_before_target_node(self, value, node):
	
	# 判断基准结点是否为头结点
	if self._head == node:
		self.insert_new_value_to_head(value)
	else:
		new_node = Node(value)

		node._prev._next = new_node
		new_node._prev = node._prev
		new_node._next = node
		node._prev = new_node

判断链表是否为空：

1
2
3
4
5
def is_empty(self):
	if self._head == None:
		return True
	else:
		return False

删除给定结点：

1
2
3
4
5
6
7
8
9
def delete_target_node(self, node):
	if self._head == node:
		tail = self._head._prev
		node._next._prev = tail
		tail._next = node._next
		self._head = self._head._next
	else:
		node._prev._next = node._next
		node._next._prev = node._prev

根据值查找给定结点：

1
2
3
4
5
6
7
8
9
def find_by_value(self, value):
	current = self._head
	while current.data != value and current._next != self._head:
		current = current._next

	if current:
		return current
	else:
		return

获取链表长度：

1
2
3
4
5
6
7
8
9
10
11
12
13
def get_linked_list_length(self):

	current = self._head
	length = 0
	if current:
		length += 1
		current = current._next

	while current != self._head:
		length += 1
		current = current._next

	return length