本文主要是介绍Python数据结构之单向链表和双向链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链表的定义：
链表是通过一个个节点（Node）组成的，每个节点都包含了称为数据域(data)和指针域(next)的基本单元，它也是一种递归的数据结构。它能保持数据之间的逻辑顺序，但存储空间不必按照顺序存储。
链表的操作
- is_empty() 链表是否为空
- length() 链表长度即节点个数
- travel() 遍历链表
- add(item) 链表头部添加节点
- append(item) 链表尾部添加节点
- insert(index, item) 指定位置添加节点
- remove(item) 删除节点
- search(item) 查找节点是否存在
python实现代码
#!/usr/bin/env python3
# coding=utf-8class Node(object):"""节点"""def __init__(self, temp_data):super(Node, self).__init__()self.data = temp_dataself.prev = Noneself.next = None class SingleLinkList(object):"""单向链表"""def __init__(self, temp_node=None):super(SingleLinkList, self).__init__()self.head = temp_nodedef is_empty(self):"""链表是否为空"""return not self.head def length(self):"""链表长度(节点个数)"""cur = self.headcount = 0while cur:count += 1cur = cur.nextreturn count def travel(self):"""遍历链表"""cur = self.headwhile cur:print(cur.data, end=" ")cur = cur.nextprint()def add(self, item):"""链表头部添加元素"""node = Node(item)node.next = self.headself.head = node def append(self, item):"""链表尾部添加元素"""node = Node(item)cur = self.headif self.is_empty():self.head = nodeelse:while cur.next:cur = cur.nextcur.next = node def insert(self, index, item):"""指定位置添加元素"""if index <= 0:self.add(item)elif index > self.length()-1:self.append(item)else:node = Node(item)cur = self.headfor i in range(index-1):cur = cur.nextnode.next = cur.nextcur.next = node def remove(self, item):"""删除节点"""cur = self.headpre = None while cur:if cur.data == item:if cur == self.head:self.head = cur.nextbreakelse:pre.next = cur.nextbreak pre = cur cur = cur.next def search(self, item):"""查找节点是否存在"""cur = self.headwhile cur:if cur.data == item:return Truecur = cur.nextreturn False class DoubleLinkList(SingleLinkList):"""双向链表"""def add(self, item):"""从链表头部插入节点"""node = Node(item)if self.is_empty():self.head = nodeelse:node.next = self.headnode.next.prev = node self.head = node def append(self, item):"""从链表尾部插入节点"""node = Node(item)if self.is_empty():self.head = nodeelse:cur = self.headwhile cur.next:cur = cur.nextcur.next = nodenode.prev = cur def insert(self, index, item):"""从指定位置插入节点"""if index <= 0:self.add(item)elif index > self.length()-1:self.append(item)else:node = Node(item)cur = self.headfor i in range(index-1):cur = cur.nextnode.next = cur.nextcur.next.prev = nodenode.prev = curcur.next = nodedef remove(self, item):"""删除节点"""cur = self.headwhile cur:if cur.data == item:if cur == self.head: self.head = cur.nextif cur.next:cur.next.prev = cur.prev else:cur.prev.next = cur.nextif cur.next:cur.next.prev = cur.prev break else:cur = cur.next if __name__ == "__main__":my_list = SingleLinkList()#my_list = DoubleLinkList()for i in range(10):my_list.append(i)print(my_list.length())my_list.travel()my_list.insert(0, -6)my_list.travel()my_list.insert(6, 66)my_list.travel()my_list.insert(81, 666)my_list.travel()print(my_list.search(33))print(my_list.search(66))my_list.remove(66)my_list.travel()my_list.remove(-6)my_list.travel()my_list.remove(666)my_list.travel()
这篇关于Python数据结构之单向链表和双向链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
