[C++/자료구조] 배열(array)로 리스트 구현하기

포스팅에 앞서

C++로 리스트를 구현하는데에는 구조체와 포인터, 동적할당에 대한 이해가 필요합니다. 따라서 이해가 부족한 경우 이전 포스팅을 먼저 보시는 것을 추천합니다.

리스트란?

리스트(list)는 우리가 자료를 정리하는 방법 중 하나다.

예를 들어, 학생의 목록이 적혀있는 출석부라든가, 들어야 할 강의 목록과 같은 것을 리스트로 관리한다.

리스트의 특징을 살펴보자.

 

• 리스트에는 항목들이 차례대로 저장되어 있다.
• 리스트의 각 항목은 순서 또는 위치(index)를 가진다.

리스트를 가지고 할 수 있는 기본적인 연산에는 어떤 것들이 있을까?

 

• 삽입 : 리스트에 새로운 항목을 추가한다.
• 삭제 : 리스트에서 항목을 삭제한다.
• 탐색 : 리스트에서 특정한 항목을 찾는다.
• 초기화 : 리스트의 모든 요소를 제거한다.
• 길이 : 리스트의 길이를 구한다.
• 출력 : 리스트의 모든 요소를 표시한다.

위와 같은 것들이 가장 기본적인 연산이라 할 수 있으며, 리스트를 만들고자 한다면 위와 같은 것들을 구현해야 할 것이다. 리스트를 구현하는 방법들은 크게 두가지가 있다. 하나는 배열(array), 다른 하나는 연결리스트(linked list)이다.

 

이번 포스팅에는 배열을 중심으로 이 두가지를 소개하며, 둘의 장단점에 대해 알아볼 것이다. 또한, 배열로 리스트를 구현하는 코드를 알아볼 것이다. 링크드리스트의 코드를 짜는 것은 다음 포스팅에서 알아볼 예정이다.

배열

배열을 이용해 리스트를 구현하면 순차적인 메모리 공간이 할당되므로, 이것을 리스트의 순차적 표현(sequential representation)이라고도 한다.

 

 

배열로 만들어진 리스트의 중간에 새로운 항목을 추가하려면 어떻게 해야할까?

 

위의 사진과 같이 원래 그 자리에 있던 것부터 한칸씩 뒤로 밀어야한다.

삭제하는 경우도 마찬가지다. 뒤의 것들을 한칸씩 당겨야한다.

 

배열로 리스트 구현

지금부터 배열으로 리스트의 연산들을 구현해보자.

우선, 배열과 항목의 개수를 구조체로 묶어서 ArrayListType를 정의해보자.

이때, 배열의 최대 크기는 100으로 고정한다.

 

#define MAX_LIST_SIZE 100 // 리스트의 최대 크기

struct ArrayListType {
	int array[MAX_LIST_SIZE]; // 배열 정의
	int size; // 현재 리스트에 저장된 항목의 개수
};

 

이제 리스트의 연산들을 함수로 구현해보자.

---

이때, 모든 연산은 구조체 포인터를 받는다. 함수 안에서 구조체를 변경해야하기 때문이다.

예를 들어, 배열의 0번째에 5라는 숫자를 삽입한다고 생각해보자.

array[0]이 5로 바뀌어야하며, size는 1 늘어날 것이다.

또한 원래 array[0]~array[size-1]까지는 줄줄이 뒤로 밀려야한다.

이러한 변화들을 모두 구조체에 적용하려면 반드시 포인터를 사용해야한다. 포인터를 사용하지 않으면 구조체의 복사본이 전달되어서 원본 구조체를 변경할 수 없기 때문이다.

---

리스트 초기화 함수

먼저, 리스트를 초기화 하는 함수를 구현하자.

이 함수는 리스트의 사이즈를 0으로 만들어준다.

 

void init(ArrayListType* L) {
	L->size = 0;
}

 

리스트가 비어있는지 확인하는 함수

리스트에서 항목을 삭제하는 경우를 생각해보자. 리스트가 비어있다면 더이상 삭제할 것이 없으므로 오류가 발생할 것이다. 따라서 리스트가 비어있는지 확인하는 과정이 필요하다.

 

리스트가 비어있는 경우에는 리스트의 size가 0일 것이다.

이것을 코드로 나타내보면 다음과 같다.

 

int is_empty(ArrayListType* L) {
	return L->size == 0;
}

L->size == 0이면 1(참)을 반환하고, 아니면 0(거짓)을 반환하는 코드이다.

 

리스트가 꽉 찼는지 확인하는 함수

이번에는 반대로 리스트에 항목을 추가하는 경우를 생각해보자. 리스트가 꽉 차있다면 더이상 추가할 수 없으므로 오류가 발생할 것이다. 따라서 리스트가 꽉 찼는지 확인하는 함수도 필요하다.

 

