双向链表
双向链表的实现
一、往链表的头部增加一个节点
# 新建一个节点
node = Node(data)
# 判断链表是否为空
if self.is_empty():
self.head = node
else:
# 让链表中原本的头节点的prev指向新的节点
self.head.prev = node
# 先让node指向当前链表中的头节点
node.next = self.head
# 再让链表的head指向当前node节点
self.head = node
# 添加节点之后，链表的长度加1
self._length += 1
二、链表尾部添加一个节点
node = Node(data)
if self.head:
cur = self.head # 将头节点的地址赋给了变量cur
while cur.next:
cur = cur.next
node.prev = cur # 让node的prev指针域去指向原本的尾节点
cur.next = node # 让原本的尾节点的next指向新建的节点
else:
self.head = node
# 让当前的尾节点的指针指向新建的节点node
# 链表的长度加1
self._length += 1
三、往链表指定位置插入一个节点，值为data
1新建一个节点
node = Node(data)
# 2找到链表中索引为pos-1的节点
cur = self.head
while pos - 1:
cur = cur.next
pos -= 1
# 到这里之后，cur指向的是索引为pos-1的节点
# 让node的prev指向索引为pos-1的节点
node.prev = cur
# 让node的next指向索引为pos的节点
cur.next.prev = node
# 让索引为pos的节点指向新建的节点
node.next = cur.next
# 4让索引为pos-1的节点的next指向node
cur.next = node
# 5链表的长度加1
self._length += 1
四、删除链表中第一个值为data的节点
cur = self.head
while cur:
if cur.data == data:
if cur == self.head:
self.head = cur.next
else:
cur.prev.next = cur.next
if cur.next:
cur.next.prev=cur.prev
self._length -= 1
return 0
cur = cur.next
return -1
五、修改链表中指定位置节点的值
if 0 < pos < self._length:
cur = self.head
while pos:
cur = cur.next
pos -= 1
cur.data = data
else:
print('输入的范围不符合要求')
六、查找链表中是否有节点的值为data
cur=self.head
while cur:
if cur.data==data:
return 1
else:
cur=cur.next
return -1
代码块：
class Node:
def __init__(self, data, _prev=None, _next=None):
self.prev = _prev # 指针域，指向当前节点的前一个节点
self.data = data # 数据域
self.next = _next # 指针域 指向当前节点的后一个节点
class DoubleLinkList:
def __init__(self):
self.head = None # 链表的的头节点
self._length = 0 # 链表的长度，链表的元素个数
def is_empty(self):
# 判断链表的是否为空
return self._length == 0
def length(self):
# 返回链表的长度
return self._length
def nodes_list(self):
# 返回链表中的所有节点的值组成的列表
res = []
cur = self.head
while cur:
res.append(cur.data)
cur = cur.next
return res
def add(self, data):
# 往链表的头部添加一个节点，值为data
# 新建一个节点
node = Node(data)
# 判断链表是否为空
if self.is_empty():
self.head = node
else:
# 让链表中原本的头节点的prev指向新的节点
self.head.prev = node
# 先让node指向当前链表中的头节点
node.next = self.head
# 再让链表的head指向当前node节点
self.head = node
# 添加节点之后，链表的长度加1
self._length += 1
def append(self, data):
# 往链表的尾部添加一个节点，值为data
# 新建一个节点node，值为data
node = Node(data)
if self.head:
cur = self.head # 将头节点的地址赋给了变量cur
while cur.next:
cur = cur.next
node.prev = cur # 让node的prev指针域去指向原本的尾节点
cur.next = node # 让原本的尾节点的next指向新建的节点
else:
self.head = node
# 让当前的尾节点的指针指向新建的节点node
# 链表的长度加1
self._length += 1
def insert(self, pos, data):
# 往链表的指定位置插入一个节点，值为data
if pos <= 0:
self.add(data)
elif pos > self._length:
self.append(data)
else:
# 1新建一个节点
node = Node(data)
# 2找到链表中索引为pos-1的节点
cur = self.head
while pos - 1:
cur = cur.next
pos -= 1
# 到这里之后，cur指向的是索引为pos-1的节点
# 让node的prev指向索引为pos-1的节点
node.prev = cur
# 让node的next指向索引为pos的节点
cur.next.prev = node
# 让索引为pos的节点指向新建的节点
node.next = cur.next
# 4让索引为pos-1的节点的next指向node
cur.next = node
# 5链表的长度加1
self._length += 1
def remove(self, data):
# 删除链表中第一个值为data的节点
cur = self.head
while cur:
if cur.data == data:
if cur == self.head:
self.head = cur.next
else:
cur.prev.next = cur.next
if cur.next:
cur.next.prev=cur.prev
self._length -= 1
return 0
cur = cur.next
return -1
def modify(self, pos, data):
# 修改链表中指定位置节点的值
if 0 < pos < self._length:
cur = self.head
while pos:
cur = cur.next
pos -= 1
cur.data = data
else:
print('输入的范围不符合要求')
def search(self, data):
# 查找链表中是否有节点的值为data
cur = self.head
while cur:
if cur.data == data:
return True
cur = cur.next
return False
if __name__ == '__main__':
l1 = DoubleLinkList() # 新建一个链表类
print(l1.head, l1.length())
l1.add(1)
print(l1.nodes_list())
l1.append(2)
print(l1.nodes_list())
l1.append(3)
print(l1.nodes_list())
l1.insert(1, 8)
print(l1.nodes_list())
l1.remove(2)
print(l1.nodes_list())
l1.remove(1)
print(l1.nodes_list())
l1.modify(1,7)
print(l1.nodes_list())
print(l1.search(7))
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由半码博客整理，本文链接：https://www.bmabk.com/index.php/post/123551.html
