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

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

null 노드의 도입으로 코드는 한 층 간결해졌습니다. 그럼, 이제 탐색도 마저 구현해 볼까요?

class SinglyLinkedListNodeImpl<T> implements SinglyLinkedListNode<T> {
    search(element: T): SinglyLinkedList<T> {
        let curr: SinglyLinkedListNode<T> = this;
        while(!curr.isNull()) {
            const succ = curr.next();
            if(!succ.isNull() && element === succ.get()) { break; }
            curr = succ;
        }
        return curr;
    }

    // ...
}

유감입니다. 탐색에는 전혀 효과가 없었네요. 그렇다면 이를 어떻게 개선할 수 있을까요?

후임자에게 비교 떠넘기기

interface SinglyLinkedListNode<T> extends SinglyLinkedList<T> {
    is(element: T): boolean;

    // ...
}

약간의 개선을 위해 연산을 추가할 수 있습니다. 위 연산은 노드가 가진 요소와 일치하면 true, 그 외에는 모두 false를 반환합니다. 살짝 느낌이 오시죠?

class SinglyLinkedListNullNode<T> implements SinglyLinkedListNode<T> {
    is(element: T): boolean {
        return false;
    }
}

null 노드는 항상 false를 반환(헤드 노드도 마찬가지)합니다. 요소를 가지고 있지 않으니, 논리적으로 맞지요? 이를 통해 루프 탈출 조건을 다음과 같이 수정할 수 있습니다.

if(succ.is(element)) { break; }

후임자에게 전부 떠넘기기

이 정도도 충분히 좋지만, 노드 curr이 null 노드인지 매번 확인하는 절차가 맘에 들지 않을 수 있습니다. 만약에 그렇게 생각된다면 극한의 떠넘기기를 시도해 볼 수 있습니다.

class SinglyLinkedListNodeImpl<T> implements SinglyLinkedListNode<T> {
    search(element: T): SinglyLinkedList<T> {
        const succ = this.next();
        return succ.is(element) ? this : succ.search(element);
    }

    // ...
}

현재 노드가 즉시 처리할 수 없다면 후임자에게 떠넘기는 방법입니다. 기존 방법과 달리 재귀를 통해 구현됩니다. 코드도 짧고 논리적으로 더 적절합니다. 무엇보다 null 노드인지 확인할 필요가 없습니다.

가볍게 null 노드 시나리오를 생각해 봅시다. 만약 후임자가 null 노드라면 is는 false일 것입니다. 즉, 후임자의 search가 수행됩니다. null 노드의 search는 항상 this를 반환하므로 원하는 대로 null 노드를 반환하게 됩니다.

재귀는 신중히

재귀를 활용하면 더 간결한 코드를 작성할 수 있습니다. 무엇보다 문제를 여러 차례 분할하여 문제를 해결해야 할 경우, 반복에 비해 논리적으로 더 적절한 코드를 작성할 수 있습니다. 그럼에도 재귀를 피해야 하는 이유가 있습니다.

함수는 호출 시 일정 수준의 스택 메모리를 점유합니다. 이는 스택 프레임이라고 하는데 함수의 반환 전까지 유지됩니다. 즉, 재귀 방식으로 함수 호출이 발생하면 재귀 깊이만큼 스택 프레임이 중첩됩니다. 이는 성능에 악영향을 줄 뿐 아니라 심한 경우, 스택 메모리 부족으로 이어질 수 있습니다.

연결 리스트의 탐색 연산의 최대 재귀 깊이는 연결 리스트의 길이와 같습니다. 즉, 최대 깊이는 길이가 1천이라면 1천, 1만이라면 1만입니다. 일반적으로 스택 메모리는 크지 않기 때문에 1천 개 이상의 요소를 취급하는 경우엔 메모리 부족 문제를 염두에 두어야 합니다.

지난 배열 파트에서도 재귀를 활용한 바가 있으나 해당 알고리즘의 시간 복잡도는 \(O(\log{n})\)으로 최대 깊이가 무시할 수 있을 정도로 매우 얕습니다. 배열의 요소 수가 1경 개인 경우에도 최대 깊이는 약 54 정도입니다.

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

묻고 답하기

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