리스트가 꽉 차있는 경우에는 리스트의 size가 MAX_LIST_SIZE와 같을 것이다.

이것을 코드로 나타내보면 다음과 같다.

 

int is_full(ArrayListType* L) {
	return L->size == MAX_LIST_SIZE;
}

 

***

여기서 잠깐 배열의 특징 하나를 짚고 넘어가자.

배열은 크기가 고정되어있다.  사용하기 전에 배열의 크기를 지정해야하며, 실행시간동안에 변경이 불가능하다.

코드를 짤 당시에, 얼마나 많은 데이터를 배열에 저장할지에 대해서는 알 수 없다. 따라서 이런 점이 배열의 치명적인 단점이다. 이 코드에서는 MAX_LIST_SIZE가 100으로 고정되어있으므로 100개가 넘어가면 배열에 더이상 넣을 수 없다.

 

리스트의 특정한 항목을 찾는 함수

다음으로, 리스트의 인덱스를 받아 해당 인덱스의 요소를 반환하는 함수를 구현해보자.

이때, 입력받는 인덱스가 0 이상이어야하며, 리스트의 사이즈를 초과하면 오류가 날 것이다. 이 경우, "위치 오류"라고 오류메세지를 출력해주자.

 

int get_entry(ArrayListType* L, int pos) {
	if (pos < 0 || pos >= L->size) {
		cout << "위치 오류" << '\n';
		exit(1);
	}
	return L->array[pos];
}

 

pos에는 위치가 들어가면 될 것이다.

 

리스트 출력 함수

리스트를 출력해주는 함수는 설명이 많이 필요하지 않을 것 같다.

그냥 리스트를 한번 훑으며 리스트의 사이즈만큼 처음부터 끝까지 출력해주면 될 것이다.

 

void print_list(ArrayListType* L) {
	for (int i = 0; i < L->size; i++) {
		cout << L->array[i] << ' ';
	}
	cout << '\n';
}

 

항목 추가 함수

임의의 위치에 원하는 정수를 삽입하는 insert()함수를 구현해보자.

 

앞에서 언급했듯이 중간에 새로운 항목을 추가하게 된다면, 이후의 것들이 한칸씩 뒤로 밀린다.

예를 들어, pos=1에 새로운 항목을 추가한다면,

끝에 있는 것부터 한칸씩 뒤로 밀면 될 것이다. 이해가 되지 않는다면 그림을 통해 알아보자.

 

 

 

array[4] = array[3]

array[3] = array[2]

array[2] = array[1]

array[1] = 원하는 숫자

 

 

또한, 원하는 위치에 정수를 추가하기 전에 따져봐야 할 것이 있다.

 

• 리스트가 꽉 차있지는 않은가? -> is_full 함수로 체크
• 위치가 유효한 위치인가?  -> 0이상이어야하고, 리스트의 사이즈를 초과하면 안된다.

이런 조건들을 코드로 작성해보면 다음과 같다.

 

void insert(ArrayListType* L, int pos, int item) {
	if (!is_full(L) && (pos >= 0) && (pos <= L->size)) {
		for (int i = (L->size - 1); i >= pos; i--) {
			L->array[i + 1] = L->array[i];
		}
		L->array[pos] = item;
		L->size++;
	}
}

 

반복문이 L->size-1부터 시작하는 이유는, index가 0부터 시작하기 때문에 size - 1이 맨 뒤의 index이기 때문이다.

item에는 리스트에 삽입하고 싶은 정수를 입력하면 되겠다.

 

항목 삭제 함수

마지막으로 임의의 위치에 있는 항목을 삭제하는 remove(list, pos)를 구현해보자.

이때도 역시 순서가 중요한데, 항목을 추가할 때와 반대된다.

먼저 삭제하고, 빈공간을 만든뒤 뒤에 있는 것들을 앞으로 땡겨오면 된다.

이번에도 그림으로 알아보자.

 

 

 

원하는 위치에 있는 항목을 삭제할 때도 조건이 있다.

• 리스트가 비어있지는 않은가? -> is_empty 함수로 확인
• 유효한 위치인가? - 위치가 음수가 아니며 리스트의 크기를 초과하지 않는가?

만약 위치 조건을 만족하지 못 하면, "위치오류"라는 오류 메세지를 출력하자.

 

이런 조건들을 코드로 작성해보면 다음과 같다.

int remove(ArrayListType* L, int pos) {
	int item;

	if (pos < 0 || pos >= L->size) {
		cout << "위치오류" << '\n';
		exit(1);
	}
	item = L->array[pos];
	for (int i = pos; i < (L->size - 1); i++) {
		L->array[i] = L->array[i + 1];
	}
	L->size--;
	return item;
}

 

