목록(추상 데이터 유형)
List (abstract data type)컴퓨터 과학에서 목록 또는 시퀀스는 한정된 수의 순서 값을 나타내는 추상 데이터 유형으로, 같은 값이 두 번 이상 발생할 수 있습니다.목록의 인스턴스는 튜플 또는 유한 수열의 수학적 개념을 컴퓨터로 표현한 것입니다. 목록의 (잠재적) 무한 아날로그는 [1]: §3.5 스트림입니다.목록은 다른 값을 포함하므로 컨테이너의 기본 예입니다.같은 값이 여러 번 발생하는 경우 각 발생은 개별 항목으로 간주됩니다.
이름 목록은 추상 목록, 특히 연결된 목록 및 배열 구현에 사용할 수 있는 몇 가지 구체적인 데이터 구조에도 사용됩니다.Lisp 프로그래밍과 같은 일부 컨텍스트에서는 목록이라는 용어는 배열이 아닌 링크된 목록을 나타낼 수 있습니다.클래스 기반 프로그래밍에서 목록은 일반적으로 일반적인 "목록" 클래스의 하위 클래스의 인스턴스로 제공되며 별도의 반복자를 통해 전달됩니다.
많은 프로그래밍 언어는 목록 데이터 유형을 지원하며 목록 및 목록 작업을 위한 특별한 구문과 의미를 가집니다.목록은 종종 쉼표, 세미콜론 및/또는 공백으로 구분된 항목을 괄호 '()', 대괄호 '[], 대괄호 '{}', 또는 대괄호 '<>'와 같은 딜리미터 쌍으로 작성하여 구성할 수 있습니다.일부 언어에서는 목록 유형을 배열 유형처럼 인덱싱하거나 슬라이스할 수 있습니다. 이 경우 데이터 유형은 배열로 더 정확하게 설명됩니다.
유형 이론과 함수 프로그래밍에서 추상 리스트는 보통 두 가지 연산에 의해 유도적으로 정의된다: 빈 리스트를 생성하는 0과 [2]목록의 선두에 항목을 추가하는 단점.
운용
리스트 데이터 구조를 실장하면, 다음의 조작의 일부를 실현할 수 있습니다.
- 빈 목록을 작성하기 위한 생성자.
- 목록이 비어 있는지 여부를 테스트하는 작업
- 엔티티를 리스트에 추가하는 작업
- 엔티티를 리스트에 추가하는 작업
- 목록의 첫 번째 구성요소(또는 "머리")를 결정하는 작업
- 목록의 첫 번째 구성 요소를 제외한 모든 구성 요소로 구성된 목록을 참조하는 작업(이 작업을 목록의 "꼬리"라고 합니다).
- 특정 인덱스에서 요소에 액세스하는 작업입니다.
실장
목록은 일반적으로 링크된 목록(단일 또는 이중 링크됨) 또는 배열(일반적으로 가변 길이 또는 동적 배열)로 구현됩니다.
프로그래밍 언어 Lisp에서 시작된 목록을 구현하는 표준 방법은 목록의 각 요소에 해당 값과 목록 내 다음 요소의 위치를 나타내는 포인터를 모두 포함시키는 것입니다.그러면 목록에 중첩된 하위 목록이 있는지 여부에 따라 링크된 목록 또는 트리가 생성됩니다.일부 오래된 Lisp 실장(Symbolics 3600의 Lisp 실장 등)에서는 특별한 내부 표현(사용자에게는 보이지 않음)이 있는 "압축 리스트"도 지원되고 있습니다.목록은 반복 또는 재귀를 사용하여 조작할 수 있습니다.전자는 명령형 프로그래밍 언어에서 선호되는 경우가 많은 반면 후자는 함수형 언어에서 표준입니다.
목록은 인덱스-값 쌍을 보유하는 자가 균형 바이너리 검색 트리로 구현될 수 있으며, 모든 요소(예를 들어 가장 오른쪽에 있는 모든 요소, 검색을 안내하기 위해 사용되는 가장 오른쪽의 하위 인덱스를 저장하는 내부 노드)에 동일한 시간 액세스를 제공합니다. 목록 크기에 로그 시간이 걸리지만 크게 변경되지 않는 한, 이 검색 트리는 제공할 수 있습니다.랜덤 액세스의 환상, 스왑, 프리픽스, 추가 조작을 로그 타임으로 실행할 [3]수 있습니다.
프로그래밍 언어 지원
일부 언어에서는 목록 데이터 구조를 제공하지 않지만 목록을 에뮬레이트하기 위해 연관 배열 또는 일종의 테이블을 사용할 수 있습니다.예를 들어, Lua는 테이블을 제공합니다.Lua는 내부적으로 숫자 인덱스가 있는 목록을 배열로 저장하지만 여전히 [4]사전으로 표시됩니다.
Lisp에서 목록은 기본 데이터 유형이며 프로그램 코드와 데이터를 모두 나타낼 수 있습니다.대부분의 방언에서, 처음 세 개의 소수 목록은 다음과 같이 쓰여질 수 있다.(list 2 3 5)스킴을 포함한 리스프의 몇 가지 방언에서 리스트는 한 쌍의 집합으로 다음 쌍(또는 늘 값)에 대한 포인터로 구성되어 하나의 링크 [5]리스트를 만듭니다.
적용들
이름에서 알 수 있듯이 목록을 사용하여 요소 목록을 저장할 수 있습니다.그러나 기존 어레이와 달리 목록은 확장 및 축소될 수 있으며 메모리에 동적으로 저장됩니다.
컴퓨팅에서는 리스트는 세트보다 구현이 용이합니다.수학적 의미의 유한 집합은 추가적인 제한이 있는 목록으로 실현될 수 있습니다. 즉, 중복 요소는 허용되지 않으며 순서는 관련이 없습니다.목록을 정렬하면 지정된 항목이 이미 세트에 있는지 확인하는 속도가 빨라지지만 순서를 확인하려면 목록에 새 항목을 추가하는 데 시간이 더 걸립니다.그러나 효율적인 구현에서는 목록이 아닌 자체 밸런싱 바이너리 검색 트리 또는 해시 테이블을 사용하여 세트가 구현됩니다.
리스트는 큐, 스택 및 그 변형을 포함한 기타 추상 데이터 유형의 기초가 됩니다.
추상적 정의
일부 유형 E(단형 목록) 요소를 포함하는 추상 목록 유형 L은 다음 함수에 의해 정의됩니다.
- 0: () → L
- 단점: E × L → L
- 첫 번째: L → E
- 나머지: L → L
공리와 함께
- first (cons (e, l)) = e
- rest (cons (e, l)) = l
모든 요소 e 및 모든 목록 l에 적용됩니다.은 함축되어 있다
- 단점(e, l) § l
- 단점(e, l) § e
- cons (e1, l1) = cons (e2, l2) e = e1 및2 l = l인2 경우1
첫 번째(nil)와 나머지(nil)는 정의되어 있지 않습니다.
이러한 공리는 추상 스택 데이터 유형의 공리와 동일합니다.
유형 이론에서 위의 정의는 생성자의 관점에서 정의된 귀납적 유형으로 보다 단순하게 간주됩니다: 0과 단점.대수적 용어로, 이것은 변환 1 + E × L → L로 표현될 수 있다. 그리고 나서 먼저 컨스 컨스트럭터에서 패턴을 일치시키고 영 케이스를 별도로 처리함으로써 나머지를 구한다.
리스트 모나드
목록 유형은 다음 함수를 사용하여 모나드를 형성합니다(유형 E의 요소를 가진 단형 목록을 나타내기 위해 L이 아닌 E를* 사용합니다).
여기서 append는 다음과 같이 정의됩니다.
또는 모나드는 다음과 같은 방법으로 운영 복귀, fmap 및 결합의 관점에서 정의할 수 있습니다.
fmap, join, append 및 bind는 각 재귀 호출에서 점진적으로 더 깊은 인수에 적용되기 때문에 잘 정의되어 있습니다.
목록 유형은 가법 모나드이며, 0은 모나드 0으로 추가되며, 추가는 모나드 합으로 지정됩니다.
목록은 추가 작업 아래에 모노이드를 형성합니다.monoid의 identity 요소는 빈 목록, 0입니다.실제로 이것은 일련의 목록 요소 위에 있는 자유 모노이드입니다.
「 」를 참조해 주세요.
레퍼런스
- ^ Abelson, Harold; Sussman, Gerald Jay (1996). Structure and Interpretation of Computer Programs. MIT Press.
- ^ Reingold, Edward; Nievergelt, Jurg; Narsingh, Deo (1977). Combinatorial Algorithms: Theory and Practice. Englewood Cliffs, New Jersey: Prentice Hall. pp. 38–41. ISBN 0-13-152447-X.
- ^ Barnett, Granville; Del tonga, Luca (2008). "Data Structures and Algorithms" (PDF). mta.ca. Retrieved 12 November 2014.
- ^ Lerusalimschy, Roberto (December 2003). Programming in Lua (first edition) (First ed.). Lua.org. ISBN 8590379817. Retrieved 12 November 2014.
- ^ Steele, Guy (1990). Common Lisp (Second ed.). Digital Press. pp. 29–31. ISBN 1-55558-041-6.
