리스트 (컴퓨팅)

3. 구현

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

리스트 구현의 표준적인 방법은 Lisp에서 시작되었으며, 리스트의 각 요소는 값과 다음 요소의 위치를 가리키는 포인터를 포함한다.^[1] 이는 리스트에 중첩된 하위 리스트가 있는지 여부에 따라 연결 리스트 또는 트리를 생성한다.^[2] 일부 구형 Lisp 구현 (예: 심볼릭스 3600의 Lisp 구현)은 특수한 내부 표현을 가진 "압축 리스트" (CDR 코딩 사용)를 지원했다.^[3] 리스트는 반복 또는 재귀를 사용하여 조작할 수 있는데,^[4] 전자는 명령형 프로그래밍 언어에서, 후자는 함수형 프로그래밍 언어에서 일반적이다.^[5]

리스트는 인덱스-값 쌍을 저장하는 자기 균형 이진 탐색 트리로 구현할 수 있으며, 임의의 요소에 대해 동일한 시간 접근을 제공한다.^[6] (예: 모두 가장자리에 있고, 내부 노드는 검색을 안내하는 데 사용되는 가장 오른쪽 자식의 인덱스를 저장). 리스트 크기에 대해 로그 시간만큼 소요되지만, 크게 변경되지 않는 한 임의 접근의 기능을 제공하고, 로그 시간에 스왑, 접두사 및 추가 작업을 수행할 수 있게 한다.

Lisp에서 리스트는 프로그램과 데이터를 모두 표현하는 기반 데이터 타입이다. 많은 방언에서 처음 세 개의 소수 리스트는 `(list 2 3 5)`로 표기할 수 있다. Scheme을 포함한 몇몇 방언에서는 리스트는 값과 포인터의 쌍의 집합이며, 포인터는 다음 쌍 (또는 null)을 가리킨다.

값과 포인터의 쌍 집합으로 리스트를 구현하는 것은 표준적인 방법이며, 중첩된 리스트는 트리 구조가 되고, 그렇지 않으면 연결 리스트가 된다. 그러나, Lisp 처리 시스템에 따라서는 (심볼릭스 3600의 Lisp 등) 배열을 "compressed list^영어"라고 부르며 사용하는 것도 있었다.

Lua와 같이 리스트 데이터 구조가 준비되지 않은 언어에서는 연관 배열이나 테이블로 리스트를 구현하기도 한다. Lua는 내부적으로 수치 인덱스를 가진 리스트를 배열로 저장하지만, 인터페이스는 테이블 그대로이다.

리스트는 반복이나 재귀 호출을 사용하여 처리할 수 있다. 전자는 꼬리 최적화가 없는 언어나 리스트에 대한 재귀 처리가 일반적이지 않은 언어에서 선호된다. 후자는 일반적으로 함수형 프로그래밍 언어에서 선호되는데, 반복은 배열과 함께 사용되는 경우가 많고 명령형으로 간주되기 때문이다.

컴퓨터에서 리스트는 집합보다 구현이 간단하여, 수학에서의 유한 집합은 제한(중복 요소 불허, 순서 무의미)을 가한 리스트로 구현할 수 있다. 리스트가 정렬되면 객체가 집합의 요소인지 판정이 빨라지지만, 정렬 유지를 위해 요소 추가 시간이 증가한다. 따라서 효율적인 구현에서는 집합을 리스트가 아닌 균형 이진 탐색 트리나 해시 테이블로 구현한다.

4. 특성

리스트는 다음과 같은 특성을 갖는다.

• '''크기''': 리스트 내에 몇 개의 요소가 있는지를 나타낸다.
• '''등가성''':
• 수학적으로 리스트의 등가성은 단순히 객체의 동일성으로 정의될 수 있다. 즉, 두 리스트가 같다는 것은 두 리스트가 동일한 객체라는 것이고, 그 경우에만 해당한다.
• 현대의 프로그래밍 언어에서는 리스트의 등가성은 일반적으로 요소 간의 구조적 등가성으로 정의된다. 리스트가 타입화된 경우, 해당 타입 또한 영향을 미칠 수 있다.
• '''타입''': 리스트의 요소는 리스트의 타입과 호환되는 타입을 가져야 한다. 리스트가 배열을 사용하여 구현된 경우에는 타입이 지정되는 것이 일반적이다.
• 리스트 내의 모든 요소는 '''인덱스'''를 갖는다. 첫 번째 요소는 인덱스 0 (또는 다른 정의된 정수 값)을 갖는다. 그 다음 요소는 이전 요소보다 1 큰 인덱스를 갖는다. 마지막 요소는 `(첫 번째 인덱스) + (리스트의 크기) - 1`이라는 인덱스를 갖는다.
• 특정 인덱스를 지정하여 요소를 얻을 수 있다.
• 인덱스가 증가하는 순서로 리스트의 내용을 순회할 수 있다.
• 특정 인덱스에 있는 요소의 값을 다른 요소에 영향을 주지 않고 변경할 수 있다.
• 특정 인덱스에 요소를 추가할 수 있다. 뒤쪽 요소의 인덱스는 1씩 증가한다.
• 특정 인덱스의 요소를 제거할 수 있다. 뒤쪽 요소의 인덱스는 1씩 감소한다.

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'' 케이스를 별도로 처리한다.