테스트 프로그램

지금까지 작성한 코드를 테스트해보자.

 

int main() {
	ArrayListType list;
	
	init(&list);
	insert(&list, 0, 10); print_list(&list); // 0번째 위치에 10 추가
	insert(&list, 0, 5); print_list(&list); // 0번째 위치에 5 추가
	insert(&list, 1, 15); print_list(&list); // 1번째 위치에 15 추가
	insert(&list, 2, 0); print_list(&list); // 2번째 위치에 0 추가
	cout << get_entry(&list, 1) << '\n'; // 1번째 위치에 있는 항목 출력
	remove(&list, 2); print_list(&list); // 2번째 위치에 있는 항목 제거
	remove(&list, 0); print_list(&list); // 0번째 위치에 있는 항목 제거

	return 0;
}

 

실행 결과는 다음과 같다.

 

 

전체 코드

#include <iostream>
using namespace std;

#define MAX_LIST_SIZE 100 // 리스트의 최대 크기

struct ArrayListType {
	int array[MAX_LIST_SIZE]; // 배열 정의
	int size; // 현재 리스트에 저장된 항목의 개수
};

// 리스트 초기화 함수
void init(ArrayListType* L) {
	L->size = 0;
}

int is_empty(ArrayListType* L) {
	return L->size == 0;
}

int is_full(ArrayListType* L) {
	return L->size == MAX_LIST_SIZE;
}

int get_entry(ArrayListType* L, int pos) {
	if (pos < 0 || pos >= L->size) {
		cout << "위치 오류" << '\n';
		exit(1);
	}
	return L->array[pos];
}

void print_list(ArrayListType* L) {
	for (int i = 0; i < L->size; i++) {
		cout << L->array[i] << ' ';
	}
	cout << '\n';
}

void insert(ArrayListType* L, int pos, int item) {
	if (!is_full(L) && (pos >= 0) && (pos <= L->size)) {
		for (int i = (L->size - 1); i >= pos; i--) {
			L->array[i + 1] = L->array[i];
		}
		L->array[pos] = item;
		L->size++;
	}
}

int remove(ArrayListType* L, int pos) {
	int item;

	if (pos < 0 || pos >= L->size) {
		cout << "위치오류" << '\n';
		exit(1);
	}
	item = L->array[pos];
	for (int i = pos; i < (L->size - 1); i++) {
		L->array[i] = L->array[i + 1];
	}
	L->size--;
	return item;
}

int main() {
	ArrayListType list;
	
	init(&list);
	insert(&list, 0, 10); print_list(&list); // 0번째 위치에 10 추가
	insert(&list, 0, 5); print_list(&list); // 0번째 위치에 5 추가
	insert(&list, 1, 15); print_list(&list); // 1번째 위치에 15 추가
	insert(&list, 2, 0); print_list(&list); // 2번째 위치에 0 추가
	cout << get_entry(&list, 1) << '\n'; // 1번째 위치에 있는 항목 출력
	remove(&list, 2); print_list(&list); // 2번째 위치에 있는 항목 제거
	remove(&list, 0); print_list(&list); // 0번째 위치에 있는 항목 제거


	return 0;
}

 

배열의 장단점

배열은 구현이 간단하고 속도가 빠르다는 장점이 있다.

 

코드를 한번 짜봄으로써 단점에 대해서는 어느정도 느낌이 왔을 것이다.

리스트의 크기가 고정되어 있다는 것이 큰 단점이고,

리스트 중간에 새로운 데이터를 삽입하거나 삭제하는 과정이 링크드리스트에 비해 복잡하다.

 

링크드리스트의 장점은 배열의 단점이 없다는 것이다.

링크드리스트는 동적으로 크기가 변할 수 있으며 삭제나 삽입 시에 배열처럼 데이터를 이동할 필요도 없다.

이 친구는 포인터를 사용해 데이터들을 연결한다. 따라서 추상 데이터 타입 "리스트"의 구현에만 사용되는 것이 아니고 다른 여러가지 자료구조(트리, 그래프, 스택, 큐) 등을 구현하는데도 많이 사용된다.

하지만 배열에 비해 구현이 어렵고 오류가 나기 쉬우며, 포인터까지 저장해야하므로 메모리 공간을 많이 사용한다. 또한 배열처럼 i번째 데이터를 바로 찾을 수 없어 맨 앞에서부터 순차적으로 접근해야한다.

 

이렇게 배열을 중심으로, 배열의 장단점과 링크드리스트의 장단점, 그리고 배열로 리스트를 구현하는 방법까지 알아보았다. 다음 포스팅에서는 연결리스트(linked list)에 대해 더 깊게 알아보고, 연결리스트로 리스트를 구현하는 코드까지 짜볼 예정이다.