【数据结构】双向链表

**双向链表**

双向链表是一种特殊的线性数据结构，它允许在链表中既可以从头部插入或删除元素，也可以从尾部插入或删除元素。这种数据结构在某些场景下比单向链表更有效率。

### 双向链表的定义双向链表由一系列的结点组成，每个结点包含一个值和两个指针：一个指向前一个结点（prev），一个指向后一个结点（next）。

markdown+---------------+
| 值 | prev | next |
+---------------+

class Node:
 def __init__(self, value):
 self.value = value # 值 self.prev = None # 前一个结点 self.next = None # 后一个结点

class DoublyLinkedList:
 def __init__(self):
 self.head = None # 头结点 self.tail = None # 尾结点 self.size =0 # 结点数量

def insert(self, value, position=None):
 if position is None:
 position = self.size node = Node(value)
 if position ==0:
 if self.head is not None:
 self.head.prev = node else:
 self.tail = node node.next = self.head self.head = node elif position == self.size:
 if self.tail is not None:
 self.tail.next = node else:
 self.head = node node.prev = self.tail self.tail = node else:
 prev_node = self._get_node(position -1)
 next_node = prev_node.next prev_node.next = node node.prev = prev_node node.next = next_node if next_node is not None:
 next_node.prev = node self.size +=1

def delete(self, position):
 if position < 0 or position >= self.size:
 raise ValueError("Invalid position")
 node = self._get_node(position)
 if node.prev is not None:
 node.prev.next = node.next else:
 self.head = node.next if node.next is not None:
 node.next.prev = node.prev else:
 self.tail = node.prev self.size -=1

def find(self, value):
 current = self.head while current is not None:
 if current.value == value:
 return current current = current.next return None

def traverse(self):
 current = self.head while current is not None:
 yield current.value current = current.next

dll = DoublyLinkedList()

# 插入元素dll.insert(1)
dll.insert(2)
dll.insert(3)

# 删除元素dll.delete(1)

# 查找元素print(dll.find(2).value) # 输出:2# 遍历链表for value in dll.traverse():
 print(value) # 输出:1,3