6. 모나드

리스트 타입은 다음 함수를 사용하여 모나드를 형성한다. (타입 ''E''의 요소를 갖는 단형 리스트를 나타내기 위해 ''L'' 대신 ''E''^*를 사용):

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

:

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

:

또는 모나드는 연산 ''return'', ''fmap'' 및 ''join''을 사용하여 정의할 수 있으며, 다음과 같다.

:

:

''fmap'', ''join'', ''append'' 및 ''bind''는 각 재귀 호출 시 점차 더 깊은 인수에 적용되므로 잘 정의되어 있다.

리스트 타입은 ''nil''을 모나드 제로로, ''append''를 모나드 합으로 하는 덧셈 모나드이다.

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

7. 활용

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

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

리스트 구현 방법은 주로 연결 리스트 (단방향 또는 양방향)와 동적 배열 두 가지가 있다.

Lisp에서 리스트는 그 기반을 이루는 데이터 타입으로, 프로그램과 데이터를 모두 표현한다. 처음 세 개의 소수의 리스트는 많은 방언에서 `(list 2 3 5)`로 표기할 수 있다. Scheme을 포함한 몇몇 방언에서는 리스트는 값과 포인터의 쌍의 집합이며, 포인터는 다음 쌍 (또는 null)을 가리킨다.

값과 포인터 쌍의 집합으로 리스트를 구현하는 것은 표준적인 방법이며, 리스트가 중첩되어 있다면 트리 구조가 되고, 그렇지 않다면 연결 리스트가 된다. 그러나, Symbolics 3600의 Lisp 등에서는 배열을 "compressed list^영어"라고 부르며 사용하는 것도 있었다.

언어에 따라서는 리스트 데이터 구조가 준비되어 있지 않은 경우도 있다. 그러나 그러한 언어에서는 연관 배열이나 어떤 종류의 테이블로 리스트를 구현하는 수단을 제공한다. 예를 들어, Lua는 테이블을 제공한다. Lua에서는 수치 인덱스를 가진 리스트를 내부적으로 배열로 저장하지만, 인터페이스는 테이블 그대로이다.

리스트는 반복이나 재귀 호출을 사용하여 처리할 수도 있다. 전자는 꼬리 최적화가 없는 언어 또는 리스트에 대한 재귀 처리가 어떤 이유로든 일반적이지 않은 언어에서 선호된다. 후자는 일반적으로 함수형 프로그래밍 언어에서 선호되는데, 반복은 배열과의 조합으로 사용되는 경우가 많고, 또한 명령형으로 간주되는 경우가 많기 때문이다.

8. 프로그래밍 언어별 지원

대부분의 프로그래밍 언어들은 리스트 자료형을 지원한다. 문법은 `[0, 1, 2]`와 같이 대괄호 안에 쉼표로 값을 구분하는 것이 보통이지만, 몇몇 프로그래밍 언어들은 다른 방식을 사용한다.

일부 프로그래밍 언어는 리스트 자료 구조를 제공하지 않지만, 리스트를 에뮬레이션하기 위해 연관 배열 또는 일종의 테이블을 사용하도록 제공한다. 예를 들어, Lua는 테이블을 제공한다. Lua는 숫자 인덱스를 가진 리스트를 내부적으로 배열로 저장하지만, 여전히 딕셔너리 형태로 나타난다.^[4]

Lisp에서 리스트는 기본적인 데이터 타입이며 프로그램 코드와 데이터를 모두 나타낼 수 있다. 대부분의 방언에서 처음 세 개의 소수를 나타내는 리스트는 `(list 2 3 5)`로 작성할 수 있다. Scheme을 포함한 여러 Lisp 방언에서 리스트는 값과 다음 쌍(또는 null 값)에 대한 포인터로 구성된 쌍의 모음이며, 단일 연결 리스트를 만든다.^[5]

파이썬 등, 내장 데이터 타입 중 하나로 리스트를 제공하는 언어도 있다.

참조

_[1] 서적 Combinatorial Algorithms: Theory and Practice Prentice Hall 1977
_[2] 서적 Structure and Interpretation of Computer Programs MIT Press
_[3] 웹사이트 Data Structures and Algorithms http://www.mta.ca/~r[...] 2014-11-12
_[4] 서적 Programming in Lua (first edition) http://www.lua.org/p[...] Lua.org 2003-12
_[5] 서적 Common Lisp Digital Press 1990
_[6] 서적 Structure and Interpretation of Computer Programs MIT Press