[TypeScript] 자료 구조로 담아내기. #14 - 연결 리스트(with. 이중 연결)

이번 편은 이전 편으로부터 이어집니다.

연결 리스트의 또 다른 형태는 이중 연결 리스트입니다. 후임자의 참조만 저장하는 단일 연결 리스트와 달리 이중 연결 리스트는 선임자의 참조도 함께 저장합니다.

interface DoublyLinkedListNode<T> extends DoublyLinkedList<T> {
    linkBefore(succ: DoublyLinkedListNode<T>): void;
    linkAfter(pred: DoublyLinkedListNode<T>): void;

    prev(): DoublyLinkedListNode<T>;
    next(): DoublyLinkedListNode<T>;

    // ...
}

class DoublyLinkedListNodeImpl<T> implements DoublyLinkedListNode<T> {
    private predecessor: DoublyLinkedListNode<T> = DoublyLinkedListNullNode.get();
    private successor: DoublyLinkedListNode<T> = DoublyLinkedListNullNode.get();

    linkBefore(succ: DoublyLinkedListNode<T>): void {
        if(succ === this.next()) { return; }
        this.successor = succ;
        succ.linkAfter(this);
    }

    linkAfter(pred: DoublyLinkedListNode<T>): void {
        if(pred === this.prev()) { return; }
        this.predecessor = pred;
        pred.linkBefore(this);
    }

    // ...
}

이중 연결 리스트는 양방향 연결이 가능합니다. 기준을 선임자에 둘 수도 있고, 후임자에 둘 수도 있지요. 간단하게 설명하면 둘 중 하나의 link 연산이 호출되면 방향에 맞게 이미 연결되었는지 확인합니다. 만약 연결되지 않았다면 방향에 맞는 연결을 설정하고, 역방향의 link 연산을 호출합니다. 이렇게 하면 어느 쪽을 호출하든 동일한 결과를 얻을 수 있습니다.

양방향 접근 및 탐색

interface DoublyLinkedList<T> {
    access(index: number): DoublyLinkedList<T>;

    searchForwards(element: T): DoublyLinkedList<T>;
    searchBackwards(element: T): DoublyLinkedList<T>;

    // ...
}

양방향 참조를 유지하는 덕분에 접근과 탐색을 양방향으로 할 수 있게 됩니다.

class DoublyLinkedListNodeImpl<T> implements DoublyLinkedListNode<T> {
    access(index: number): DoublyLinkedList<T> {
        let curr: DoublyLinkedListNode<T> = this;

        let i = index;
        for(; i < 0; i++) { curr = curr.prev(); }
        for(; i > 0; i--) { curr = curr.next(); }
        return curr;
    }

    searchBackwards(element: T): DoublyLinkedList<T> {
        let curr: DoublyLinkedListNode<T> = this;
        while(!curr.isNull()) {
            if(curr.next().is(element)) { break; }
            curr = curr.prev();
        }
        return curr;
    }

    // ...
}

access의 경우, 음수이면 역방향, 양수이면 정방향으로 취급합니다. search는 방향마다 따로 둡니다. 하지만 역방향 또한 정방향 탐색과 큰 차이점은 없어 유사하게 구현할 수 없습니다.

이중 연결 리스트의 접근자는 첫 노드?

연결 리스트의 접근자에 대해 다시 한번 생각해 볼 필요가 있습니다. 단일 연결 리스트는 후임자의 참조만 보관하여 첫 노드를 접근자로 하기에는 곤란한 부분이 있었습니다. 하지만 이중 연결 리스트는 선임자의 참조를 함께 보관하기 때문에, 기존에 언급했던 문제는 자연스레 해결됩니다. 그렇다면 첫 노드를 접근자로 선택하는 게 좋을까요? 이는 선택 사항이지만 선임자를 접근자로 두는 이점은 여전히 존재합니다.

만약 첫 노드를 접근자로 하고 insertFirst나 deleteFirst를 사용하면 첫 노드가 변경되므로 새로운 참조가 반환됩니다. 하지만 선임자를 접근자로 한다면 연산 후에도 동일한 연결 리스트에 대해 여전히 같은 참조를 유지할 수 있습니다. 이는 큰 문제는 아니므로 각자 원하는 결정을 할 수 있습니다. 두 방법을 서로 비교해 보고 더 적절한 선택을 하길 바랍니다!

읽어주셔서 감사합니다!

묻고 답하기

개인적인 판단에 의해 적절하다고 여겨지는 경우, 모두가 볼 수 있도록 이곳에 문답이 추가됩니다. 그렇지 않더라도 질문에 대한 답변은 별도로 이루어집니다.