불변 및 순환 참조

Question

예제 코드에서는 python을 사용 하겠지만 대부분의 프로그래밍 언어에서이 문제를 재현 할 수 있습니다.

class Node(object): 

    def __init__(self, value=None, prev=None, next=None): 
     self._value = value 
     self._prev = prev 
     self._next = next 

    def with_value(self, value): 
     return Node(value=value, prev=self._prev, next=self._next) 

    def with_prev(self, prev): 
     return Node(value=self._value, prev=prev, next=self._next) 

    def with_next(self, next): 
     return Node(value=self._value, prev=self._prev, next=next) 

그래서 기본적으로 this'd 우리가 이런 Node 인스턴스를 만들 수 있습니다 : 가정하자

나는 클래스가

node = Node() 
     .with_value(30) 
     .with_prev(
     Node() 
     .with_value(25)) 
     .with_next(
     Node() 
     .with_value(35)) 

여기서 문제는 각 Node 요구를 가지고 있다는 것입니다 이전 및 다음 노드에 대한 참조이므로 실제로는 with_prev 및 with_next 메소드를 수정해야합니다.

def with_prev(self, prev): 
    prev = prev.with_next(self) 
    return Node(value=self._value, prev=prev, next=self._next) 

그러나 이것은 올바르지 않습니다 ... 이전 노드에는 이제 버려진 인스턴스에 대한 next 참조가 있습니다.

나는 그것을 다른 방법을 시도 할 경우

주위 나는 비슷한 문제를 가지고 :

내 node 인스턴스가 이제 잘못된/오래된 prev 참조가

def with_prev(self, prev): 
    node = Node(value=self._value, prev=prev, next=self._next) 
    prev = prev.with_next(node) 
    return node 

.

이 문제를 어떻게 해결할 수 있습니까?

Answer 1

실제 참조로 느리게 평가되는 썽크에 대한 next 및 prev 참조를 변경하면됩니다. 이 작업은 매우 까다 롭지 만 전체 목록을 한 번에 초기화해야합니다.

더 쉬운 방법은 단일 링크 된 목록을 저장 한 다음 zipper을 사용하여 다시 트래버스 할 때 뒤로 링크를 추적하는 것입니다. 목록의 꼬리부터 시작하여 트래버스 할 수 있어야한다면, 순방향 링크와 역순으로 두 개의 목록을 저장하면됩니다.