python链接列表指针和大小

Question

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

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

Q1只是想知道"self.next"的类型是什么，我知道在C++中，它应该是一个表示下一个节点地址的指针。但是python没有那个类型，所以我很困惑"下一个"是什么类型

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

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

首先head.next为"None"，然后将其分配给另一个ListNode类型，但在这次更改前后，我得到了相同大小的头，我认为头的大小应该更大，因为它的一个成员(next(从None类型更改为ListNode类型。我只是对此感到困惑，非常感谢！

PS。在我的理解中，如果我不断地向链接列表中添加新节点，那么头会越来越大，因为"下一个"的"嵌套"成员越来越多，只需指出我错在哪里，谢谢。

Answer 1

问题1:

Python变量是动态类型化的。(即，一个变量可以包含一个int，然后包含一个list，然后包含任何其他任意对象，等等(。

在您的情况下，Head.next通过引用None一个NoneType对象开始。

为其指定不同的值(ListNode(2)(后，Head.next现在将引用新创建的ListNode对象。

问题2:

为什么尺寸不变。我不是python的sys.getsizeof如何工作的专家，但据我所知，List.next在这两种情况下都是引用变量(即引用其他对象的变量(。大小不会改变，因为sys.getsizeof会查找对象变量的大小。其中Head.next在这两种情况下都只是对某个其他对象的引用。

请参阅，如何在Python中确定对象的大小？，以获得关于CCD_ 10如何工作的更完整答案。

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]