双向链表
还不清楚单向链表的同学可以去看我另一篇文章,实践总结:一篇搞懂链表——单链表和双指针技巧
首先,我们先看下双向链表(下文用双链表表述)的图示,见下图:
与单链表不同的是,双链表有两个方向,对应单链表节点中的一个引用字段next,双链表每个节点中都含有两个引用字段,我们用prev和next表示。
也就是在双链表中的每个节点,包含一个数值val,还包括两个引用字段,一个是prev 指向前一个节点,next 指向后一个节点。
添加操作 - 双链表
如果我们想在现有的结点 prev 之后插入一个新的结点 cur,我们可以将此过程分为两个步骤:
- 链接 cur 与 prev 和 next,其中 next 是 prev 原始的下一个节点;
- prev 和 next再次指向cur
这两步在代码上的实现,可以简化为:
new_node.next = curr.next
new_node.prev = curr
curr.next.prev = new_node
curr.next = new_node
删除操作 - 双链表
如果我们想从双链表中删除一个现有的结点 cur,我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。
举个例子:
设计一个双链表
要求:
实现一个向链表。
实现 MyLinkedList 类:文章来源:https://www.toymoban.com/news/detail-839143.html
- MyLinkedList() 初始化 MyLinkedList 对象。
- int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
- void addAtHead(int val) 将一个值为 val的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。
- void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
- void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度,那么该节点会被追加到链表的末尾。如果 index 比长度更大,该节点将 不会插入 到链表中。
- void deleteAtIndex(int index) 如果下标有效,则删除链表中下标为 index 的节点。
代码实现:文章来源地址https://www.toymoban.com/news/detail-839143.html
class ListNode:
def __init__(self, val=0):
self.val = val
# 标记向后的变量
self.next = None
# 标记向前的变量
self.prev = None
class MyLinkedList:
def __init__(self):
# 初始化头节点
self.head = None
# 初始化尾节点
self.tail = None
self.size = 0
# 获取链表中下标为 index 的节点的值
def get(self, index: int) -> int:
# 在index有效的范围内,遍历得到curr即可
if 0 <= index < self.size:
curr = self.head
for _ in range(index):
curr = curr.next
return curr.val
else:
return -1
#将一个值为 val 的节点插入到链表中第一个元素之前
def addAtHead(self, val: int) -> None:
self.addAtIndex(0, val)
# 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.size, val)
# 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
def addAtIndex(self, index: int, val: int) -> None:
if index < 0 or index > self.size:
return None
new_node = ListNode(val)
# 插入头节点
if index == 0:
new_node.next = self.head
if self.head:
self.head.prev = new_node
else:
self.tail=new_node
self.head = new_node
self.size += 1
return
if index == self.size:
new_node.prev = self.tail
if self.tail:
self.tail.next = new_node
else:
self.head=new_node
self.tail = new_node
self.size += 1
return
if 0 < index < self.size:
curr = self.head
# 从头节点遍历链表到index的前一位
for _ in range(index - 1):
curr = curr.next
new_node.next = curr.next
new_node.prev = curr
curr.next.prev = new_node
curr.next = new_node
self.size += 1
return
return
# 删除链表中下标为 index 的节点。
def deleteAtIndex(self, index: int) -> None:
# 如果删除的是头节点
if index == 0:
# 当链表长度等于1时
if self.size == 1:
# 删除之后链表就为空了
self.head = None
self.tail = None
self.size -= 1
else:
self.head = self.head.next
self.head.prev = None
self.size -= 1
# 删除尾节点
elif index == self.size - 1:
self.tail = self.tail.prev
self.tail.next = None
self.size -= 1
elif 0 < index < self.size - 1:
curr = self.head
# 遍历到当前节点
for _ in range(index):
curr = curr.next
# 当前节点的前一个节点指向当前节点下一个节点
curr.prev.next = curr.next
# 当前节点后一个节点的前一个节点,是当前节点的前一个节点
curr.next.prev = curr.prev
self.size-=1
return None
到了这里,关于什么是双向链表,一篇搞懂双向链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!