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

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

연결 리스트에는 여러 가지 변형이 있습니다. 그중 가장 기본적인 형태인 단일 연결 리스트의 연산에 대해 알아봅니다. 단일 연결 리스트에 대한 설명은 이전 편에 언급된 연결 리스트의 설명으로 충분할 것으로 보입니다. 연결 리스트는 노드라는 단위로 이루어져 있고, 이는 요소와 다음 노드에 대한 참조를 가지고 있습니다.

연산의 종류

interface SinglyLinkedList<T> {
    access(index: number): SinglyLinkedList<T> | null;

    getFirst(): T;
    setFirst(element: T): void;

    insertFirst(element: T): SinglyLinkedList<T>;
    deleteFirst(): SinglyLinkedList<T>;

    search(element: T): SinglyLinkedList<T> | null;
}

연결 리스트의 기본적인 연산은 위와 같습니다. 배열 파트에서 다뤘던 연산과 유사합니다. 접근해서 읽거나 쓸 수 있고, 요소를 삽입하거나 삭제할 수 있으며, 원하는 요소를 탐색할 수 있습니다. 그러나 연산의 형태가 조금 다르지요? 이에 대해 알아보겠습니다.

access는 특정 위치에 대한 접근을 의미합니다. 배열과는 다르게 접근 연산이 다른 연산과 분리되어 있습니다. 임의 접근을 통해 빠른 접근이 가능한 배열과는 달리 연결 리스트의 접근은 부담이 큰 편에 속하기에 분리하는 것이 유리합니다. 이 연산은 요청 위치에 위치한 연결 리스트를 반환하며, 부적절한 위치에 접근 시 null을 반환합니다. 노드가 아닌 연결 리스트를 반환하는 것에 대해서는 후술하겠습니다.

get, set, insert, delete는 배열에서 의미와 동일합니다. 다만, 어미에 First가 붙은 이유는 현재 연결 리스트를 기준으로 첫 위치에 대해 적용됨을 나타냅니다.

search도 배열에서 의미와 동일합니다. 다만, 인덱스가 아닌 요소가 저장된 위치의 연결 리스트를 반환합니다. 존재하지 않으면 null을 반환합니다.

노드 === 연결 리스트

배열과 연결 리스트가 공유하는 부분이 있습니다. access와 search는 모두 접근자를 반환한다는 것입니다. 배열의 경우는 인덱스이고, 연결 리스트의 경우에는 해당 위치(실은 조금 다르지만)의 노드일 것입니다. 흠, 그런데 조금 이상합니다. 왜 노드가 아닌 연결 리스트를 반환할까요? 여기에는 약간의 추상화가 있습니다.

연결 리스트에서 노드라는 것이 우리에게 가져다주는 실질적인 의미는 무엇일까요? 즉, 노드를 통해 무엇을 할 수 있을까요? 노드는 해당 위치의 요소에 대한 접근자입니다. 동시에 연결 리스트에 대한 접근자입니다. 즉, 노드는 뒤에 연결된 모든 노드로 이루어진 목록에 대한 접근자이기도 하다는 의미입니다. 이는 특정 노드로부터 뒤에 연결된 모든 노드에 대한 접근이 가능하기 때문입니다. 따라서 노드를 연결 리스트로 추상화하여 반환할 수 있다는 의미가 됩니다.

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

묻고 답하기

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