4. 선형 리스트
in Study on Data Structure
Overview
리스트(list)는 단순히 원소들의 순열(sequence) 즉, 원소들을 일렬로 정렬해 놓은 것이다.
선형 리스트(linear list) 또는 순서 리스트(ordered list)는 순서를 가진 원소들의 순열을 말한다.
여기서 순서의 의미는 원소들이 가지고 있는 어떤 특성에 의한 논리적 순서이지 원소들의 물리적 위치로 표현하는 물리적 순서를 의미하지는 않는다.
리스트에 정렬해 놓은 원소들 간에 최소한 앞 뒤 관계와 같이 어떤 의미의 순서 개념을 갖고 있으므로, 리스트는 기본적으로 선형 또는 순서 리스트라 볼 수 있다.
따라서 이 포스트에서는 리스트와 순서 리스트를 특별히 구분하지 않고 사용한다.
List
리스트는 보통 L=(e\(_1\), e\(_2\), …, e\(_n\))로 표기하며, 이때 L은 리스트 이름이고 e\(_i\)는 리스트 원소이다.
첨자 i는 순서를 나타내지만, 리스트에서는 통산 그 위치를 가지고 묵시적으로 순서를 나타내는 것이 보통이다.
원소가 하나도 없는 리스트는 공백 리스트(empty list)라 하고 빈 괄호 L=()로 표현한다.
리스트의 원소는 처음 것을 제외하고 모두 유일한 선행자(predecessor)를 가지고 있으며, 마지막 원소를 제외하고 모두 유일한 후속자(successor)를 가지고 있는 것이 특징이다.
리스트를 정확히 이해햐고 잘 활용하기 위해서는 먼저 이 리스트를 추상 데이터 타입으로 정의해 볼 필요가 있다.
리스트 ADT를 정의하기 위해 리스트를 처리하는 연산을 정의해야 한다.
이런 연산에는 다음과 같은 연산들을 고려해볼 수 있다.
- createList() : 초기에 공백 리스트를 생성한다
- isEmpty(L) : 리스트 L이 공백인지 아닌지 결정한다.
- length(L) : 리스트 L의 길이를 계산한다. 여기서 리스트 길이는 리스트에 포함된 원소의 수이다.
- retrieve(L, i) : 리스트 L의 i번째 원소를 검색한다.
- replace(L, x, y) : 리스트 L의 원소 x를 y로 대체한다.
- delete(L, x) : 공백이 아닌 리스트 L로부터 원소 x를 제거한다. 이 때 리스트 L의 길이는 하나 감소한다.
- insert(L, i, x) : 새로운 원소 x를 리스트 L의 지정된 위치 i에 삽입한다. 이 때 리스트 원소 e\(_i\), e\(_i+1\), …, e\(_n\)은 e\(_i+1\), e\(_i+2\), …, e\(_n+1\)로 되고, 리스트 L의 길이는 하나 증가한다.
이와 같은 연산이 항상 우리가 사용하는 리스트에서 반드시 다 필요한 것은 아니다.
하지만 리스트 정의를 위해서는 주요 연산들을 모두 명세하는 것이 중요하다.
이러한 연산들이 효과적으로 수행되기 위해서는 리스트가 적절히 표현되어야 한다.
순서 리스트는 보통 배열을 이용한 순차 사상 방법을 통해 표현한다.
전통적인 배열 표현 방법을 이용하면 리스트 원소 e\(_i\)와 e\(_i+1\)은 배열의 인덱스 i-1과 i에 대응되게 연속적으로 저장하면 된다.
다음 그림은 리스트 원소들이 어떻게 1차원 배열에 저장되는지를 보여주고 있다.
이러한 순차 표현 방법은 원소의 물리적 순서로 원소의 논리적 순서를 나타내기 때문에, 리스트의 순서를 표시하기 위한 특별한 장치가 필요없다.
이렇게 배열로 표현된 리스트를 순차 표현 리스트라고 하는데, 이러한 리스트는 인덱스를 적절히 제어하면 어떤 방향으로도 원소값을 접근할 수 있다.
다만 리스트에 원소를 제거하거나 삽입하는 연산은 후속 원소들을 모두 앞으로 한 자리씩 당기거나, 뒤로 밀어야만 한다.
이러한 추가적인 오버헤드로 인해 삽입, 삭제가 주도적인 응용에서는 순차 사상으로 표현된 리스트를 이용할 수 없다.
이것이 순차 사상의 치명적인 약점이다.
다음 포스트에서는 이러한 오버헤드가 없는 비순차 사상 표현법에 대해 알아본다.
참고 문서
- 이석호. (2004). 자료 구조와 JAVA. 정익사.
