[TypeScript] 자료 구조로 담아내기. #12 - 연결 리스트(with. null 노드)

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

조금 예리하신 분들은 이전 편에서 다룬 헤드 노드만으로는 충분치 않다는 것을 느끼셨을 것입니다. 최소한 첫 노드에 예외를 부여하는 상황은 피했으나 후임자가 null임을 확인하는 구현 또한 만족스럽지는 않습니다.

카이로의 코끼리

카이로의 코끼리에 대해 알고 계십니까? 링크를 통해 확인하실 수 있습니다. 꽤 재밌으므로 한번 읽어 보시길 추천합니다. 여기서 중요한 아이디어는 끝 위치에 미리 코끼리를 둔다는 것입니다. 즉, 단일 연결 리스트의 경우엔 끝을 의미하는 센티넬 노드를 두는 것으로 해석할 수 있습니다.

null 노드

null 노드는 전역적으로 사용되는 불변 객체이므로 아래와 같이 생성합니다.

class SinglyLinkedListNullNode<T> implements SinglyLinkedListNode<T> {
    private static nullNode?: SinglyLinkedListNullNode<any>;

    private constructor() {}

    static get(): SinglyLinkedListNullNode<any> {
        if(!this.nullNode) { this.nullNode = new SinglyLinkedListNullNode(); }
        return this.nullNode;
    }

    // ...
}

외부에서 구분하기 위해 아래와 같은 연산을 추가합니다. 이는 null 노드이면 true, 그 외에는 모두 false를 반환합니다.

interface SinglyLinkedList<T> {
    isNull(): boolean;

    // ...
}

null 노드는 그저 종료자 역할만 수행하는 것으로 충분합니다. 일종의 null 오브젝트 패턴의 예로 볼 수 있습니다.

class SinglyLinkedListNullNode<T> implements SinglyLinkedListNode<T> {
    linkBefore(succ: SinglyLinkedListNode<T>): void {

    }

    unlink(pred: SinglyLinkedListNode<T>): void {

    }

    next(): SinglyLinkedListNode<T> {
        return this;
    }

    get(): T {
        throw new ReferenceError("...");
    }

    set(element: T): void {
        throw new ReferenceError("...");
    }

    access(index: number): SinglyLinkedList<T> {
        return this;
    }

    getFirst(): T {
        return this.get();
    }

    setFirst(element: T): void {
        this.set(element);
    }

    insertFirst(element: T): SinglyLinkedList<T> {
        throw new ReferenceError("...");
    }

    deleteFirst(): SinglyLinkedList<T> {
        throw new ReferenceError("...");
    }

    isNull(): boolean {
        return true;
    }

    // ...
}

주의해야 할 점은 null 노드는 길이가 0인 빈 연결 리스트와는 다르다는 점입니다. 명목상 null과 동일하므로 내부에 영향을 미치는 연산은 잘못된 시도입니다. 그러나 그 외의 연산은 아무것도 하지 않을 뿐 허용됩니다. 이것이 null과 유일한 차이점입니다.

이제 기존에 작성한 모든 코드에서 null을 제거할 수 있습니다!

내용은 다음 편에서 이어집니다. 읽어주셔서 감사합니다!

묻고 답하기

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