双向链表定义
双向链表(Double Linked List)是一种更复杂的链表,每个节点除了包含元素域,还包含两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;另一个指向下一个节点,当此节点为最后一个节点时,指向空值。
节点示意图
- 表元素域
用来存放具体的数据。elem
- 链接域
用来存放上一个节点的位置(python中的标识)prev
- 链接域
用来存放下一个节点的位置(python中的标识)next
双向链表示意图
双向链表的基本操作
-
判断链表是否为空is_empty()
-
链表长度length
-
遍历整个链表,打印元素travel()
-
在链表头部添加元素add(item)
-
在链表尾部添加元素append(item)
-
在指定位置插入元素insert(pos, item)
-
删除元素remove(item)
-
清空链表clear()
-
判断元素是否存在is_contain(item)
Python 代码实现
# 节点代码实现
class Node(object):
"""双向链表节点"""
def __init__(self, item):
self.item = item
self.next = None
self.prev = None
# 双向链表代码实现
class DoubleLinkList(object):
"""双向链表"""
def __init__(self):
self._head = None
def is_empty(self):
"""判断链表是否为空"""
return self._head is None
@property
def length(self):
"""返回链表的长度"""
cur = self._head
count = 0
while cur is not None :
count += 1
cur = cur.next
return count
def travel(self):
"""遍历链表"""
cur = self._head
while cur is not None:
print(cur.item)
cur = cur.next
print("")
def add(self, item):
"""头部插入元素"""
node = Node(item)
if self.is_empty():
# 如果是空链表,将_head指向node
self._head = node
else:
# 将node的next指向_head的头节点
node.next = self._head
# 将_head的头节点的prev指向node
self._head.prev = node
# 将_head 指向node
self._head = node
def append(self, item):
"""尾部插入元素"""
node = Node(item)
if self.is_empty():
# 如果是空链表,将_head指向node
self._head = node
else:
# 移动到链表尾部
cur = self._head
while cur.next is not None:
cur = cur.next
# 将尾节点cur的next指向node
cur.next = node
# 将node的prev指向cur
node.prev = cur
def is_contain(self, item):
"""查找元素是否存在"""
cur = self._head
while cur is not None:
if cur.item == item:
return True
cur = cur.next
return False
def insert(self, pos, item):
"""在指定位置添加节点"""
if pos <= 0:
self.add(item)
elif pos > (self.length-1):
self.append(item)
else:
node = Node(item)
cur = self._head
count = 0
# 移动到指定位置的前一个位置
while count < (pos-1):
count += 1
cur = cur.next
# 将node的prev指向cur
node.prev = cur
# 将node的next指向cur的下一个节点
node.next = cur.next
# 将cur的下一个节点的prev指向node
cur.next.prev = node
# 将cur的next指向node
cur.next = node
def remove(self, item):
"""删除元素"""
if self.is_empty():
return
else:
cur = self._head
if cur.item == item:
# 如果首节点的元素即是要删除的元素
if cur.next is None:
# 如果链表只有这一个节点
self._head = None
else:
# 将第二个节点的prev设置为None
cur.next.prev = None
# 将_head指向第二个节点
self._head = cur.next
return
while cur is not None:
if cur.item == item:
# 将cur的前一个节点的next指向cur的后一个节点
cur.prev.next = cur.next
# 将cur的后一个节点的prev指向cur的前一个节点
cur.next.prev = cur.prev
break
cur = cur.next
def clear(self):
"""清空链表"""
self._head = None
def __len__(self):
"""可以用len()方法获取链表长度"""
return self.length
def __iter__(self):
"""可以使用循环遍历链表"""
cur = self._head
while cur is not None:
value = cur.item
cur = cur.next
yield value
def __contains__(self, item):
"""可以用in判断元素是否在链表中"""
cur = self._head
while cur is not None:
if cur.item == item:
return True
cur = cur.next
return False
# 测试数据
if __name__ == "__main__":
print("------创建链表------")
dl_list = DoubleLinkList()
dl_list.add(1)
dl_list.add(2)
dl_list.append(3)
dl_list.insert(2, 4)
dl_list.insert(4, 5)
dl_list.insert(0, 6)
print("length:",len(dl_list))
dl_list.travel()
print(dl_list.is_contain(3))
print(dl_list.is_contain(8))
print(3 in dl_list)
print(8 in dl_list)
dl_list.remove(1)
print("length:",len(dl_list))
dl_list.travel()
print("------循环遍历------")
for i in dl_list:
print(i)
# 输出结果
------创建链表------
length: 6
6
2
1
4
3
5
True
False
True
False
length: 5
6
2
4
3
5
------循环遍历------
6
2
4
3
5
算法分析
操作 | 复杂度 |
---|---|
访问元素 | O ( n ) O(n) O(n) |
在头部插入/删除 | O ( 1 ) O(1) O(1) |
在尾部插入/删除 | O ( n ) O(n) O(n) |
在中间插入/删除 | O ( n ) O(n) O(n) |
联系我们
个人博客网站:http://www.bling2.cn/
Github地址:https://github.com/lb971216008/Use-Python-to-Achieve
知乎专栏:https://zhuanlan.zhihu.com/Use-Python-to-Achieve
小专栏:https://xiaozhuanlan.com/Use-Python-to-Achieve
博客园:https://www.cnblogs.com/Use-Python-to-Achieve