python linklist указатель и размер

Question

Я новичок программиста на питоне. Ниже приведено описание связанного списка в leetcode. У меня есть 2 вопроса для этой концепции, любая помощь будет оценена. Заранее спасибо

# 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, , но я получаю тот же размер головы до и после этого изменения, который, я думаю, размер головы должен быть больше, поскольку один из его членов (следующий) изменяется с типа None на тип ListNode. Я просто смущен, спасибо вам большое!

PS. В моем понимании, если я буду добавлять новые узлы в список ссылок, голова будет больше и больше, так как все больше и больше «вложенных» членов «следующий», просто укажите, где я ошибаюсь, спасибо.

Answer 1

Вопрос 1:

переменные Python динамически типизированный. (т. е. переменная может содержать int, а затем содержать список, а затем любой другой произвольный объект и т. д.).

В вашем случае Head.next начинается со ссылок, None a 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.

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]