python链接列表指针和大小

Question

我是一个新手python程序员。我在下面看到了leetcode对链表的定义。我有2个关于这个概念的问题，任何帮助都将不胜感激。提前谢谢

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

我只是想知道自我。下一个“我在C++中知道，它应该是一个指针，它代表下一个节点的地址。但是python没有这种类型，所以我不知道“next”是什么类型。你知道吗

有人告诉我下一个只是一个名字。如果是这样，我运行下面的代码

head =ListNode(1)
print sys.getsizeof(head)
head.next = ListNode(2)
print sys.getsizeof(head)

首先头。下一个为“None”，然后将其分配给另一个ListNode类型， 但是我得到的head大小在这个更改前后是一样的，我认为head的大小应该更大，因为它的一个成员（next）从None类型更改为ListNode类型。我只是很困惑，非常感谢！你知道吗

另外，在我的理解中，如果我继续在链接列表中添加新的节点，头部会越来越大，因为接下来有越来越多的“嵌套”成员，请指出我的错误，谢谢。你知道吗

Answer 1

问题1：

Python变量是动态类型的。（也就是说，一个变量可以保存一个int，然后保存一个list，然后保存任何其他任意对象，等等）。你知道吗

在您的例子中，Head.next从引用None一个NoneType对象开始。你知道吗

在为它赋值（ListNode(2)）之后，Head.next现在引用新创建的ListNode对象。你知道吗

问题2：

为什么尺寸不变。 我不是python的sys.getsizeof工作原理方面的专家，但据我所知，是这样吗列表.下一步在这两种情况下都是引用变量（即引用其他对象的变量）。大小不会改变，因为sys.getsizeof会找到对象变量的大小。其中Head.next在这两种情况下都只是对其他对象的引用。你知道吗

有关sys.getsizeof如何工作的更完整答案，请参见How do I determine the size of an object in Python?。你知道吗

Answer 2

我对链表的理解。你知道吗

class LinkedList(object):
    class Node(object):
        def __init__(self, val=None, next=None, previous=None):
            self.val = val
            self.next = next
            self.last = previous

    def __init__(self):
        self.length = 0
        self.start = None
        self.end = None

    def append(self, value):
        self.length += 1
        if not self.start:
            self.start = self.Node(value)
        else:
            if not self.end:
                self.end = self.Node(value)
                self.end.previous = self.start
                self.end.next = self.start
                self.start.next = self.end
            else:
                end = self.Node(value)
                self.end.next = end
                end.previous = self.end
                self.end = end
                self.end.next = self.start

    def prepend(self, value):
        self.length += 1
        if not self.start:
            self.start = self.Node(value)
        else:
            n = self.Node(value, self.start, self.end)
            self.start.previous = n
            self.start = n

    def __len__(self):
        return self.length

    def __iter__(self):
        self.position = 0
        return self

    def next(self):
        self.position += 1
        if self.position-1 >= len(self):
            raise StopIteration
        if self.position-1 == 0:
            return self.start
        cnt = 0
        n = self.start
        while cnt<self.position-1:
            n = n.next
            cnt += 1
        return n


    def __getitem__(self, index):
        if index == 0:
            return self.start

        if index == -1:
            return self.end

        cnt = 0
        n = self.start
        while cnt<index+1:
            n = n.next
            cnt += 1
        return n.val

    def __repr__(self):
        return repr(tuple(x.val for x in self))

l = LinkedList()
l.append(4)
l.append(5)
l.append(3)
l.prepend(0)
print l
print l[1]