在 Python 的链表中有效地在尾部插入节点

Question

我正在尝试实现一个在O(1(时间内向双方inserts和deletes的单向链表。为此，我保存了一个指向head和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]

Answer 1

要在 O(1( 时间内对两边进行删除，你需要一个双向链表;否则在删除后找到新的尾巴需要从头部迭代。