Python全系列 教程
3567个小节阅读:5931.1k
目录
鸿蒙应用开发
C语言快速入门
JAVA全系列 教程
面向对象的程序设计语言
Python全系列 教程
Python3.x版本,未来主流的版本
人工智能 教程
顺势而为,AI创新未来
大厂算法 教程
算法,程序员自我提升必经之路
C++ 教程
一门通用计算机编程语言
微服务 教程
目前业界流行的框架组合
web前端全系列 教程
通向WEB技术世界的钥匙
大数据全系列 教程
站在云端操控万千数据
AIGC全能工具班
A A
White Night
双向链表是一种链表数据结构,每个节点除了包含指向下一个节点的指针外,还包含指向前一个节点的指针。这种特性使得在双向链表中,可以从任意一个节点开始,向前或向后遍历链表。
xxxxxxxxxx
class ListNode:
def __init__(self, val):
self.val = val
self.pre = None #指向前面节点的指针
self.next = None #指向后面节点的指针
xxxxxxxxxx
class MyLinkedList:
def __init__(self):
self.head = ListNode(0) #虚拟头节点
self.tail = ListNode(0) #虚拟尾节点
self.head.next = self.tail # 让虚拟头节点指向虚拟尾节点
self.tail.pre = self.head #虚拟尾节点指回虚拟头节点
self.size = 0
x def add_at_index(self,index:int,val:int) -> None:
# 判断index是否合法
if index > self.size:
return
index = max(0,index)
# 遍历index前一个节点
if index < self.size-index:
# 从头节点开始遍历
# 找到头节点
pred = self.head
for _ in range(index):
# 找到前驱节点
pred = pred.next
# 找到后继节点
succ = pred.next
else:
# 从尾节点开始遍历
succ = self.tail
for _ in range(self.size-index):
# 找到后继节点
succ = succ.pre
# 找到前驱节点
pred = succ.pre
# 创建新节点
add_node = ListNode(val)
add_node.pre = pred # 新节点的前驱节点为前驱节点
add_node.next = succ # 新节点的后继节点为后继节点
pred.next = add_node # 前驱节点的后继节点为新节点
succ.pre = add_node # 后继节点的前驱节点为新节点
# 链表长度加一
self.size += 1
xxxxxxxxxx
def add_at_head(self, val: int) -> None:
self.add_at_index(0, val)
xxxxxxxxxx
def add_at_tail(self, val: int) -> None:
self.add_at_index(self.size, val)
xxxxxxxxxx
def get(self,index:int) -> int:
# 判断index是否合法
if index < 0 or index >= self.size:
return -1
# 遍历index前一个节点
if index < 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.pre
return curr.val
如果索引index有效,则删除链表中的第index个节点
xxxxxxxxxx
def delete_at_index(self,index:int):
# 判断index是否合法
if index < 0 or index >= self.size:
return -1
# 遍历index,找到需要删除index节点的前驱节点和后继节点
if index < self.size-index:
pred = self.head
for _ in range(index):
pred = pred.next
succ = pred.next.next
else:
succ = self.tail
for _ in range(self.size-index-1):
succ = succ.pre
pred = succ.pre.pre
# 设置前驱节点的后继节点为后继节点后继节点
pred.next = succ
# 设置后继节点的前驱节点为前驱节点的前驱节点
succ.pre = pred
# 链表长度减一
self.size -= 1