수집(추상 데이터 유형)
Collection (abstract data type)컴퓨터 프로그래밍에서 컬렉션은 해결 중인 문제에 대해 어느 정도 공통의 중요성을 가지며 제어된 방식으로 함께 작동해야 하는 몇 가지 가변 데이터 항목(아마도 0개)의 그룹입니다.일반적으로 데이터 항목은 동일한 유형이거나 상속을 지원하는 언어에서는 일부 공통 상위 유형에서 파생됩니다.수집은 추상 데이터 유형에 적용할 수 있는 개념이며, 구체적인 데이터 구조로서 구체적인 구현을 규정하지는 않습니다(종류 이론에 대한 설명은 컨테이너 참조).
컬렉션의 예로는 리스트, 세트, 멀티셋, 트리, 그래프 등이 있습니다.
고정 크기 배열(또는 테이블)은 일반적으로 수집 구현에서 역할을 하지만 고정 개수의 데이터 항목을 보유하고 있기 때문에 일반적으로 수집으로 간주되지 않습니다.일반적으로 가변 크기 배열은 [citation needed]집합으로 간주됩니다.
선형 컬렉션
많은 컬렉션에서 특정 선형 순서를 정의하며, 한쪽 끝 또는 양쪽 끝에 액세스할 수 있습니다.이러한 수집을 구현하는 실제 데이터 구조는 선형일 필요는 없습니다.예를 들어 priority 큐는 종종 일종의 트리인 힙으로 구현됩니다.중요한 선형 수집에는 다음이 포함됩니다.
리스트
목록에서 데이터 항목의 순서는 유의합니다.중복된 데이터 항목은 허용됩니다.리스트에서의 조작의 예로는 리스트내의 데이터 아이템의 검색과 그 위치 결정(존재하는 경우), 리스트로부터 데이터 아이템의 삭제, 특정의 장소의 리스트에 데이터 아이템의 추가등이 있습니다.리스트의 주요 조작이 한쪽 끝에서 데이터 아이템을 추가하고 다른 한쪽 끝에서 데이터 아이템을 삭제하는 경우 일반적으로 큐 또는 FIFO라고 불립니다.주요 작업이 한쪽 끝에만 데이터 항목을 추가하고 제거하는 것이라면 스택 또는 LIFO라고 합니다.두 경우 모두 데이터 항목은 컬렉션 내에서 동일한 순서로 유지되므로(다른 곳에 제거했다가 다시 삽입하지 않는 한), 이는 목록 수집의 특수한 경우입니다.목록에 대한 다른 전문 작업으로는 데이터 항목의 순서가 매우 중요한 정렬이 있습니다.
스택
스택은 컬렉션의 "위"에 요소를 추가하는 push와 상위 요소를 제거하는 pop이라는 두 가지 주요 연산이 있는 LIFO 데이터 구조입니다.
큐
priority 큐
priority 큐에서는 수집 중 최소 또는 최대 데이터 항목의 트랙이 어떤 순서 기준에 따라 유지되며 다른 데이터 항목의 순서는 중요하지 않다.priority 큐는 항상 선두에 최소 또는 최대를 유지하고 나머지 요소는 가방에 보관하는 목록이라고 생각할 수 있습니다.
더블 엔드 큐
이중 엔드 priority 큐
관련 컬렉션
대신 다른 컬렉션은 일종의 함수로 해석될 수 있습니다. 즉, 입력이 주어지면 컬렉션은 출력을 생성합니다.중요한 관련 컬렉션은 다음과 같습니다.
세트는 인디케이터 함수로 표현되는 세트를 고려하여 가능한 값을 제한함으로써 특수한 멀티셋으로 해석할 수 있습니다.이러한 멀티셋은 각각의 경우에 특화된 어소시에이션 어레이가 됩니다.
놓다
집합에서 데이터 항목의 순서는 중요하지 않지만(또는 정의되지 않음) 중복 데이터 항목은 허용되지 않습니다.세트에 대한 연산의 예로는 데이터 항목의 추가 및 제거, 세트 내의 데이터 항목 검색 등이 있습니다.일부 언어는 세트를 직접 지원합니다.또, 더미 값을 가지는 해시 테이블로 세트를 실장할 수도 있습니다.키만 세트를 나타내는 데 사용됩니다.
멀티셋
멀티셋(또는 가방)에서는 세트와 마찬가지로 데이터 항목의 순서는 중요하지 않지만 이 경우 중복 데이터 항목은 허용됩니다.멀티셋에 대한 연산의 예로는 데이터 항목의 추가 및 제거, 멀티셋에 존재하는 특정 데이터 항목의 중복 수 결정 등이 있습니다.멀티셋은 정렬 동작에 의해 목록으로 변환할 수 있습니다.
어소시에이션 어레이
사전과 같이 연관 배열(또는 지도, 사전, 룩업 테이블)에서 키(단어 등)에 대한 룩업은 값(정의 등)을 제공합니다.이 값은 복합 데이터 구조에 대한 참조일 수 있습니다.해시 테이블은 일반적으로 효율적인 구현이므로 이러한 데이터 유형을 "해시"라고 합니다.
그래프
그래프에서 데이터 항목은 컬렉션 내의 하나 이상의 다른 데이터 항목과 관련성을 가지며 루트 또는 부모-자녀 관계의 개념이 없는 나무와 비슷하므로 모든 데이터 항목이 피어입니다.그래프 작업의 예로는 특정 속성을 찾는 데이터 항목의 연결을 탐색하는 통과 및 검색이 있습니다.그래프는 실제 상황을 모델링하고 관련 문제를 해결하기 위해 자주 사용됩니다.예를 들어 스패닝트리 프로토콜은 데이터 네트워크의 그래프(또는 메쉬) 표현을 생성하여 스위칭노드를 트리로 변환하기 위해 어떤 어소시에이션을 끊어야 하는지 파악하여 데이터가 루프로 돌아가는 것을 방지합니다.
나무들
특별한 종류의 그래프인 트리에서 루트 데이터 항목은 부모-자녀 관계로 자주 간주되는 다른 데이터 항목 중 몇 가지와 연관된 데이터 항목을 몇 개 가지고 있다.모든 데이터 항목(루트 제외)에는 단일 상위 항목(루트에는 상위 항목이 없음)과 일부 하위 항목(경우에 따라서는 0)이 있습니다.트리 조작의 예로는 정렬 등을 수행하기 위한 트리의 특정 특성을 유지하기 위한 데이터 항목의 추가와 특정 순서로 데이터 항목을 방문하기 위한 트래버스가 있다.
트리 컬렉션은 계층형 데이터를 자연스럽게 저장하기 위해 사용할 수 있습니다. 계층형 데이터는 데이터 스토리지 시스템의 디렉토리에 있는 메뉴 시스템 및 파일과 같은 트리 형태로 표시됩니다.
특수 트리는 다양한 알고리즘에 사용됩니다.예를 들어 힙 정렬에서는 힙이라고 하는 일종의 트리가 사용됩니다.
추상 개념과 구현
여기서 설명한 바와 같이 컬렉션과 다양한 종류의 컬렉션은 추상적인 개념이다.문헌에는 컴퓨터 과학의 추상적 개념과 다양한 언어 또는 종류의 언어에서의 구체적인 구현 사이에 상당한 혼란이 존재한다.목록, 집합, 트리 등과 같은 집합이 데이터 구조, 추상 데이터 유형 또는 클래스라는 주장은 이를 염두에 두고 읽어야 합니다.컬렉션은 컴퓨팅 문제에 대한 솔루션을 공식화할 때 가장 유용한 추상화입니다.이러한 관점에서 볼 때, 그것들은 구현에 초점을 맞추면 상실될 수 있는 기본적인 수학적 개념에 대한 중요한 연결을 유지한다.
예를 들어 priority 큐는 종종 힙으로 구현되는 반면, 관련 배열은 종종 해시 테이블로 구현되기 때문에 이러한 추상 유형은 엄밀하게는 정확하지 않지만 선호되는 구현에 의해 종종 "히프" 또는 "해시"라고 불립니다.
실장
일부 컬렉션은 목록과 같은 언어의 원시 데이터 유형일 수 있지만, 더 복잡한 컬렉션은 라이브러리, 때로는 표준 라이브러리에서 복합 데이터 유형으로 구현됩니다.예를 들어 다음과 같습니다.
- C++: C++ 표준 라이브러리 및 이전 표준 템플릿 라이브러리에 구현된 "컨테이너"
- Java: Java 컬렉션 프레임워크에 구현
- Oracle PL/SQL은 컬렉션을 프로그래머 정의[1] 유형으로 구현합니다.
- Python: 일부 빌트인, 기타는 컬렉션 라이브러리에 구현되어 있습니다.
레퍼런스
- ^ Feuerstein, Steven; Pribyl, Bill; Dawes, Chip (2007) [1999]. "Collections in PL/SQL". Oracle PL/SQL Language Pocket Reference. Pocket Reference (4 ed.). Sebastopol, California: O'Reilly Media, Inc. p. 63. ISBN 9780596551612. Retrieved 2017-06-26.
Collections are implemented as TYPEs. As with any programmer-defined type, you must first define the type; then you can declare instances of that type.
외부 링크
- Apache Commons 컬렉션.
- AS3Commons Collections Framework ActionScript3의 가장 일반적인 컬렉션 구현.
- CollectionSpy : Java의 Collections Framework용 프로파일러입니다.
- 구아바.
- 망고 자바 라이브러리