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

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

이전 편에서는 연결 리스트의 접근자는 첫 노드의 선임자가 적절하다는 것을 알았습니다. 얼핏 보기엔 문제없어 보이는데 어떤가요? 최상위 연결 리스트 즉, 가장 처음에 위치한 노드로 시작하는 경우를 생각해 봅시다. 가장 처음에 위치한 노드의 선임자는 무엇인가요? 맞습니다. 선임자가 존재하지 않겠지요. 그럼 어떻게 해야 할까요? 선임자를 가지지 않는 첫 노드를 갖는 연결 리스트에 대해 예외를 적용해야 할까요? 이는 가능하지만 조금 지저분합니다.

센티넬 노드

센티넬 노드란 알고리즘을 단순화하기 위해 사용하는 특별한 노드입니다. 예를 들어, 지금의경우엔 맨 처음에 항상 특별한 노드를 두어 단일 연결 리스트의 구조적 일관성을 유지할 수 있습니다. 이러한 용도로 사용되는 센티넬 노드를 헤드 노드라 부릅니다.

헤드 노드

interface SinglyLinkedListNode<T> extends SinglyLinkedList<T> {
    get(): T;
    set(element: T): void;

    // ...
}

class SinglyLinkedListHeadNode<T> implements SinglyLinkedListNode<T> {
    get(): T {
        throw new ReferenceError("...");
    }

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

    // ...
}

class SinglyLinkedListNodeImpl<T> implements SinglyLinkedListNode<T> {
    get(): T {
        return this.element;
    }

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

    // ...
}

일반 노드는 요소를 저장하고 관리하는 데 반해 헤드 노드는 그렇지 않습니다. 이는 요소를 저장하지 않습니다. 하지만 이는 전혀 문제가 되지 않습니다. 이러한 일은 일어나지 않기 때문이지요. 왜일까요? 맞습니다. 앞서 정의한 단일 연결 리스트의 연산인 getFirst와 setFirst는 모든 후임자를 대상으로 하기 때문입니다. 어떠한 노드의 후임자도 아닌 헤드 노드와는 인연이 없는 이야기입니다.

class SinglyLinkedListHeadNode<T> implements SinglyLinkedListNode<T> {
    getFirst(): T {
        const succ = this.next();
        return succ ? succ.get() : this.get();
    }

    setFirst(element: T): void {
        const succ = this.next();
        succ ? succ.set(element) : this.set(element);
    }

    // ...
}

class SinglyLinkedListNodeImpl<T> implements SinglyLinkedListNode<T> {
    getFirst(): T {
        const succ = this.next();
        if(!succ) { throw new ReferenceError("..."); }
        return succ.get();
    }

    setFirst(element: T): void {
        const succ = this.next();
        if(!succ) { throw new ReferenceError("..."); }
        succ.set(element);
    }

    // ...
}

길이가 0인 빈 단일 연결 리스트 즉, 첫 노드의 후임자가 없는 경우, 두 연산은 잘못된 접근입니다. 따라서 헤드 노드와 일반 노드 모두 예외를 던집니다.

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

묻고 답하기

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