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

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

연결 리스트의 연산은 연결을 통해 진행됩니다. 그렇다면 단일 연결 리스트의 연결은 어떻게 이루어질까요? 매우 간단합니다.

interface SinglyLinkedListNode<T> extends SinglyLinkedList<T> {
    linkBefore(succ: SinglyLinkedListNode<T> | null): void;
    unlink(pred: SinglyLinkedListNode<T>): void;

    next(): SinglyLinkedListNode<T>;

    // ...
}

객체를 언제나 연결 리스트로만 공개하는 것이 좋습니다. 노드로써 활용되는 것은 순전히 구현체 내부로 제한되어야 합니다. 이를 준수하지 않으면 연결 리스트의 구조가 심각하게 훼손될 수 있습니다.

class SinglyLinkedListNodeImpl<T> implements SinglyLinkedListNode<T> {
    private successor: SinglyLinkedListNode<T> | null = null;

    linkBefore(succ: SinglyLinkedListNode<T> | null): void {
        this.successor = succ;
    }

    unlink(pred: SinglyLinkedListNode<T>): void {
        pred.linkBefore(this.next());
        this.successor = null;
    }

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

    // ...
}

위 코드는 연결에 관련된 노드 연산입니다. 연결은 곧 후임자의 참조를 얻는 것을 의미하므로 간단히 linkBefore을 구현할 수 있습니다. 연결을 끊는 것 또한 단순히 선임자와 후임자를 서로 연결하는 것을 의미하므로 구현된 linkBefore을 활용해 간단히 unlink를 구현할 수 있습니다. next는 단순히 후임자를 의미하는 successor를 반환합니다.

적용

class SinglyLinkedListNodeImpl<T> implements SinglyLinkedListNode<T> {
    constructor(private element: T) {}

    access(index: number): SinglyLinkedList<T> | null {
        if(index < 0) { return null; }

        let curr: SinglyLinkedListNode<T> | null = this;
        for(let i = 0; curr !== null && i < index; i++) {
            curr = curr.next();
        }
        return curr;
    }

    insertFirst(element: T): SinglyLinkedList<T> {
        const node = new SinglyLinkedListNodeImpl(element);
        node.linkBefore(this.next());
        this.linkBefore(node);

        return this;

    }

    deleteFirst(): SinglyLinkedList<T> {
        this.next()?.unlink(this);
        return this;
    }

    // ...
}

위 연산은 모두 연결을 활용합니다. 차례대로 설명하겠습니다.

access는 반복 혹은 재귀를 통해 구현할 수 있습니다. 위 코드에서는 재귀를 통해 구현되었습니다.

1. index가 음수라면 즉시 null을 반환. (단일 연결 리스트는 역방향 접근이 불가하므로)

2. index가 양수라면 index만큼 뒤로 이동하며 노드를 선택. (도중 null을 만나면 조기 반환)

3. 최종 선택된 노드를 반환.

insertFirst는 linkBefore을 직접적으로 활용해 간단히 구현할 수 있습니다.

1. 전달받은 요소를 통해 새 노드를 생성.

2. 새 노드를 현재 노드 후임자의 앞부분에 연결.

3. 현재 노드를 새 노드의 앞부분에 연결.

4. this를 반환. (현재 위치의 연결 리스트가 여전히 현재 노드와 동일하므로)

deleteFirst는 unlink를 직접적으로 활용해 마찬가지로 간단히 구현할 수 있습니다.

1. 후임자의 연결을 해제.

2. this를 반환.

흠, 꽤 괜찮네요. 하지만 조금 이상하지 않나요?

단일 연결 리스트의 접근자는 첫 노드?

코드를 유심히 살펴보세요. 눈치채셨나요? 분명 연결 리스트의 접근자는 첫 노드일 텐데 코드상에는 this가 첫 노드의 선임자로 보입니다. 이미 눈치채셨을지 모르겠지만 단일 연결 리스트의 접근자로 첫 노드는 다소 부적절합니다. 첫 노드는 연결 리스트를 이루는 모든 노드에 대해 연산을 수행할 능력이 없기 때문이지요.

생각해 봅시다. 연결 리스트의 0번 요소를 제거하려면 어떻게 해야 할까요? 제거는 선임자와 후임자를 연결하는 것을 의미하므로 선임자의 참조가 필요하다는 것을 알 수 있습니다. 하지만 모든 노드는 후임자의 참조만 유지할 뿐, 선임자의 참조를 유지하지 않습니다. 이것은 역방향 접근이 불가한 이유이기도 합니다. 이 때문에 단일 연결 리스트의 접근자 역할은 첫 노드가 아닌 첫 노드의 선임자가 더 적절합니다.

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

묻고 답하기

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