선형 리스트

선형 리스트(linear list)는 자료가 순서 있게 나열된 추상적 자료형(ADT)입니다.

(a_0, a_1, a_2, \cdots, a_{n-1})

아래와 같은 예시를 생각해볼 수 있습니다:

(폰, 룩, 퀸, 킹, 비숍, 나이트)
(월, 화, 수, 목, 금, 토, 일)
(1, 2, 3, 4, 5, ...)
그 외 순서 있게 나열할 수 있는 모든 것들

구분

선형 리스트에 포함된 자료의 타입이 모두 같다면 동형(homogeneous)이라고 합니다. 아래는 러스트의 배열이며, 동형 선형 리스트입니다.

let ages: [i32; 4] = [15, 26, 34, 42];

반대로 자료의 타입이 다를 수 있다면 이형(heterogeneous)이라고 합니다. 아래는 엘릭서의 리스트이며, 이형 선형 리스트입니다.

inputs = [:something, "Hello", 42]

연산

길이 구하기
모든 원소를 하나씩 방문하기
$k$ 번째 원소 구하기
$k$ 번째 원소 바꾸기
$k$ 번째 자리에 새 원소를 삽입하고 나머지 원소를 뒤로 밀기
$k$ 번째 원소를 삭제하고 나머지 원소를 앞으로 당기기
서로 다른 두 리스트를 합치기

구현

배열

배열(array)은 가장 기본적인 연속적 자료구조입니다.

고정된 크기의 메모리에 각 원소가 순서에 맞게 연속적으로 저장됩니다. 각 원소에 바로 접근할 수 있어 효율적이지만, 원소를 더하거나 뺄 때 형태를 유지하기 위해 비용이 필요합니다.

장점

랜덤 엑세스가 가능하다: 시작 주소와 인덱스로 각 원소의 메모리 주소를 바로 알 수 있기 때문에 각 원소에 바로 접근할 수 있습니다.
공간 효율성이 좋다: 순수한 데이터의 나열이기 때문에 낭비되는 공간이 없습니다.
메모리 지역성이 좋다: 현대 컴퓨터는 캐시 메모리를 적극 이용하는데, 배열은 연관된 자료가 한 곳에 모여있으므로 캐시 적중률이 좋아서 실질적으로 더 빠릅니다.

단점

프로그램 실행 중 그 크기를 바꿀 수 없습니다.
- 동적 배열로 해결할 수 있습니다.
리스트를 쪼개고 합치거나, 앞에 자료를 추가하는것이 비효율적입니다.
- 리스트의 $n$ 개의 원소를 옮겨야하므로, $O(n)$ 의 비용이 듭니다.

용례

대부분의 프로그래밍 언어들이 동적 배열을 기본 선형 리스트로 사용합니다.

효율이 중요한 시스템 프로그래밍 언어들은 배열

연결 리스트

연결 리스트(linked list)는 가장 기본적인 연결적 자료구조입니다.

각각의 원소는 메모리 이곳저곳에 떨어져서 저장되고, 이들을 포인터로 논리적으로 연결합니다. 각 원소가 논리적으로 연결되어 있기 때문에 중간에 값을 추가하거나 자르거나 나누거나 합치는 등의 연산은 효율적이지만 랜덤 엑세스가 불가능하여 특정 원소를 찾기 위해서는 대부분의 경우 앞에서부터 순차적으로 확인해야합니다.

장점

쪼개고 잇는 연산이 효율적이다: 배열은 수정을 위해서 배열 전체를 복사해야 하지만 연결 리스트는 그럴 필요가 없습니다. 해당 노드에서 다음 노드로의 연결 고리만 바꾸어주면 되기 때문에 상수시간( $O(1)$ )에 해결할 수 있습니다. 원소의 순서를 바꿔야할 필요가 있을 경우에도, 원소 자체를 옮기는 것보다는 포인터를 바꾸는 것이 훨씬 효율적입니다.
성능이 일정하다: 동적 배열의 경우 실행 중간에 크기가 커질 때에 한해 성능 저하가 일어나기 때문에 성능이 일정하지 않습니다.
추가가 자유롭다: 컴퓨터의 메모리가 부족하지 않는 이상 오버플로우 등의 문제를 겪을 일이 없습니다.

단점

최적화가 어렵습니다. 캐시 지역성(cach locality)이 좋지 않기 때문에 캐시 적중률이 낮으며, 반드시 포인터로 메모리 여기저기를 순회해야합니다.
랜덤 엑세스가 불가능합니다. 리스트의 마지막 원소에 접근하려면 대부분의 경우 전체 리스트를 순회해야합니다.
공간 효율성이 나쁩니다. 포인터를 활용하기 때문에 반드시 배열보다 많은 메모리를 사용합니다.

용례

불변 자료구조를 적극 활용하는 프로그래밍 언어들이 연결 리스트를 기본 선형 리스트로 자주 사용합니다. ex) 엘릭서의 List, 하스켈의 [a]

이러한 언어들은 언어 차원에서 리스트를 쪼개고 잇는 연산을 쉽게 쓸 수 있도록 지원합니다.

list = [1, 2, 3, 5, 7]

[_ | primes] = list
assert primes == [2, 3, 5, 7]

이러한 언어들은 포인터로 잇는 연결적 자료구조의 특성을 적극 활용하여 성능을 높입니다. 이를 영속적 자료 구조(persistent data structure)라고 합니다. 예를 들어 아래와 같이 1, 2, 3, 4를 담은 연결 리스트 list가 있고, 이를 이용해 new_list를 만들었다고 합시다:

list = [1, 2, 3, 4]
new_list = [0 | list]

연결 리스트의 특성을 활용하면 1, 2, 3, 4를 복사하지 않고도 이를 표현할 수 있습니다.

     /-> [1, 2, 3, 4]
[0, *]

그러나 위에서 언급한 단점으로 인하여 데이터를 저장하고 다룰 때에는 배열을 쓸 수 있도록 지원하고 있습니다. ex) 엘릭서의 :array, {}, 하스켈의 Data.Array 등.