리스트(List)
리스트란 순서를 가진 항목들의 모임을 말한다. 예시로 순서를 갖는 요일, 한글의 자음의 모임 등이 리스트에 해당한다.
리스트를 활용하면 어떤 연산들을 할 수 있을까.
리스트의 Abstract Data Type
-
insert(list, pos, item) - pos 위치에 요소를 추가한다.
-
insert_last(list, item) - 맨 끝에 요소를 추가한다.
-
insert_first(list, item) - 맨 처음에 요소를 추가한다.
-
delete(list, pos) - pos 위치의 요소를 제거한다.
-
clear(list) - 리스트의 모든 요소를 제거한다.
-
get_entry(list, pos) - pos 위치의 요소를 반환한다.
-
get_length(list) - 리스트의 길이를 구한다.
-
is_empty(list) - 리스트가 비었는지를 검사한다.
-
is_full(list) - 리스트가 꽉 찼는지를 검사한다.
-
print_list(list) - 리스트의 모든 요소를 표시한다.
리스트는 두가지 배열 리스트와 연결 리스트 두 가지 방법으로 구현할 수 있다. 이번 내용에서는 배열을 이용해 구현하는 리스트에 대해 공부해보자.
배열 리스트 (ArrayList)
배열로 리스트는 간단하게 구현할 수 있다는 장점을 가지고 있다. 하지만 배열의 특성상 크기가 고정되어 항목의 개수에 제한이 생기고 삽입, 삭제를 효율적으로 구현하지 못한다는 단점이 있다.
배열 리스트는 1차원 배열에 항목들을 순서대로 저장하고 삽입 연산시 삽입한 다음의 항목들을 모두 순서대로 옮겨 공간을 확보해야 하고 삭제도 마찬가지로 삭제위치 다음의 항목들을 순서대로 다시 이동시켜 공간을 메워야 한다.
배열 리스트의 구현
1. ArrayListType 정의
#define MAX_LIST_SIZE 100 //리스트의 최대 크기 정의
typedef int element; //항목의 정의
typedef struct {
element list[MAX_LIST_SIZE]; //배열 정의
int length; //현재 배열에 저장된 항목의 개수
} ArrayListType;
void init(ArrayListType *L){
L->length = 0; //리스트 초기화
} 2. is_empty 와 is_full 연산 구현
int is_empty(ArrayListType *L){
return(L->length == 0);
} //리스트가 비어있는지 확인
int is_full(ArrayListType *L){
return(L->length == MAX_LIST_SIZE);
} //리스트가 꽉 차있는지 확인3. insert 연산 구현 (삽입)
void insert(ArrayListType *L, int position, element item)
{ //position은 삽입위치, item은 삽입하려는 원소
if(!is_full(L) && (position >= 0) && (position <= L->length){ //삽입 가능한지 검사
int i;
for(i=(L->length-1); i>=position; i--)
L->list[i+1] = L->list[i]; //position에 삽입될 원소를 위한 공간 마련
L->list[position] = item; //원소 삽입
L->length++; //리스트의 길이 +1 증가
}
}
이 부분이 좀 어려워서 구체적인 설명을 해야겠다...
먼저 if문을 통해 원소를 삽입할 수 있는지 여부에 대해서 검사해야 한다.
여기서 L->length-1은 인덱스의 마지막 항목을 의미하는 것이며 삽입위치가 인덱스 0보다 작아서도 마지막 항목을 벗어나 있어도 안된다는 뜻이다.
조건을 만족했으면 먼저 반복문을 통해 삽입 위치에 공간을 확보해야한다.
for문은 인덱스의 마지막 항목을 시작으로 position 위치까지 하나씩 그 다음 칸으로 이동하며 원소가 들어갈 자리의 공간을 마련하는 과정이다.
공간이 확보가 되면 position의 위치에 원소 item을 삽입하고 리스트의 길이를 추가된 만큼 한칸 늘려주면 된다.
4. delete 연산 구현 (삭제)
element delete(ArrayListType *L, int position)
{
int i;
element item;
if(position < 0 || position >= L->length)
error("위치오류") //삭제할 위치 검사
item = L->list[position];
for(i=position; i<(L->length-1); i++)
L->list[i] = L->list[i+1]; //삭제할 공간 메우기
L->length--; //리스트 길이 한칸 줄이기
return item; //삭제한 원소 item에 반환
}
[참고자료]
교재: C언어로 쉽게 풀어쓴 자료구조
