리스트 (컴퓨팅)

컴퓨터 과학에서 리스트(영어: list) 또는 시퀀스(영어: sequence)는 유한한 개수와 특정 순서를 가진 항목들의 컬렉션이다. 리스트의 인스턴스는 수학적 개념인 튜플 또는 유한 수열의 컴퓨터 표현이다.

리스트는 동일한 값을 두 번 이상 포함할 수 있으며, 각 발생은 별개의 항목으로 간주된다.

세 개의 정수 요소를 가진 리스트를 구현하는 단일 연결 리스트 구조.

리스트라는 용어는 추상 리스트를 구현하는 데 사용될 수 있는 여러 구체적인 자료 구조, 특히 연결 리스트와 배열에도 사용된다. 리스프 프로그래밍과 같은 일부 맥락에서, 리스트라는 용어는 배열보다는 특정하게 연결 리스트를 지칭할 수 있다. 클래스 기반 프로그래밍에서, 리스트는 일반적으로 일반 "리스트" 클래스의 하위 클래스 인스턴스로 제공되며, 별도의 이터레이터를 통해 순회된다.

많은 프로그래밍 언어는 리스트 자료형에 대한 지원을 제공하며, 리스트와 리스트 연산을 위한 특별한 구문과 의미론을 가지고 있다. 리스트는 종종 괄호 '()', 대괄호 '[]', 중괄호 '{}' 또는 꺾쇠괄호 '<>'와 같은 구분 기호 쌍 안에 쉼표, 세미콜론 및 공백으로 구분하여 항목을 순서대로 작성하여 구성할 수 있다. 일부 언어는 리스트 유형이 인덱스되거나 슬라이스될 수 있도록 허용할 수 있으며, 이 경우 자료형은 더욱 정확하게 배열로 설명된다.

유형 이론 및 함수형 프로그래밍에서, 추상 리스트는 일반적으로 두 가지 연산에 의해 귀납적으로 정의된다: 빈 리스트를 생성하는 nil과 리스트의 시작 부분에 항목을 추가하는 cons.

스트림은 리스트의 잠재적으로 무한한 아날로그이다.

연산

리스트 자료 구조의 구현은 다음 연산 중 일부를 제공할 수 있다:

• 생성
• 비어 있는지 테스트
• 시작 또는 끝에 항목 추가
• 첫 번째 또는 마지막 항목 접근
• 인덱스로 항목 접근

구현

리스트는 일반적으로 연결 리스트(단일 또는 이중 연결) 또는 배열 (일반적으로 가변 길이 또는 동적 배열)로 구현된다.

리스프 프로그래밍 언어에서 유래한 리스트를 구현하는 표준 방법은 리스트의 각 요소가 값과 리스트의 다음 요소 위치를 나타내는 포인터를 모두 포함하도록 하는 것이다. 이는 리스트에 중첩된 하위 리스트가 있는지 여부에 따라 연결 리스트 또는 트리를 생성한다. 일부 구형 리스프 구현(예: 심볼릭스 3600의 리스프 구현)은 특수한 내부 표현(사용자에게는 보이지 않음)을 가진 "압축된 리스트"(CDR 코딩)도 지원했다. 리스트는 반복 또는 재귀를 사용하여 조작할 수 있다. 전자는 명령형 프로그래밍 언어에서 종종 선호되는 반면, 후자는 함수형 언어에서 일반적이다.

리스트는 인덱스-값 쌍을 저장하는 자가 균형 이진 탐색 트리로 구현될 수 있으며, 모든 요소에 대한 동일 시간 접근(예: 모두 리프에 위치하고, 내부 노드는 탐색을 안내하는 데 사용되는 가장 오른쪽 자식의 인덱스를 저장)을 제공하여 리스트 크기에 로그 시간의 시간이 걸리지만, 크게 변경되지 않는 한 임의 접근의 환상을 제공하고 로그 시간에 스왑, 접두사 및 추가 연산을 가능하게 한다.

프로그래밍 언어 지원

일부 컴퓨터 언어는 리스트 자료 구조를 제공하지 않지만, 연관 배열 또는 일종의 테이블을 사용하여 리스트를 에뮬레이트하는 것을 제공한다. 예를 들어, 루아는 테이블을 제공한다. 루아는 내부적으로 숫자 인덱스를 가진 리스트를 배열로 저장하지만, 여전히 사전으로 나타난다.

