리스트에 대한 이해와 배열을 통한 구현 (c++)
다음 포스트 : 링크드리스트의 이해와 이를 통한 리스트의 구현
리스트(List)
리스트는 우리가 일상생활에서 자주 사용하는 자료구조 중 하나입이다. 장 볼 때 사용하는 장보기리스트, 소망 등을 적어놓는 버킷리스트 등이 대표적인 예입니다. 현실에서는 특별한 경우가 아니면 리스트에서의 자료 간 순서가 크게 중요하지는 않습니다. 다만 컴퓨터로 구현할 때에 있어서는 index를 통해 자료 간 순서를 설정하는 것이 일반적입니다.
리스트 ADT
리스트 adt에는 자료의 삽입, 삭제, 두 요소 간 교환, 전체 비우기, 리스트 안에 자료가 있는지 확인하기, 리스트의 모든 요소를 표시하기 등 많은 기능이 포함될 수 있습니다. 이번 포스트에서는 삽입 기능, 삭제 기능, 비었는지 확인하는 기능, 요소의 총 개수를 나타내는 기능, 모든 요소를 표현하는 기능 이 다섯 가지만 구현해보도록 합시다.
// c++ code
#include<iostream>
#include<string>
using namespace std;
class List {
// 구현 방법에 따라 앞과 뒤에 추가 구현부가 있을 수 있습니다.
public:
void add() {
// 삽입 함수 구현부
};
void del() {
// 삭제 함수 구현부
};
bool isEmpty() { // 리스트가 비어있는지 확인하는 함수
if ()// 리스트가 비어있을 때 true 반환
return true;
else
return false;
};
void displayAll() {
// 리스트의 모든 요소를 콘솔 화면에 출력하는 함수
};
// 구현 방법에 따라 앞과 뒤에 추가 구현부가 있을 수 있습니다.
};
int main() { // 리스트를 사용하는 부분입니다. 쇼핑리스트로 이용한다고 가정합시다.
List list1;
cout << "쇼핑리스트에 넣을 항목을 입력하시오";
// 쇼핑리스트에 항목을 입력하는 부분, list1.add()를 통해 사용
cout << "집에 있는 물건들을 살펴보고 삭제할 물건들은 삭제합시다.\n";
cout << "삭제할 항목 : ";
// 항목을 삭제하는 부분, list1.del()을 통해 사용
cout << "장 볼 리스트를 출력합니다.";
// 장 볼 리스트를 출력하는 부분, isEmpty()와 displayAll()을 통해 사용 가능배열(array)을 통한 구현
배열을 통해 리스트 adt를 구현해봅시다. 우선 입력받은 문자열을 배열에 저장해야 하므로 문자형 배열과 배열에 들어있는 항목의 수를 갖는 정수형 변수 하나를 포함시켜야 합니다.
// c++ with array
#include<iostream>
#include<string>
using namespace std;
class List {
private:
string shoppingList[100];
int length = 0;
사용자는 List가 배열로 이루어져있는지 아닌지 몰라도 List를 사용할 수 있어야 하므로 private으로 선언합시다. 다음은 삽입 구현부입니다.
public:
void add(string str) {
shoppingList[length] = str;
length++;
};
legnth변수를 이용하여 쇼핑리스트 맨 끝에 입력받은 값을 넣고, length를 하나 늘려줍니다.
삭제 함수는 삽입과 다르게 과정이 약간 복잡합니다. 다음 그림을 보면서 설명한 후 코드를 작성해봅시다.
배열은 특정 인덱스의 값을 삭제하고 나서 그 칸을 채우고 다음 값들을 이동하는 것을 원칙으로 합니다. 이를 코드로 나타내면 다음과 같습니다.
void del(string str) {
if (isEmpty()) { cout << "리스트가 비어있습니다!"; return; }
for (int i = 0; i < length; i++) {
if(shoppingList[i] == str)
for (int j = i; j < length; j++) {
shoppingList[j] = shoppingList[j + 1];
}
}
};제거하고자 하는 값이 배열에 존재하는 경우 내부에 있는 for문에서 제거한 값 다음에 있는 값들을 한 칸씩 앞으로 당겨옵니다.
이번에는 모든 요소를 출력하는 함수를 살펴봅시다.
bool isEmpty() {
if (length == 0)
return true;
else
return false;
};
void displayAll() {
cout << "쇼핑리스트 목록입니다.\n";
for (int i = 0; shoppingList[i].size() != 0; i++) {
cout << i + 1 << ". " << shoppingList[i] << endl;
}
};
};배열을 통한 리스트의 구현이 완료되었습니다. 구현된 List를 실제 main함수에서 어떻게 사용되고 있는지 List의 구현부와 한번에 봅시다.
// c++ with array
#include<iostream>
#include<string>
using namespace std;
class List {
private:
string shoppingList[100];
int length = 0;
public:
void add(string str) {
shoppingList[length] = str;
length++;
};
void del(string str) {
if (isEmpty()) { cout << "리스트가 비어있습니다!"; return; }
for (int i = 0; i < length; i++) {
if(shoppingList[i] == str)
for (int j = i; j < length; j++) {
shoppingList[j] = shoppingList[j + 1];
}
}
};
bool isEmpty() {
if (length == 0)
return true;
else
return false;
};
void displayAll() {
cout << "쇼핑리스트 목록입니다.\n";
for (int i = 0; shoppingList[i].size() != 0; i++) {
cout << i + 1 << ". " << shoppingList[i] << endl;
}
};
};
int main() {
List list1;
cout << "쇼핑리스트에 넣을 항목을 입력하시오. (최대 100개 입력 가능, 다음 단계로 넘어가려면 q 입력)\n";
cout << "입력할 항목 : ";
for (int i = 0; i < 100; i++) {
string t;
cin >> t;
if (t == "q") break;
list1.add(t);
}
cout << "집에 있는 물건들을 살펴보고 삭제할 물건들은 삭제합시다.(다음 단계로 넘어가려면 q 입력)\n";
cout << "삭제할 항목 : ";
for (int i = 0; i < 100; i++) {
string t;
cin >> t;
if (t == "q") break;
list1.del(t);
}
cout << "장 볼 리스트를 출력합니다.\n";
list1.displayAll();
}배열로 구현했을 때의 장단점
위에서도 알 수 있듯이 배열로 구현했을 때에는 구현이 쉽고 idx 탐색이 빠르다는 장점이 있습니다.
그러나 특정 개수 이상의 요소를 List에 넣을 때 문제가 발생합니다. c++에서는 정적 할당하든 동적으로 할당하든 한번 구현된 배열은 자기의 크기를 넘어서는 값들을 더 담을 수 없기 때문입니다. 뿐만 아니라 삭제와 같은 메서드의 경우 쓰레기 공간을 비워줘야 하는 케이스가 발생하기 때문에 데이터가 삭제된 이후에도 뒤에 있던 자료들을 앞으로 당겨줘야 하기 때문에 시간복잡도가 높아지게 됩니다.
다음 포스트에서는 링크드리스트의 정의와 이를 통한 리스트adt의 구현을 확인해보도록 합시다.
