python上链表的添加方法

我建议你把 node 和 linkedlist 和 node 类型。A. node 参考了 next node .虽然a 双链表 参考了 head node 通常为a tail node 因此,添加一个新 node 是一个常量操作(即不需要遍历整个列表)。这很容易看出你需要一个新的 node 每次调用实例 add() :

class node:
    def __init__(self, item):
       self.item=item
       self.next=None

class linkedlist:
    def __init__(self):
        self.head = None
        self.tail = None
    def add(self, val):
        n = node(val)
        if self.head:
            self.tail.next = n
        else:
            self.head = n
        self.tail = n

myobj=linkedlist()
myobj.add(1)
myobj.add(2)
myobj.add(3)
print(
        myobj.head.item,
        myobj.head.next.item,
        myobj.head.next.next.item
)

以下是示例输出:

1 2 3

您只有1个对象和2个指向它的引用。在添加之前,您需要复制列表:

from copy import copy

class linkedlist:
    def __init__(self):
       self.item=None
       self.next=None
    def add(self,val):
       self.next=copy(self)
       self.item=val

myobj=linkedlist()
myobj.add(1)
myobj.add(2)
print(myobj.next.item) # prints 1

澄清一下:

print(myobj.item, id(myobj))
print(myobj.next.item, id(myobj.next))

使用您的代码:

2 140520931226768
2 140520931226768 # same object!

与我的:

2 140520931224368
1 140519593761456

更新:

首先,你的期望是错误的,你应该得到3和2,这是你戳破脑袋后列表中剩下的值。 要获得这些结果,您需要更新 a 指向。您可以通过添加 return self 在最后 add 和 pop 方法和重新分配 一 :

from copy import copy

class linkedlist:
    def __init__(self):
       self.item=None
       self.next=None
    def add(self,val):
       self.next=copy(self)
       self.item=val
       return self
    def pop(self):
       self=copy(self.next)
       return self
    
a=linkedlist()
a = a.add(1)
a = a.add(2)
a = a.add(3)
a = a.add(4)
a = a.pop()
print(a.item)
a = a.pop()
print(a.item)

但在我看来,这相当丑陋,我宁愿使用艾伦的方法。。。