리스프에서 리스트는 기본 자료형이며 프로그램 코드와 데이터를 모두 나타낼 수 있다. 대부분의 방언에서 처음 세 소수의 리스트는 (list 2 3 5)로 작성될 수 있다. 스킴을 포함한 리스프의 여러 방언에서, 리스트는 값과 다음 쌍(또는 널 값)에 대한 포인터로 구성된 쌍들의 컬렉션으로, 단일 연결 리스트를 형성한다.

응용

배열과는 달리 리스트는 확장 및 축소될 수 있다.

컴퓨팅에서 리스트는 집합보다 구현하기 쉽다. 수학적 의미의 유한 집합은 추가 제약이 있는 리스트로 구현될 수 있다. 즉, 중복 요소는 허용되지 않고 순서는 무관하다. 리스트를 정렬하면 주어진 항목이 이미 집합에 있는지 확인하는 속도가 빨라지지만, 순서를 보장하기 위해서는 새 항목을 리스트에 추가하는 데 더 많은 시간이 필요하다. 그러나 효율적인 구현에서는 집합이 리스트 대신 자가 균형 이진 탐색 트리 또는 해시 테이블을 사용하여 구현된다.

리스트는 또한 큐, 스택, 그리고 그 변형을 포함한 다른 추상 자료형의 기초를 형성한다.

추상적 정의

일부 유형 E의 요소를 가진 추상 리스트 유형 L(모노모픽 리스트)은 다음 함수로 정의된다:

nil: () → L

cons: E × L → L

first: L → E

rest: L → L

다음 공리들과 함께

first (cons (e, l)) = e

rest (cons (e, l)) = l

모든 요소 e와 모든 리스트 l에 대해. 다음이 암시적으로 적용된다.

cons (e, l) ≠ l

cons (e, l) ≠ e

cons (e₁, l₁) = cons (e₂, l₂) if e₁ = e₂ and l₁ = l₂

first (nil ())과 rest (nil ())는 정의되지 않는다.

이 공리들은 추상 스택 자료형의 공리들과 동등하다.

유형 이론에서 위의 정의는 nil과 cons 생성자를 사용하여 정의된 귀납적 타입으로 더 간단하게 간주된다. 대수적으로 이것은 변환 1 + E × L → L로 나타낼 수 있다. first와 rest는 cons 생성자에 대한 패턴 매칭과 nil 사례를 별도로 처리하여 얻어진다.

리스트 모나드

리스트 유형은 다음 함수를 사용하여 모나드를 형성한다 (유형 E의 요소를 가진 모노모픽 리스트를 나타내기 위해 L 대신 E^* 사용):

${\text{return}}\colon A\to A^{*}=a\mapsto {\text{cons}}\,a\,{\text{nil}}$

${\text{bind}}\colon A^{*}\to (A\to B^{*})\to B^{*}=l\mapsto f\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,(f\,a)\,({\text{bind}}\,l'\,f)&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

여기서 append는 다음과 같이 정의된다:

${\text{append}}\colon A^{*}\to A^{*}\to A^{*}=l_{1}\mapsto l_{2}\mapsto {\begin{cases}l_{2}&{\text{if}}\ l_{1}={\text{nil}}\\{\text{cons}}\,a\,({\text{append}}\,l_{1}'\,l_{2})&{\text{if}}\ l_{1}={\text{cons}}\,a\,l_{1}'\end{cases}}$

또는 모나드는 return, fmap 및 join 연산으로 정의될 수 있으며:

${\text{fmap}}\colon (A\to B)\to (A^{*}\to B^{*})=f\mapsto l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{cons}}\,(f\,a)({\text{fmap}}f\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

${\text{join}}\colon {A^{*}}^{*}\to A^{*}=l\mapsto {\begin{cases}{\text{nil}}&{\text{if}}\ l={\text{nil}}\\{\text{append}}\,a\,({\text{join}}\,l')&{\text{if}}\ l={\text{cons}}\,a\,l'\end{cases}}$

fmap, join, append 및 bind는 각 재귀 호출에서 점진적으로 더 깊은 인수에 적용되므로 잘 정의된다.

리스트 유형은 모나드 영으로 nil을, 모나드 합으로 append를 가지는 가법 모나드이다.

리스트는 append 연산 하에서 모노이드를 형성한다. 모노이드의 항등원은 빈 리스트인 nil이다. 사실, 이것은 리스트 요소 집합에 대한 자유 모노이드이다.

같이 보기

• 배열
• 연결 리스트
• 큐