使用python实现双向链表，供大家参考，具体内容如下
双向链表： 指的是讲数据链接在一起，每个数据是一个节点，每一个节点都有一个数据区，两个链接区，分别链接上一个节点和下一个节点
数据区： 存放数据的地方
prev： 链接上一个节点
next： 链接下一个节点双向链表操作
1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在代码实现
# Functions ?函数声明 class Node(): ? ? """实例化节点类""" ? ? def __init__(self, item): ? ? ? ? self.item = item ? ? ? ? self.prev = None ? ? ? ? self.next = None class Linklist(): ? ? """ ? ? 存储所有节点类 ? ? """ ? ? def __init__(self): ? ? ? ? """ ? ? ? ? 初始化一个头结点 ? ? ? ? 默认为空 ? ? ? ? """ ? ? ? ? self.head = None ? ? # 1. 链表是否为空 ? ? def is_empty(self): ? ? ? ? return self.head == None ? ? # 2. 链表的长度 ? ? def length(self): ? ? ? ? """ ? ? ? ? 返回节点的长度 ? ? ? ? 实例化一个游标 ? ? ? ? 使用这个游标遍历所有的数据 ? ? ? ? 使用一个计数器，遍历一个数据，自增一，最后输出计数器 ? ? ? ? """ ? ? ? ? # 实例化游标 ? ? ? ? cur = self.head ? ? ? ? # 技术器 ? ? ? ? # 如果链表为空，不会进入循环，直接输出 0 ? ? ? ? count = 0 ? ? ? ? # 遍历所有的数据 ? ? ? ? while cur != None: ? ? ? ? ? ? count +=1 ? ? ? ? ? ? cur = cur.next ? ? ? ? return count ? ? # 3. 遍历链表 ? ? def treval(self): ? ? ? ? """ ? ? ? ? 遍历链表，获取所有的数据 ? ? ? ? 使用游标，遍历整个链表，每次输出cur.item 的值 ? ? ? ? 注意链表为空的情况， ? ? ? ? """ ? ? ? ? # 实例化一个游标 ? ? ? ? cur = self.head ? ? ? ? # 遍历链表 ? ? ? ? while cur != None: ? ? ? ? ? ? print(cur.item, end=' ') ? ? ? ? ? ? cur = cur.next ? ? ? ? print() ? ? # 4. 链表头部添加元素 ? ? def add(self, item): ? ? ? ? """ ? ? ? ? 头部添加数据 ? ? ? ? 分析： ? ? ? ? 1、头部添加数据，链表为空时： self.head 指向node ? ? ? ? 2、链表不为空时： 先将node.next = self.head.next, 再讲 self.head = node ? ? ? ? """ ? ? ? ? # 实例化节点 ? ? ? ? node = Node(item) ? ? ? ? # 添加数据 ? ? ? ? # 判断链表是否为空 ? ? ? ? if self.is_empty(): ? ? ? ? ? ? # 为空，直接将self.head 指向node ? ? ? ? ? ? self.head=node ? ? ? ? else: ? ? ? ? ? ? # 不为空，先将noede ? ? ? ? ? ? node.next = self.head ? ? ? ? ? ? self.head.prev=node ? ? ? ? ? ? self.head=node ? ? # 5. 链表尾部添加元素 ? ? def append(self,item): ? ? ? ? """ ? ? ? ? 尾部添加数据 ? ? ? ? 分析： ? ? ? ? 要先将指针指向尾部的节点 ? ? ? ? 最后的节点的 cur.next = node, node.prev = cur ? ? ? ? """ ? ? ? ? # 实例化节点 ? ? ? ? node = Node(item) ? ? ? ? # 实例化游标 ? ? ? ? cur = self.head ? ? ? ? # 移动游标到最后一个节点 ? ? ? ? # 如果链表为空 ? ? ? ? # 直接使用头插法 ? ? ? ? if self.is_empty(): ? ? ? ? ? ? self.add(item) ? ? ? ? else: ? ? ? ? ? ? while cur.next != None: ? ? ? ? ? ? ? ? # cur.next 不为空，则进入循环， 上次循环，是进入上上个节点，但 将cur ?= cur.next，就指向了最后一个节点 ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? node.prev = cur ? ? ? ? ? ? cur.next = node ? ? # 6. 链表指定位置添加元素 ? ? def insert(self, index, item): ? ? ? ? """ ? ? ? ? 指定位置添加数据 ? ? ? ? 分析 ? ? ? ? 单链表中需要实例化两个有游标 ? ? ? ? 双向链表，直接向指针指向索引的位置 ? ? ? ? 将这个位置节点的 cur. ? ? ? ? """ ? ? ? ? # 实例化节点 ? ? ? ? node = Node(item) ? ? ? ? # 实例化游标 ? ? ? ? cur = self.head ? ? ? ? # 起始位置 ? ? ? ? count = 0 ? ? ? ? if index<=0: ? ? ? ? ? ? # 使用头插法 ? ? ? ? ? ? self.add(item) ? ? ? ? elif index > (self.length()-1): ? ? ? ? ? ? self.append(item) ? ? ? ? else: ? ? ? ? ? ? # 移动游标 ? ? ? ? ? ? while count < index: ? ? ? ? ? ? ? ? # 增加一 ? ? ? ? ? ? ? ? count += 1 ? ? ? ? ? ? ? ? # 移动游标到索引位置 ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? ? ? node.next = cur ? ? ? ? ? ? node.prev = cur.prev ? ? ? ? ? ? cur.prev.next = node ? ? ? ? ? ? cur.prev = node ? ? # 7. 链表删除节点 ? ? def remove(self,item): ? ? ? ? """ ? ? ? ? 删除指定的节点 ? ? ? ? 首先实例化节点，遍历链表，找到该节点，删除该节点 ? ? ? ? """ ? ? ? ? # 实例化游标 ? ? ? ? cur = self.head ? ? ? ? # 遍历链表，找到该节点 ? ? ? ? while cur != None: ? ? ? ? ? ? if cur.item == item: ? ? ? ? ? ? ? ? if self.head == cur: ? ? ? ? ? ? ? ? ? ? self.head = cur.next ? ? ? ? ? ? ? ? ? ? if cur.next: ? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = None ? ? ? ? ? ? ? ? else: ? ? ? ? ? ? ? ? ? ? cur.prev.next = cur.next ? ? ? ? ? ? ? ? ? ? # 如果有下个节点，防止最后一个节点 ? ? ? ? ? ? ? ? ? ? if cur.next: ? ? ? ? ? ? ? ? ? ? ? ? cur.next.prev = cur.prev ? ? ? ? ? ? ? ? ? ? pass ? ? ? ? ? ? ? ? break ? ? ? ? ? ? else: ? ? ? ? ? ? ? ? cur = cur.next ? ? # # 8. 查找节点是否存在 ? ? def search(self, item): ? ? ? ? """ ? ? ? ? 查看节点是否存在 ? ? ? ? 分析 ? ? ? ? 遍历链表，查看每一个节点的数据区 ? ? ? ? 空链表 ? ? ? ? 只有头节点 ? ? ? ? 只有尾节点 ? ? ? ? """ ? ? ? ? # 实例化一个游标 ? ? ? ? cur = self.head ? ? ? ? # 遍历链表 ? ? ? ? while cur != None: ? ? ? ? ? ? if cur.item == item: ? ? ? ? ? ? ? ? return True ? ? ? ? ? ? else: ? ? ? ? ? ? ? ? cur = cur.next ? ? ? ? return False测试运行
# 程序的入口 if __name__ == "__main__": ? ? s = Linklist() ? ? print(s.is_empty()) ?# ?True ? ? s.append(100)? ? ? s.append(200) ? ? s.append(300) ? ? s.add(6) ? ? s.insert(1, 10) ? ? s.search(6) ? ? s.treval() ? # 6 10 100 200 300? ? ? s.remove(100) ? ? s.treval() ? # 6 10 200 300? ? ? pass以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did17021