1.双链表的定义
1.1 节点的定义
双链表中节点： 一个节点中 包括数值， 前指针， 后指针；
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
self.prev = None
1.2 链表的初始化
哨兵节点 产生两个 伪节点：
sentinel nodes as pseudo-head and pseudo-tail
包含了 伪头节点， 和 伪 尾节点；
class MyLinkedList:
def __init__(self):
self.size = 0
# sentinel nodes as pseudo-head and pseudo-tail
self.head, self.tail = ListNode(0), ListNode(0)
self.head.next = self.tail
self.tail.prev = self.head
2. 实现重点：
- 寻找前驱节点和 后继节点时， 先判断 从短的 一端开始：
- 如果 目标节点 靠近 头节点， 从 伪头节点开始
- 如果目标节点靠近 尾节点， 从 伪 尾节点开始
2.1 链表 中 节点的 插入；
addAtIndex，addAtHead 和 addAtTail：
找到要插入节点的前驱节点和后继节点。如果要在头部插入节点，则它的前驱结点是伪头。如果要在尾部插入节点，则它的后继节点是伪尾。
通过改变前驱结点和后继节点的链接关系添加元素。
to_add.prev = pred
to_add.next = succ
pred.next = to_add
succ.prev = to_add
2.2 链表 中 节点的 删除；
deleteAtIndex：
和插入同样的道理。
找到要删除节点的前驱结点和后继节点。
通过改变前驱结点和后继节点的链接关系删除元素
pred.next = succ
succ.prev = pred
2.2 链表 中 节点的 获取；
get：
通过比较 index 和 size - index 的大小判断从头开始较快还是从尾巴开始较快。
从较快的方向开始。
# choose the fastest way: to move from the head
# or to move from the tail
if index + 1 < self.size - index:
curr = self.head
for _ in range(index + 1):
curr = curr.next
else:
curr = self.tail
for _ in range(self.size - index):
curr = curr.prev
3 双链表的完整代码；
class LinkNode:
def __init__(self, x):
self.val = x
self.prev = None
self.next = None
class BiLinkList:
def __init__(self):
self._head = LinkNode(None)
self._tail = LinkNode(None) # sentinel nodes as pseudo-head node and pseudo-tail
self._count = 0
self._head.next = self._tail
self._tail.prev = self._head
def get(self, index: int) -> int:
if index < 0 or index >= self._count:
return
# 判断从 短的那一端测开始，
# 此处 Index + 1: 代表 考虑当只有一个元素时的情况，
if index +1 < self._count - index:
cur = self._head # 目标节点靠近头节点， 则从伪头节点开始；
for _ in range(index + 1):
cur = cur.next
else:
# 目标节点靠近尾节点 ， 则从伪 尾节点开始， 往前推进的次数；
cur = self._tail
for _ in range(self._count - index):
cur = cur.prev
return cur.val
# pred: predecessor: 前驱节点 successor： 后继节点；
def addAtIndex(self, index:int, val: int) -> None:
if index >= self._count:
return
if index < 0:
index = 0
# 判断从 短的那一端测开始，
if index < self._count - index:
pred = self._head # pred 从 伪头节点 开始 往后走；
for _ in range(index):
pred = pred.next # 此时 循环结束后， pred 代表 插入节点的 前驱节点；
succ = pred.next # succ 代表插入节点的 后继节点；
else: # 否则，当index 靠近尾节点时， 从伪尾节点开始 往前走；
succ = self._tail
for _ in range(self._count - index): # 此时 _count - index : 代表往前走的次数；
succ = succ.prev
pred = succ.prev
add_node = LinkNode(val) # 初始化节点，
self._count += 1 # 链表节点 个数 加 一；
add_node.next = succ
add_node.prev = pred
pred.next = add_node
succ.prev = add_node
def addAtHead(self, val: int) -> None:
add_node = LinkNode(val)
self._count += 1
pred = self._head
succ = self._head.next
add_node.prev = pred
add_node.next = succ
pred.next = add_node
succ.prev = add_node
def addAtTail(self, val: int) -> None:
add_node = LinkNode(val)
self._count += 1
succ = self._tail
pred = self._tail.prev
add_node.prev = pred
add_node.next = succ
pred.next = add_node
succ.prev = add_node
def delete(self, index) -> None:
if index < 0 or index >= self._count:
return
if index < self._count - index:
pred = self._head
for _ in range(index):
pred = pred.next
succ = pred.next.next
else:
succ = self._tail
# 注意这里是 删除Index 节点， 能够取得到index 处， 故需要 减一；
for _ in range(self._count - index - 1 ):
succ = succ.prev
pred = succ.prev.prev
self._count -= 1
pred.next = succ
succ.prev = pred
def removeElements(self, target: int) -> None:
def traversal(self,) -> None: