[자료구조] 컬렉션

컬렉션(collection)이란 데이터(요소)를 그룹화한 것으로 추상 자료형(ADT, abstract data type)을 의미하며, 자료 구조의 구체적인 구현을 규정 짓지는 않는다. 일반적으로 컬렉션의 예로는 리스트(list), 셋(set), 큐(queue), 스택(stack), 맵(map), 트리(tree) 등이 있다. 컬렉션의 추상적인 개념에 대한 구체적인 구현(자료 구조의 동작 방식, 구현체 용어 등)은 프로그래밍 언어마다 다를 수 있다.

컬렉션의 종류는 다음과 같다.

• 선형 컬렉션 (linear collection): 데이터를 순서대로 저장하는 컬렉션이다. 한쪽 끝 또는 양쪽 끝에서 데이터가 저장된 순서대로 데이터에 접근할 수 있다. 구현에 따라 선형 구조 대신 트리와 같은 다른 구조가 사용될 수도 있다.
• 연관 컬렉션 (associative collection): 입력에 따른 출력을 반환하는 함수에 의해 연관 관계를 갖는 키와 값을 저장하는 컬렉션이다. 키만을 저장하거나 키와 값을 저장하는 자료 구조 모두 연관 컬렉션에 속한다.
• 그래프 (graph): 노드(node)와 간선(edge)의 집합으로 구성되는 그래프 자료 구조를 의미하는 컬렉션이다. 트리(tree)는 그래프 자료 구조의 하위 개념으로, 순환 구조를 갖지 않는다. 선형 컬렉션에서 데이터에 대한 탐색(또는 순회(traverse))은 비교적 간단하지만 트리 데이터 구조에 대한 탐색은 보다 복잡한 알고리즘(깊이 우선 탐색, 너비 우선 탐색 등)을 필요로 한다.

선형 컬렉션의 예는 다음과 같다.

• 리스트 (list): 순서대로 데이터를 저장하는 선형 자료 구조이다. 데이터의 중복을 허용한다. 서로 다른 타입의 데이터를 저장할 수 있으며 크기가 고정되어 있지 않다. 리스트는 큐, 스택, 연결 리스트, 배열과 같은 선형 자료 구조의 기본을 의미하기도 한다. 프로그래밍 언어에 따라 리스트 자체에 대한 타입 정의가 제공되지 않을 수도 있다.
• 배열 (array): 크기가 고정되어 있으며 서로 동일한 타입의 데이터만 저장 가능한 자료 구조이다. 정적(static) 배열이라고도 한다. 크기가 고정되어 있기 때문에 한 번 생성된 배열은 크기를 변경할 수 없다. 기본적으로 배열은 데이터가 메모리에 물리적인 순서대로 저장되는 인접(contiguous) 배열을 의미한다. 대부분의 경우 서로 인접한 메모리 주소에 접근하는 것은 분산된 주소에 접근하는 것보다 빠르므로 탐색 시 배열은 연결 리스트 보다 연산 속도가 빠르다. 배열은 연속된 메모리 공간에 데이터를 저장하기 때문에 중간에 데이터를 삽입할 경우 해당 위치 이후의 모든 데이터를 한 칸씩 뒤로 이동시켜야 한다.
• 동적 배열 (dynamic array): 배열과 달리 크기가 고정되어 있지 않은 배열 자료 구조이다. 데이터의 크기에 따라 메모리 재할당(re-allocation)이 일어나며 배열의 크기가 자동으로 증가 또는 감소한다. 배열의 크기 조정 작업은 새로운 배열을 위해 메모리를 할당하고 원래 배열에서 데이터를 복사하며 비용이 많이 들지만 정적 배열과 달리 초기에 크기를 지정할 필요가 없으며 메모리를 보다 효율적으로 사용한다는 장점이 있다.
• 큐 (queue): 선입선출(first-in-first-out, FIFO)의 특성을 갖는 선형 자료 구조이다.
  • 우선순위 큐 (priority queue): 데이터에 우선순위가 존재하는 큐 자료 구조이다. 우선순위 큐에서 데이터는 선입선출 규칙 대신 정해진 우선순위에 따라 제공되며 우선순위가 높은 데이터가 우선순위가 낮은 데이터보다 먼저 제공된다. 우선순위의 기준(큰 값을 가진 데이터가 높은 우선순위, 작은 값을 가진 데이터가 높은 우선순위 등)은 구현체 마다 다를 수 있다. 트리 구조의 하나인 힙(heap)은 우선순위 큐 구현에 사용되는 자료 구조이다.
• 스택 (stack): 후입선출(last-in-first-out, LIFO)의 특성을 갖는 선형 자료 구조이다.
• 연결 리스트 (linked list): 데이터를 메모리에 물리적인 순서대로 저장하지 않는 연결(link) 방식의 선형 자료 구조이다. 연결 방식에서는 데이터를 구조체로 묶어서 포인터로 연결한다. 배열의 경우 데이터를 메모리에 물리적인 순서대로 저장한다. 연결 리스트에 저장되는 데이터를 노드(node)라고 한다. 연결 리스트는 연속된 메모리 공간에 데이터를 저장하지 않기 때문에 중간에 데이터를 삽입하더라도 해당 위치 이후의 모든 데이터를 이동시킬 필요가 없으며 기존 두 노드의 연결을 끊고 새로운 노드와 기존 두 노드를 연결시키면 된다.
  • 단일 연결 리스트 (singly-linked list): 데이터의 삽입 및 삭제가 단방향으로만 가능한 연결 리스트이다. 노드는 다음 노드에 대한 참조만 가지고 있다. 따라서 노드 탐색 시 다음 노드 탐색은 빠르게 수행되지만 이전 노드 탐색에 시간이 소요된다.
  • 이중 연결 리스트 (doubly-linked list): 데이터의 삽입 및 삭제가 양방향으로 가능한 연결 리스트이다. 노드는 이전 노드와 다음 노드에 대한 참조를 모두 가지고 있다. 따라서 노드 탐색 시 이전 노드와 다음 노드 탐색이 빠르게 수행된다.

연관 컬렉션의 예는 다음과 같다.

• 셋 (set): 리스트와 유사하지만 중복을 허용하지 않는 자료 구조이다. 정렬 여부에 따라 비정렬 셋과(unordered set)과 정렬 셋(ordered set)으로 구분할 수 있다. 셋은 키만을 저장하는 연관 컬렉션이다. 셋은 다양한 자료 구조를 사용하여 구현할 수 있으며 구현체 별로 시간 및 공간 복잡도가 다르다. 비정렬 셋의 가장 간단한 구현은 리스트를 사용하여 값이 반복되지 않도록 하는 것이다. 리스트 대신 보다 효율적인 연관 배열을 사용하여 구현할 수도 있다. 정렬 셋은 트리를 사용하여 구현한다.
• 멀티셋 (multiset): 셋과 마찬가지로 데이터의 순서는 중요하지 않지만 중복 데이터가 허용되는 자료 구조이다.
• 연관 배열 (associative array): 연관 배열은 키와 키에 대한 값을 매핑하는(연관 짓는) 자료 구조이다. 맵(map), 딕셔너리(dictionary) 등으로 표현하는 자료 구조가 연관 배열에 속한다. 연관 배열은 셋과는 달리 키와 키에 대한 값을 모두 저장하는 연관 컬렉션이다. 연관 배열의 대표적인 구현체로는 해시 테이블(hash table)이 있다. 해시 테이블은 해시 함수(hash function)를 사용하여 키에 대한 값을 결정함으로써 컬렉션 내에 데이터를 분산시킨다. 해시 함수(hash function)의 효율(해시 함수가 데이터를 버킷(bucket)에 얼마나 골고루 분산시키는지)에 따라 연산의 성능이 달라진다. 해시 함수가 여러 데이터를 하나의 키로 해싱하여 해시 충돌(hash collision)이 발생한다면 연산 성능이 저하된다. 서로 다른 키 값이 서로 다른 해시값으로 매핑될 경우 연관 배열 조회에 걸리는 시간은 상수 시간이 되지만 여러 개의 서로 다른 키 값이 동일한 해시값으로 매핑될 경우 성능이 저하된다. 기본적으로 연관 배열은 입력 순서를 보장하지 않지만 순서를 유지하는 구현체도 존재한다.

그래프의 예는 다음과 같다.

