Как он узнает, что будет дальше в этом связанном списке?
Я понимаю большую часть кода, но чего я не понимаю, так это того, что происходит в функции append_after. Как именно элементы в связанном списке добавляются друг за другом? Насколько я вижу, last_node.next никогда не указывает на следующий элемент. Также он говорит: «Хотя last_node.next не равен None», но разве он не None по умолчанию? Я не вижу, что сделало бы его не «Нет», если бы я специально не закодировал его для этого.
class node:
def __init__(self, data):
self.data = data
self.next = None
class linked_list:
def __init__(self):
self.head = None
def display(self):
node = self.head
while node is not None:
print(node.data)
node = node.next
def append_after(self, data):
new_node = node(data)
if self.head is None:
self.head = new_node
return
last_node = self.head # I'm assuming this starts at the letter "A"?
while last_node.next is not None: # What makes it not None?
last_node = last_node.next
last_node.next = new_node # It comes here after finishing the loop?
ll = linked_list()
ll.append_after("A")
ll.append_after("B")
ll.append_after("C")
ll.append_after("D")
ll.display()
ВЫХОД
A
B
C
D
Ниже приведен другой способ вызова объектов. Если я вызываю объекты, как в приведенном ниже примере, я могу легко это понять, потому что я ясно вижу, что определяется как следующий элемент, но я не понимаю, как функция append_after возвращает тот же результат.
ll = linked_list()
ll.head = node("A")
data2 = node("B")
data3 = node("C")
data4 = node("D")
ll.head.next = data2
data2.next = data3
data3.next = data4
ll.display()
Я использую Python 3, и я уже рассматривал подобные вопросы, но они не очень хорошо объяснялись. Что-то происходит под капотом, чего я не понимаю?
Я думал, что все довольно хорошо разъяснил, но я не понимаю, как код в функции append_after добавляет следующий узел. В нем говорится: «Хотя append_after.next — None», но в какой момент это «None»? И когда вы говорите, что голова всегда одна и та же, вы имеете в виду, что каждый раз, когда вызываются разные объекты, голова все равно будет первым элементом? в списке?
Ответы 1
Это может помочь визуализировать процесс. Когда выполняется ll = linked_list(), создается экземпляр linked_list, его атрибуту head присваивается значение None, а ссылка на этот экземпляр присваивается ll. Мы можем изобразить состояние следующим образом:
ll
↓
┌────────────┐
│ head: None │
└────────────┘
Теперь ll.append_after("A") называется. Во время этого вызова self имеет ссылку на связанный список, а с помощью new_node = node("A") создается новый узел с атрибутом data, установленным на «A», и атрибутом next, установленным на None. Давайте уже представим это состояние:
self (ll)
↓
┌────────────┐
│ head: None │
└────────────┘
┌────────────┐
│ data: "A" │
│ next: None │
└────────────┘
↑
new_node
Поскольку self.head — это None, мы попадаем в блок if, где выполняется self.head = new_node. Это делает новый экземпляр узла членом списка:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐
│ data: "A" │
│ next: None │
└────────────┘
↑
new_node
Функция append_after возвращается, и основная программа выполняет вызов ll.append_after("B"). Снова создается новый узел с помощью new_node = node("B"). Это приводит к такому состоянию:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │
│ next: None │ │ next: None │
└────────────┘ └────────────┘
↑
new_node
На этот раз условие if (self.head is None) неверно, поэтому мы получаем last_node = self.head, вводя другое имя, которое ссылается на первый узел в списке:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │
│ next: None │ │ next: None │
└────────────┘ └────────────┘
↑ ↑
last_node new_node
Теперь запускается цикл while, но его условие ложно, потому что last_node.next — это None, что указывает на то, что в настоящее время он является последним узлом в списке. И это то, что нам нужно: мы хотим иметь ссылку на последний узел в списке, чтобы мы могли присоединить новый узел сразу после него.
После цикла while (который не делал итераций) выполняем last_node.next = new_node. Это выполняет вложение:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │
│ next: ────────► │ next: None │
└────────────┘ └────────────┘
↑ ↑
last_node new_node
Функция возвращается. Давайте сделаем еще один звонок: ll.append_after("C"). Снова создается новый узел, условие if равно False, а last_node снова получает ссылку на первый узел в списке. Итак, непосредственно перед началом цикла while у нас есть это состояние:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │ │ data: "C" │
│ next: ────────► │ next: None │ │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
last_node new_node
На этот раз условие while истинно, что означает, что last_node не соответствует его названию — это не последний узел в списке, поэтому выполняется итерация цикла с last_node = last_node.next:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │ │ data: "C" │
│ next: ────────► │ next: None │ │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
last_node new_node
Теперь условие while истинно, что означает, что last_node действительно является последним узлом списка. Именно здесь нам нужно прикрепить новый узел. Итак, после выполнения last_node.next = new_node мы получаем:
self (ll)
↓
┌────────────┐
│ head: ─┐ │
└────────│───┘
▼
┌────────────┐ ┌────────────┐ ┌────────────┐
│ data: "A" │ │ data: "B" │ │ data: "C" │
│ next: ────────► │ next: ────────► │ next: None │
└────────────┘ └────────────┘ └────────────┘
↑ ↑
last_node new_node
Вызов ll.append_after("D") пройдёт тот же процесс: last_node снова начнётся слева и по циклу дойдёт до последнего узла в списке, а затем туда будет добавлен новый узел.
Я надеюсь, что это проясняет это.
Спасибо за ясное объяснение этого. Думаю, теперь я понимаю. Сначала делается «А», и он вызывает «Б». Затем он сначала пропускает цикл, потому что он ложный, а A.next становится новым узлом «B». Затем он вызывает «C», а B.next делает цикл истинным, поэтому last_node становится B, а B.next становится «C», а затем повторяется для D. Я очень ценю это. Я пытался понять это в течение нескольких дней, и я, наконец, понимаю это от и до. Я бы поставил вам палец вверх, но так как я новичок, это не позволит мне.
Я рад видеть, что это помогло вам. Просто замечание по терминологии: «и он вызывает B»: узлы не «вызываются». Это термин, используемый для вызова функций. Ссылаются на узлы.
Уточните, пожалуйста, что вам в этом непонятно. Вы уже определили, где назначается следующий узел, так как же вас смущает, что он может иметь значение, отличное от значения по умолчанию? Вы в курсе, что голова всегда одна и та же даже при последующих вызовах? Проверяли ли вы состояние списка на различных этапах?