python - 在 Python 的链表中有效地在尾部插入节点
问题描述
我正在尝试在 O(1) 时间内实现一个单链表,inserts
并deletes
在双方之间实现。为此,我保存了一个指向head
and的指针tail
。
我遇到的麻烦是我的insert_tail
方法。这是我的伪代码:
If there is no head or tail,
Set the head AND tail to the new Node
Otherwise,
Insert the new node as a child of the tail
Set the tail to that new node
这是我的 Python 3 代码:
class Node:
def __init__(self, val):
self.val = val
self.next = None
def __str__(self):
if self.next:
return "{} -> {}".format(self.val, self.next.val)
else:
return "{}".format(self.val)
class LinkedList():
def __init__(self, init):
self.head = Node(init)
self.tail = Node(init)
# Search at O(n)
def search(self, val) -> Node:
pass
# Insert head or tail at O(1). Returns new node.
def insert_head(self, val) -> None:
inserting = Node(val)
inserting.next = self.head
self.head = inserting
# Inserting to empty case
if self.tail == None:
self.head = inserting
self.tail = inserting
return self.head
def insert_tail(self, val) -> None:
inserting = Node(val)
# Inserting to empty case
if self.head == None and self.tail == None:
self.head = inserting
self.tail = inserting
else:
# Change the value of the tail
self.tail.next = inserting
self.tail = self.tail.next
# Insert average case O(n) + 1
def insert(self, val) -> Node:
pass
# Delete at O(1).
def delete(self, val) -> None:
pass
def __str__(self):
return str(list(self))
def __iter__(self):
node = self.head
while node:
yield node.val
node = node.next
# 14, 12, 11, 19, 17, 16, 30, 18, 22, 21, 24, 23, 15
linked = LinkedList(30)
linked.insert_head(16)
linked.insert_head(17)
linked.insert_head(19)
linked.insert_head(11)
linked.insert_head(12)
linked.insert_head(14)
print(linked)
linked.insert_tail(18)
linked.insert_tail(22)
linked.insert_tail(21)
linked.insert_tail(24)
linked.insert_tail(23)
linked.insert_tail(15)
print(linked) # Should actually be: [14, 12, 11, 19, 17, 16, 30, 18, 22, 21, 24, 23, 15]
# But instead it printsas if a new tail was never inserted: [14, 12, 11, 19, 17, 16, 30]
解决方案
要在 O(1) 时间内对两边进行删除,您需要一个双向链表;否则在删除后找到新的尾部需要从头部迭代。
推荐阅读
- apache-spark - Spark 配置调优
- r - 如何修复:训练错误[, 1:9] : 维数不正确
- python - 创建“综合点”
- node.js - MongoDB NodeJS Native Driver(mongodb) vs Mongo Shell 性能
- r - 如何计算数据帧行中某些字符串的频率?
- python - git push heroku master 如何在heroku服务器的数据库中保存文件/文件夹数据
- c# - AutoMapper 从 ICollection 中删除所有元素
EF 核心代理实体的属性 - c - 为什么“查询期间丢失与 MySQL 服务器的连接”错误时不时发生(引发超时,查询前 ping)
- visual-studio - Online Visual Studio 中的早期适配器访问级别是什么?
- angular - 有没有办法为在组件内部计算一次的组件创建 css 规则?