순서 리스트의 순차 표현(sequential representation)은 순서 리스트를 컴퓨터 메모리에 저장할 때 객체들의 논리 순서와 메모리의 실제 저장 순서를 일치시키는 것으로, 순차적 사상(sequential mapping) 표현이라고 하며, 순차 표현된 순서 리스트를 간단히 순차 리스트(sequential list)라고 합니다.
순서 리스트의 순차 표현
순차 리스트는 일반적으로 배열을 이용해서 구현합니다. 예제 3.2와 같이, 원소들의 논리 순서를 인덱스로 구성하여 순서 리스트를 논리적 배열로 표현하고, 이 인덱스를 프로그래밍 언어에서 제공하는 배열의 인덱스에 순차적으로 대응시켜 메모리에 저장하면 원소들의 논리 순서와 메모리 저장 순서는 동일하게 됩니다.
예를 들면, 성적 순서 리스트 L1=<(광석, 98, 185), (민국 92, 188), (혜리, 87, 163), (슬기, 75, 156), (재민, 63, 172)>을 원소들의 논리 순서를 인덱스로 구성해서 논리적 배열 L1={<0, (광석, 98, 185)>, <1, (민국 92, 188)>, <2, (혜리, 87, 163)>, <3, (슬기, 75, 156)>, <4, (재민, 63, 172)>}으로 표현하고, 이 논리적 배열의 인덱스 순서(즉, 순서 리스트의 논리 순서)를 프로그래밍 언어에서 제공하는 1차원 배열의 인덱스에 순차적으로 대응시켜 저장하면, L1은 배열 메모리에 저장됩니다.
공집합인 순차 리스트의 생성
순차 리스트를 구현하기 위해서는 원소들의 순차적으로 저장하기 위해 메모리 공간인 1차원 배열(예를 들면, 크기 N인 1차원 배열 list)과 이 배열에 저장된 순차 리스트의 크기(원소 개수)를 나타내기 위한 변수(예를 들면, 정수형 변수 length)를 정의해야 합니다. 그리고 순차 리스트를 처음 생성하면 공집합이므로, length 변수는 -1로 초기화됩니다. 예제 코드 3.1은 최대 크기가 N인 정수형 순차 리스트를 생성하는 C 코드의 예입니다.
예제 코드 3.1
순차 리스트를 위한 변수정의 및 초기화 예
int list[N], length; /* 순차리스트를 위한 변수 정의 */
length = -1; /* 공집합인 순차리스트 표현 */
순차 리스트의 추가 연산
순차 리스트에서 새로운 원소를 i번째 순서로 추가하면, i번째 원소와 그 뒤의 원소들은 한 칸씩 뒤로 이동하게 되고, 특히 새로운 원소를 맨 앞쪽에 추가하면, 모든 원소들은 한 칸씩 뒤로 이동하게 됩니다. 순차 리스트 list에서 i번째로 새로운 원소 x를 추가하려면, 맨 뒤에서부터 i번째까지 각 원소를 한 칸씩 뒤로 이동시켜 i번째 위치를 비운 후, 여기에 추가 원소 x를 저장하면 됩니다. 함수 3.1은 이런 추가 연산을 수행하는 C함수의 작성 예입니다.
함수 3.1
순차 리스트의 추가 함수 설계 및 작성 예
/* 순차리스트 list[]의 i번째 위치에 원소 x를 추가함 */
int insertList(int list[], int n, int *length, int i, int x){
int j;
if(i<0 || i>*length+1). return(0); /* 추가연산 실패 */
if(*length +1 == n) return(0); /* 추가연산 실패 */
for(j=*length; j >= i; j--) list[j+1] = list[j];
list[i] = x;
*length = *length+1;
return(1); /* 추가연산 성공 */
}순차 리스트의 삭제 연산
순차 리스트의 i번째 원소를 삭제되면, i번째 이후의 원소들은 한 칸씩 앞으로 이동해야 하고, 특히 0번째 원소를 삭제하면 모든 원소들은 한 칸씩 앞으로 이동해야 합니다. 순차 리스트에서 i번째 원소를 삭제하려면, 우선 i번째 원소를 임시 변수에 저장한 후, i번째 다음(즉 i+1번째)부터 맨 뒤까지 각 원소를 한 칸씩 앞으로 이동시키면 됩니다.
원소 list [2]=30을 삭제한 후에도 list [4]에는 여전히 50이 저장되어 있지만 순서 리스트의 크기를 나타내는 변수 length의 값이 3으로 변경되었기 때문에 논리적으로 순서 리스트에는 포함되지 않고 무시됩니다. 그리고 삭제된 원소 30은 순서 리스트에서는 삭제되었지만 프로그램에서는 여전히 사용될 수 있음을 고려해서 임시 변수에 저장해 두었는데, 이런 점을 고려해서 일반적으로 삭제 함수는 삭제 연산을 수행한 후 삭제된 원소를 반환하도록 정의합니다.
함수 3.2
순차 리스트의 삭제 함수 설계 및 작성 예
int delete(int list[], int n, int *length, int i){
int temp, j;
if(i<0 }} (i>*length)) return(-1); /* 삭제연산 실패 */
temp = list[i];
for(j=i+1; j<=*length; j++) list[j-1] = list[j];
*length = *length-1;
return(temp); /* 삭제된 원소 반환 */
}추가 연산과 삭제 연산은 앞에서 정의했던 순차 리스트 연산들도 간단히 구현할 수 있습니다. 추가와 삭제 연산을 수행할 때 많은 원소들을 이동시켜야 하는 순차 리스트의 단점은 순서 리스트의 연결 표현으로 해결할 수 있습니다.
댓글