Когда указатель на связанный список меняет фактический список?

Question

У меня есть односвязный список L, и я создаю указатель на этот список P. Кажется, что иногда изменение P изменяет реальный список, в то время как в других случаях изменение P ничего не делает с реальным списком L и только изменяет то, чтоP указывает на.

Предположим, я создаю указатель на L, P = L (в python). Выполнение чего-то вроде P = P.next оставляет L без изменений, но P.next = P.next.next изменяет L. Аналогичным образом, изменение фактических данных, хранящихся в списке, путем изменения P.data фактически изменяет L.data.

Почему это происходит? Я чувствую, что упускаю что-то фундаментальное из указателей / ссылок.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

    def addNode(self, val):
        root = self
        while root.next is not None:
            root = root.next
        root.next = Node(val)

    def iterateLL(self):
        root = self
        print
        while root is not None:
            print(str(root.val) + " ", end="")
            root = root.next
        print()

if __name__ =="__main__":
    L = Node(1)
    L.addNode(2)
    L.addNode(3)
    L.addNode(4)

    # iterate through list and print:
    L.iterateLL()

    # changing value of pointer does not affect L
    P = L
    P = P.next
    L.iterateLL() # L is unchanged

    # changing "next" value of pointer does affect L
    P = L 
    P.next = P.next.next
    L.iterateLL() # now we've skipped node 2

    # changing data of pointer does affect L
    P = L
    P.val = 10
    L.iterateLL()

Приведенный выше код выполняется со следующим выводом (первая строка показывает исходный связанный список, вторая строка показывает, что список не изменяется послеизмените указатель P, в то время как третья и четвертая строки показывают, что список изменился)

1 2 3 4

1 2 3 4

1 3 4

10 3 4

Что здесь происходит? Почему изменение P не влияет на L, а изменение P.next и P.val влияет? Если все эти действия ведут себя одинаково, то при изменении указателя либо всегда не будет изменен связанный список (и поэтому P = P.next должен изменить L, избавившись от первого узла), или никогда изменить связанный список (и, следовательно, P.next = P.next.next должен оставить L без изменений)?

У меня такое ощущение, что это как-то связано с тем фактом, что L.next является указателем, как и P.next. Таким образом, изменение P.next приводит к изменению того, на что указывает L.next (?). Но я чувствую, что правила мне не ясны.

Answer 1

В большинстве случаев в Python, когда вы выполняете присваивание переменной, P в этом случае значение P изменяется, но объект, на который он первоначально ссылался, не,Это потому, что переменные Python - это просто ссылки / указатели на объекты. Вот пример:

var1 = "test1"
var2 = "test2"
var3 = var1 # var3 = "test1"
var1 = var2 # var1 = "test2"

print(var1) # "test2"
print(var2) # "test2"
print(var3) # "test1"

Так что же здесь происходит? Ну, мы просто меняем то, на что указывают эти переменные, мы не меняем базовый объект.

Теперь в вашем случае вы делаете следующее:

# changing value of pointer does not affect L
P = L
P = P.next
L.iterateLL() # L is unchanged

Когда вы делаете P = L и P = P.next, вы просто меняете то, на что указывает переменная P. Вы не вносите изменения в базовый объект, на который указывает P. Давайте представим это.

Оригинальная конфигурация:

P = L

P = L.next

Однако, когда вы делаете

P = L
P.next = P.next.next
L.iterateLL() # we've now skipped node two

Вы изменяете атрибут объекта, на который указывает P. Вы устанавливаете атрибут P.next, чтобы он указывал на P.next.next. Вы на самом деле не вносите изменения в базовый объект, на который изначально указывал P.next. При этом объект, на который P.next первоначально указывал, выходит из области видимости и очищается сборщиком мусора.

P.next = P.next.next

Судя по вашему коду, я предполагаю, что в этом случае вы намеревались удалить L из LinkedList и в итоге получить список, подобный "2 3 4". Для этого достаточно сделать L = L.next. Это заставит первый узел выйти из области видимости, и сборщик мусора должен очистить его.

В качестве краткого замечания я упомянул, что в большинстве случаев присваивание не вносит изменений в объект, на который указывает переменная. Однако свойства немного отличаются. Они переопределяют магический метод __set__, который позволяет редактировать базовый объект с помощью оператора присваивания. Здесь дело не в этом.

Answer 2

Вы написали,

# changing "next" value of pointer does not affect L
P = L
P = P.next
L.iterateLL() # L is unchanged

Однако вы не изменили следующее значение. Вы читаете из P.next. P.next был справа от задания. Чтобы изменить P.next, P.next должен находиться слева от оператора присваивания (=)

Затем вы пишете:

# changing "next.next" value of pointer does affect L
P = L 
P.next = P.next.next
L.iterateLL() # now we've skipped node 2

На этот раз P.next находится слева от оператора присваивания (=). Таким образом, вы действительно изменили его.

write_to = read_from