双向链表DoubleLinkedList

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

双向链表的结点比单链表的结点多一个前驱指针，所以已知某一个结点后，可以很快速的访问其前驱结点和后继结点。

创建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

创建DoubleLinkedList类：

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

在头部插入新结点：

1
2
3
4
5
6
7
8
9
10
def insert_new_value_to_head(self, value):
	new_node = Node(value)
	current = self._head
	if current == None:
		self._head = new_node
	else:
		new_node._next = self._head
		self._head._prev = new_node
		self._head = new_node
		new_node._prev = None

在给定结点后插入新结点：

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

在给定结点前插入新结点：

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

删除给定结点

1
2
3
def delete_target_node(self, target_node):
	target_node._next._prev = target_node._prev
	target_node._prev._next = target_node._next

返回给定值的结点

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

	if current:
		return current
	else:
		return