### Python 实现单链表和双链表 #### 单链表定义与基本操作 为了在Python中实现单链表，首先需要定义节点(Node)类。每个节点包含两个部分：存储数据的部分(data)，以及指向下一个节点的链接(next)[^1]。 ```python class Node: def __init__(self, data=None): self.data = data self.next = None ``` 接着定义单链表(SinglyLinkedList)类，该类负责管理一系列Node对象并提供各种方法来进行增删查改等操作[^2]： ```python class SinglyLinkedList: def __init__(self): self.head = None # 插入新元素至头部 def insert_at_beginning(self, data): new_node = Node(data) new_node.next = self.head self.head = new_node # 删除指定位置处的元素 def delete_by_position(self, position): if not self.head or position < 0: return False temp = self.head if position == 0: self.head = temp.next return True prev = None count = 0 while(temp is not None and count != position): prev = temp temp = temp.next count += 1 if temp is None: return False prev.next = temp.next return True ``` #### 双向链表定义与基本操作 对于双向链表(DoubleLinkedList),除了上述提到的内容外还需要增加一个指向前驱(previous)方向的属性[^3]。因此修改后的节点结构如下所示: ```python class DNode: def __init__(self, data=None): self.data = data self.prev = None self.next = None ``` 同样地也需要重新设计对应的DoubleLinkedList类来支持新的功能需求: ```python class DoubleLinkedList: def __init__(self): self.head = None # 向列表前端添加项 def add_first(self, data): new_node = DNode(data) if not self.head: self.head = new_node else: new_node.next = self.head self.head.prev = new_node self.head = new_node # 移除最后一个元素 def remove_last(self): if not self.head: return None current = self.head while(current.next is not None): current = current.next last_data = current.data if current.prev is None: self.head = None else: current.prev.next = None del current return last_data ``` 以上代码展示了如何构建既包含单链表又含有双链表特性的Python程序框架，并提供了几种常见的链表操作作为示范.