python---自己实现双向链表常用功能
2024-09-07 16:24:46
这个和单向链表有几个功能是同样的代码。
但在add,insert,append,remove时,由于node拥有prev指针,
所以操作不一样。注意看注释。
# coding = utf-8 # 双向链表 class Node: # 双向链表存在两个指标,一个向前,一个向后 def __init__(self, new_data): self.data = new_data self.prev = None self.next = None def get_data(self): return self.data def set_data(self, new_data): self.data = new_data def get_next(self): return self.next def set_next(self, new_next): self.next = new_next def get_prev(self): return self.prev def set_prev(self, new_prev): self.prev = new_prev class DoubleList: def __init__(self): self.head = None # 作头插入时,需要要注意插入顺序, # 总之。要注意不要丢失next和prev。 def add(self, item): node = Node(item) if not self.is_empty(): # 待插入节点的后继区指向原头节点 node.set_next(self.head) # 原头节点的前驱区指向待插入节点 self.head.set_prev(node) # 将head指向node self.head = node # 作尾插入时,需要先判断是否为空列表。因为空列表时,没有next。 # 为空列表时,尾插入和头插入代码相同。 # 当不为空时,需要循环到底,再作插入处理 def append(self, item): node = Node(item) if self.is_empty(): # 将head指向node self.head = node else: # 移动到链表尾部 current = self.head while current.get_next() is not None: current = current.get_next() # 将尾节点cur的next指向node current.set_next(node) # 将node的prev指向cur node.set_prev(current) # 指定位置插入节点 def insert(self, pos, item): # 相当于头插入 if pos <= 0: self.add(item) # 相当于尾插入 elif pos >= self.size(): self.append(item) else: node = Node(item) count = 0 current = self.head # 先将游标指到要插入位置 while count < pos - 1: count += 1 current = current.get_next() # 将node的prev指向cur node.set_prev(current) # 将node的next指向cur的下一个节点 node.set_next(current.get_next()) # 将cur的下一个节点的prev指向node current.get_next().set_prev(node) # 将cur的next指向node current.set_next(node) # 删除指定节点数据 def remove(self, item): # 删除时,不需要再使用一个prev变量了。因为双向链表本身有这个指针 current = self.head while current is not None: if current.get_data() == item: # 在找到节点之后,需要判断是否为首节点 if current == self.head: self.head = current.get_next() # 判断链表是否只有一个结点 if current.get_next(): current.get_next().set_prev(None) else: current.get_prev().set_next(current.get_next()) # 如果存在下一个结点,则设置下一个结点 if current.get_next(): current.get_next().set_prev(current.get_prev()) break else: current = current.get_next() # 查找指定数据是否存在 def search(self, item): current = self.head found = False while current is not None: if current.get_data() == item: found = True current = current.get_next() return found def is_empty(self): return self.head is None def __len__(self): return self.size() def size(self): count = 0 current = self.head while current is not None: count += 1 current = current.get_next() return count def show(self): current = self.head while current is not None: print(current.get_data(), end=' ') current = current.get_next() print('\n') if __name__ == '__main__': d_list = DoubleList() print(d_list.is_empty()) d_list.add(5) d_list.add(4) d_list.add(76) d_list.add(23) d_list.show() d_list.append(48) d_list.show() d_list.append(234) d_list.show() d_list.insert(2, 100) d_list.show() d_list.remove(5) d_list.show() print(d_list.search(48))
C:\Users\Sahara\.virtualenvs\test\Scripts\python.exe C:/Users/Sahara/PycharmProjects/test/python_search.py True True Process finished with exit code
最新文章
- Redis五种数据结构简介
- ARC和MRC混编
- win7 telnet
- Hibernate总结4之HQL
- Tomcat性能调优
- 【Java】XML解析之DOM
- mysql ---复制表结构---创建新表
- Entity Framework Repository模式
- [LeetCode]题解(python):118-Excel Sheet Column Title
- (原)ubuntu16中安装moses
- Csharp多态的实现(接口)
- 在maven仓库中查找jar
- 科技股晴间多云 阿里京东IPO或受影响
- qq客服问题
- composer 安装和修改中国镜像
- 日程管理 FullCalendar
- java_29打印流
- Java如何显示线程状态?
- android(二) SurfaceView
- TraceSource记录程序日志