Добавить метод для связанного списка на Python
Я пытаюсь написать метод добавления для связанного списка на Python, но он ведет себя не так, как ожидалось.
class linkedlist:
def __init__(self):
self.item=None
self.next=None
def add(self,val):
self.next=self
self.item=val
Однако это не работает. Когда я создаю объект:
myobj=linkedlist()
myobj.add(1)
myobj.add(2)
print(myobj.next.item)
дает 2, а не 1, как я ожидал. Где я ошибся?
Я попытался посмотреть Безопасно ли заменять объект self другим объектом того же типа в методе?но это не помогает.
да, это была опечатка
Проблема в том, что вы меняете объект вместо добавления новых узлов. Каждый раз, когда вы назначаете себя для следующего, существует только 1 экземпляр объекта связанного списка.
как мне тогда изменить его, используя определение связанного списка?
Можете ли вы объяснить подробнее, что вы подразумеваете под «назначить себя следующим»?
Ответы 2
Предлагаю вам разделить типы node и linkedlist и node. node имеет ссылку на nextnode. В то время как linkedlist имеет ссылку на headnode и обычно на tailnode, поэтому добавление нового node является постоянной операцией (т. е. не требует обхода всего списка). Это позволяет легко увидеть, что вам нужен новый экземпляр node для каждого вызова add():
class node:
def __init__(self, item):
self.item=item
self.next=None
class linkedlist:
def __init__(self):
self.head = None
self.tail = None
def add(self, val):
n = node(val)
if self.head:
self.tail.next = n
else:
self.head = n
self.tail = n
myobj=linkedlist()
myobj.add(1)
myobj.add(2)
myobj.add(3)
print(
myobj.head.item,
myobj.head.next.item,
myobj.head.next.next.item
)
и вот пример вывода:
1 2 3
Но почему мой оригинальный метод не работает? Есть ли способ заставить его работать без добавления еще одного узла класса?
После первого и второго вызова add() myobj.next = myobj единственное, что вы меняете, — это значение myobj.item с 1 на 2.
но есть ли способ заставить мой исходный метод работать без добавления еще одного вспомогательного класса?
@simplylemon См. ответ Жюльена, однако я смиренно полагаю, что мой ответ более ясен, поскольку вы добавляете новый узел, а не еще один связанный список. Если вы хотите сделать это таким образом, хотя бы переименуйте его в node.
У вас есть только 1 объект и 2 ссылки, указывающие на него. Вам необходимо скопировать список перед добавлением в него:
from copy import copy
class linkedlist:
def __init__(self):
self.item=None
self.next=None
def add(self,val):
self.next=copy(self)
self.item=val
myobj=linkedlist()
myobj.add(1)
myobj.add(2)
print(myobj.next.item) # prints 1
Чтобы уточнить:
print(myobj.item, id(myobj))
print(myobj.next.item, id(myobj.next))
с вашим кодом:
2 140520931226768
2 140520931226768 # same object!
С моим:
2 140520931224368
1 140519593761456
ОБНОВЛЯТЬ:
Во-первых, ваши ожидания неверны: вы должны получить 3 и 2 — значения, оставшиеся в списке после того, как вы высунули голову.
Чтобы получить эти результаты, вам нужно обновить то, на что указывает a. Вы можете сделать это, добавив return self в конце методов add и pop и переназначив a:
from copy import copy
class linkedlist:
def __init__(self):
self.item=None
self.next=None
def add(self,val):
self.next=copy(self)
self.item=val
return self
def pop(self):
self=copy(self.next)
return self
a=linkedlist()
a = a.add(1)
a = a.add(2)
a = a.add(3)
a = a.add(4)
a = a.pop()
print(a.item)
a = a.pop()
print(a.item)
Но, по моему мнению, это довольно некрасиво, и я бы предпочел использовать подход Аллана...
ОП не создал конструктор, позволяющий это сделать, требуемый конструктор по сути будет конструктором копирования...
ОП, возможно, не волнует, но myobj должен указывать на голову, а не на хвост, чтобы список был связан, не так ли?
Почему это не работает для метода pop()? (Я добавил продолжение в исходный вопрос.)
Если у вас есть отдельный вопрос, задайте его в отдельном посте, пожалуйста. Ответ заключается в том, на что только что указал @AllanWind.
Что значит, я никогда не запускал вышеперечисленное?