• 트리 (tree): 부모(parent)와 자식(child) 관계로 구성되는 계층적인 구조를 갖는 그래프 자료 구조이다. 트리는 무향 그래프(undirected graph)에 속하며 사이클(cycle)이 존재하지 않는 비순환(acyclic) 구조이다. 트리에서 모든 노드는 단 하나의 부모 노드를 갖는다. 트리는 노드 간에 단일 연결성(single connectivity)을 가지므로(부모 노드가 자식 노드를 가리킴) 임의의 두 노드 간에는 단 하나의 경로(path)만 존재한다. 부모 노드가 두 개 이상인 노드가 존재하는 경우, 순환 구조를 갖는 노드가 존재하는 경우, 루트 노드가 두 개 이상인 경우 해당 그래프는 트리가 아니다.

자료 구조 별 시간 복잡도 비교

• 배열
  • 인덱싱 접근: O(1)
  • 탐색: O(N)
  • 삽입/삭제
    • 처음에 삽입/첫 데이터 삭제: O(N)
    • 중간에 삽입/중간 데이터 삭제: O(N)
    • 마지막에 삽입/마지막 데이터 삭제: O(1)
• 동적 배열
  • 인덱싱 접근: O(1)
  • 탐색: O(N)
  • 삽입/삭제
    • 처음에 삽입/첫 데이터 삭제: O(N)
    • 중간에 삽입/중간 데이터 삭제: O(N)
    • 마지막에 삽입/마지막 데이터 삭제
      • 일반적인 경우: O(1) (분할 상환 분석)
      • 최악의 경우: O(N) (새로운 배열에 기존 데이터를 복사하는 작업이 필요한 경우)
• 단일 연결 리스트
  • 인덱싱 접근: O(N)
  • 탐색: O(N)
  • 삽입/삭제
    • 처음에 삽입/첫 노드 삭제: O(1)
    • 중간에 삽입/중간 노드 삭제: O(N) (탐색) + O(1) (삽입/삭제) -> 주어진 노드의 이전 노드를 가져올 수 없으므로 주어진 노드를 삽입/삭제하기 전에 이전 노드를 찾아야 한다.
    • 마지막에 삽입/마지막 노드 삭제: O(N) (탐색) + O(1) (삽입/삭제)
• 이중 연결 리스트
  • 인덱싱 접근: O(N)
  • 탐색: O(N)
  • 삽입/삭제
    • 처음에 삽입/첫 노드 삭제: O(1)
    • 중간에 삽입/중간 노드 삭제: O(1)
    • 마지막에 삽입/마지막 노드 삭제: O(1) (마지막 노드에 대한 참조를 알고 있는 경우)
• 비정렬 셋 (연관 배열을 사용한 구현체)
  • 인덱싱 접근: O(1)
  • 탐색/삽입/삭제
    • 일반적인 경우: O(1)
    • 최악의 경우: O(N) (해시 함수가 모든 데이터를 하나의 키로 해싱하는 경우)
• 정렬 셋 (트리를 사용한 구현체)
  • 인덱싱 접근: O(1)
  • 탐색/삽입/삭제
    • 일반적인 경우: O(log2N)
    • 최악의 경우: O(N)
• 연관 배열
  • 탐색/삽입/삭제
    • 일반적인 경우: O(1)
    • 최악의 경우: O(N) (해시 함수가 모든 데이터를 하나의 키로 해싱하는 경우)
• 트리
  • 이진 탐색 트리
    • 탐색
      • 최선의 경우: O(1) (루트 노드인 경우)
      • 일반적인 경우: O(log2N) (균형 트리인 경우)
      • 최악의 경우: O(N) = O(H) (노드가 한 방향으로 치중되었으면서 노드가 가장 마지막 레벨에 위치한 경우)
    • 삽입
      • 최선의 경우: O(1) (노드가 한 방향으로 치중되었으면서 치중된 방향의 반대 방향에 노드를 삽입해야 하는 경우)
      • 일반적인 경우: O(log2N) (균형 트리인 경우)
      • 최악의 경우: O(N) = O(H) (노드가 한 방향으로 치중되었으면서 노드를 가장 마지막 레벨에 삽입해야 하는 경우)
    • 삭제
      • 최선의 경우: O(1) (리프 노드인 경우)
      • 일반적인 경우: O(log2N) (균형 트리인 경우)
      • 최악의 경우: O(N) = O(H) (노드가 한 방향으로 치중되었으면서 노드의 가장 마지막 레벨을 삭제해야 하는 경우)

참고

• https://www.databricks.com/glossary/hash-buckets
• https://leetcode.com/explore/learn/card/linked-list/213/conclusion/1230/
• https://www.baeldung.com/cs/inserting-complexity-binary-search-tree
• Introduction to Algorithms, 3rd Edition (Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.)