|
定义: 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。  代码: ''' 双链表 优点: 可以找到前驱和后继，可进可退； 缺点: 增加删除节点复杂，需要多分配一个指针存储空间。 适用于需要双向查找节点值的情况'''#创建一个结点类class Node: def __init__(self, value=None): self.value = value self.prev = None self.next = None''' 创建一个双链表'''class doubleLink: def __init__(self): self.header = None # 初始化头结点 self.length = 0 # 链表的长度 # 判断链表是否为空 def is_empty(self): return self.length == 0 ''' 实现向双链表添加元素的功能 有三种实现方式: 1.头插法 2.尾插法 3.向双链表的指定位置添加元素 ''' # 1.头插法 def __add__(self, value): node = Node(value) if self.is_empty(): node.prev = self.header self.header = node self.length += 1 return else: node.next = self.header self.header.prev = node self.header = node self.length += 1 # 2.尾插法 def append(self, value): node = Node(value) if self.is_empty(): self.__add__(value) else: cur = self.header while cur.next is not None: cur = cur.next cur.next = node node.prev = cur self.length += 1 # 3.向双链表的指定位置添加元素 def insert(self, index, value): node = Node(value) cur = self.header if index <= 0 or index > self.length: print('您输入的信息有误') return ' ' if index == 1: self.__add__(value) for i in range(2, index): cur = cur.next node.next = cur.next cur.next.prev = node cur.next = node node.prev = cur self.length += 1 return value ''' 实现插寻双链表元素的功能 有三种实现方式: 1.根据索引查询元素 2.直接查询元素 3.遍历整个双链表，并打印出所有的元素 ''' # 1.根据索引查询元素 def __getitem__(self, index): cur = self.header for i in range(index - 1): cur = cur.next return cur.value # 2.直接查询元素，并返回该元素的索引 def getIndex(self, value): cur = self.header temp = 0 while cur.next is not self.header: if cur.value == value: return temp + 1 cur = cur.next temp += 1 # 3.遍历整个双链表，并打印出所有的元素 def getAll(self): if self.is_empty(): print('目前双链表中没有元素！') return cur = self.header for i in range(self.length): print('%d' % cur.value, end=' ') cur = cur.next # 4.查询某个元素的后继节点 def getItem(self, value): cur = self.header temp = 0 while cur.next is not self.header: if cur.value == value: if cur.next is not None: return cur.next.value else: return -1 cur = cur.next temp += 1 # 5.查询某个元素的前驱节点 def getPrevItem(self, value): cur = self.header temp = 0 while cur.next is not self.header: if cur.value == value: if cur.prev is not None: return cur.prev.value else: return -1 cur = cur.next temp += 1 ''' 实现修改指定位置元素的功能 ''' def __setitem__(self, index, value): cur = self.header for i in range(index - 1): cur = cur.next cur.value = value return value ''' 实现删除双链表元素的功能 ''' # 直接删除元素 def __delete__(self, value): cur = self.header if self.getIndex(value) == 1: self.header = cur.next self.length -= 1 elif self.getIndex(value) != 1: while self.getIndex(value) != self.length: cur = cur.next cur=None self.length -= 1 else: while cur.value != value: cur = cur.next cur.prev.next = cur.next cur.next.prev = cur.prev self.length -= 1if __name__ == '__main__': s = doubleLink() s.__add__(12) s.__add__(13) s.__add__(14) s.__add__(15) s.append(22) s.getAll() print('\n第%d个位置的元素是%d.' % (1, s.__getitem__(1))) print('\n元素%d在双链表的第%d个位置' % (14, s.getIndex(14))) print('获取元素%d的后继节点%d' % (12, s.getItem(12))) print('获取元素%d的前驱节点%d' % (13, s.getPrevItem(13))) print('在第%d个位置插入元素%d:' % (2, s.insert(2, 45))) s.getAll() print('\n将第%d个位置的元素修改为%d:' % (1, s.__setitem__(1, 900))) s.getAll() print('\n删除元素22:') s.__delete__(22) s.getAll() |
|
|
