python linklist指針和大小

我是一名菜鳥python程序員。我在下面看到了leetcode對鏈表的定義。我對這個概念有兩個問題，任何幫助將不勝感激。在此先感謝python linklist指針和大小

# 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是「無」，然後將其分配給另一個ListNode類型，但我之前得到頭的相同尺寸和在這個變化之後，我認爲head的大小應該更大，因爲它的一個成員（next）會從None類型更改爲ListNode類型。我對此感到困惑，非常感謝！

PS。根據我的理解，如果我不斷向鏈表添加新節點，由於越來越多'嵌套'成員'下一個'，頭部會越來越大，只是指出我出錯的地方，謝謝。

來源

2016-09-11 Muhe Xie

它的python你可以分配幾乎任何東西，但它需要一個'Node'類型，它有一個'next'參數供列表工作。你最好爲list類創建一個'add'方法，而不是明確地添加到'.next'。你可以在那裏放入一個類型檢查，或者在python 3.5+中有一個類型的概念。無論如何，大小將保持不變，因爲實際節點只是一個值和對下一個節點的引用。如果您想知道有多少個節點，您需要遍歷列表以統計節點數量，或者在添加節點時保持計數。 –

感謝您的澄清，還有一個關於引用的問題，如果引用的大小沒有改變，爲什麼我們會有不同大小的引用int和list的引用，因爲在這種情況下它們都是引用他們所指的對象是不同的。 –

我不是100％肯定是誠實的。但我知道，儘管python中的所有內容都是參考。一個int值是一個不可變的引用，當它被賦值給（類似於在C++中傳遞值）時被複制，但像內建列表，字符串等的ListNode是一個可變引用，因此可以通過傳遞給它的函數（類似於C++中的非const引用）。這種語義差異可能會導致大小的差異。 [這]（http://stackoverflow.com/questions/6158907/what-does-python-treat-as-reference-types）問題可能是有趣的。 –

問題1：

Python變量是動態類型的。（即一個變量可以保存一個int，然後保存一個列表，然後是任何其他任意對象，等等）。

在你的情況，Head.next開始通過引用，None一個NoneType對象。

在爲其分配不同的值（ListNode(2)）後，Head.next現在引用新創建的ListNode對象。

問題2：

爲什麼尺寸沒有改變。我不是專家，關於python的sys.getsizeof是如何工作的，但是從我可以收集的信息來看，List.next在兩種情況下都是引用變量（即引用其他對象的變量）。大小不會改變，因爲sys.getsizeof找到對象變量的大小。在這兩種情況下，Head.next只是對某個其他對象的引用。

請參閱：How do I determine the size of an object in Python?，以獲得關於sys.getsizeof如何工作的更完整答案。

來源

2016-09-11 23:26:54

非常感謝！那麼你是說當我談論一個引用變量時，函數sizeof（Var1）會獲取它自身的引用變量的大小，而不是它指向的對象的大小？ –

@MuheXie是的，這是我從閱讀中瞭解到的。 –

我對鏈接列表的解釋。

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]

來源

2016-09-11 23:27:11 TheLazyScripter

python linklist指針和大小

回答

相關問題