솜이의 개발일기
자료구조
[c언어] ArrayList(배열리스트)의 개념과 구현 코드
developerSom 2022. 1. 22. 20:42
ArrayList(배열리스트)는 가장 간단한 자료구조인 배열로 구현한 리스트이다.
배열로 리스트를 구현하면 포인터를 이용한 연결리스트보다 탐색의 시간복잡도가 좋고(O(1)) 구현이 간단하다.
하지만 삽입과 삭제 시에 리스트 처음 또는 중간에 있는 데이터를 삽입 또는 삭제할 때 그 뒤에 있는 데이터들을 옮겨주는 작업이 필요하기에 시간복잡도가 나쁘고(O(n)) 연결리스트보다 유리하지 않다.
이해가 쉽도록 삽입 과정만 그림으로 표현하면
이렇게 표현할 수 있다.
삭제 과정의 경우에는 반대로 뒤에 있었던 data들을 뒷 쪽이 아닌 앞 쪽으로 한 칸씩 옮겨준다고 생각하면 된다.
배열로 구현한 리스트는 사실상 배열 그 자체를 리스트로 사용하는 직관적이고 간단한 자료구조이기 때문에 이해하는 데에 어려움을 겪진 않을 것이다.
배열리스트의 주요 연산
is_empty(l): list l이 비었는지를 검사
is_full(l): list l이 꽉 찼는지를 검사
get_entry(l, pos): list l의 pos 위치에 요소를 반환
print_list(l): list l의 모든 data 출력
insert(l, pos, item): list l의 pos 위치에 data를 추가
insert_last(l, item): list l의 맨 끝에 data를 추가
insert_first(l, item): list l의 맨 처음에 data를 추가
delete(l, pos): list l의 pos 위치의 data를 제거
delete_by_key(l, key): list l에서 key값을 가지는 첫번째 data를 제거
clear(l): list l의 모든 data를 제거
get_length(l): list l의 길이를 반환
replace(l, pos, item): list l의 pos 위치의 data를 item으로 변경
#배열리스트 구현 코드
#include <stdio.h> #include <stdlib.h> #define MAX_LIST_SIZE 5 typedef int element; typedef struct { element array[MAX_LIST_SIZE]; int size; }ArrayListType; void error(char* message) { fprintf(stderr, "%s\n", message); exit(1); } 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; } element get_entry(ArrayListType* L, int pos) { if (pos < 0 || pos >= L->size) error("위치 오류"); return L->array[pos]; } void print_list(ArrayListType* L) { int i; for (i = 0; i < L->size; i++) printf("%d->", L->array[i]); printf("리스트끝"); printf("\n"); } void insert_last(ArrayListType* L, element item) { if (is_full(L)) printf("리스트 오버플로우\n"); else L->array[L->size++] = item; } void insert(ArrayListType* L, int pos, element item) { int i; if (is_full(L)) printf("리스트 오버플로우\n"); else if (pos >= 0 && pos <= L->size) { for (i = (L->size - 1); i >= pos; i--) L->array[i + 1] = L->array[i]; L->array[pos] = item; L->size++; } } void insert_first(ArrayListType* L, element item) { insert(L, 0, item); } element delete(ArrayListType* L, int pos) { element item; int i; if (pos < 0 || pos >= L->size) error("위치 오류"); item = L->array[pos]; for (i = pos; i < (L->size - 1); i++) L->array[i] = L->array[i + 1]; L->size--; return item; } void clear(ArrayListType* L) { L->size = 0; } int get_length(ArrayListType* L) { return L->size; } void replace(ArrayListType* L, int pos, element item) { if (pos < 0 || pos >= L->size) error("위치 오류"); L->array[pos] = item; } int is_in_list(ArrayListType* L, element item) { int i; for (i = 0; i < L->size; i++) if (L->array[i] == item) return 1; return 0; } void delete_by_key(ArrayListType* L, element key) { int pos, i; if (is_in_list(L, key) == 0) { printf("삭제하려는 key값 %d은 리스트에 없습니다\n", key); return; } for (i = 0; i < L->size; i++) { if (L->array[i] == key) { pos = i; break; } } delete(L, pos); } int main(void) { // ArrayListType를 정적으로 생성하고 ArrayListType를 // 가리키는 포인터를 함수의 매개변수로 전달한다. ArrayListType list; init(&list); insert(&list, 0, 10); print_list(&list); // 0번째 위치에 10 추가 insert(&list, 0, 20); print_list(&list); // 0번째 위치에 20 추가 insert(&list, 0, 30); print_list(&list); // 0번째 위치에 30 추가 insert_last(&list, 40); print_list(&list); // 맨 끝에 40 추가 delete(&list, 0); print_list(&list); // 0번째 항목 삭제 return 0; }Kim's Programming
리스트(List)
리스트란 순서를 가진 항목들의 모임입니다. ADT를 정의하면 저장 형태는 데이터를 나란히 저장을 하며 저장 특성으로는 중복된 데이터의 저장을 허용한다는 것입니다. 리스트 자료구조의 ADT의 예시는 다음과 같습니다. (지정 하기 나름입니다)
- 리스트의 초기화
- 데이터 저장 (데이터 추가)
- 저장된 데이터의 탐색 및 탐색 초기화
- 다음 데이터 참조(반환)
- 바로 이전에 참조(반환)이 이루어진 데이터의 삭제
- 현재 저장되어 있는 데이터의 수 반환
그럼 이걸 C언어 함수 같이 만들어 볼까요?
- ListInit(&list) :: 리스트 초기화
- Linsert(&list, item) :: 데이터 저장
- LFirst(&list, item) :: 저장된 데이터의 탐색 및 탐색 초기화
- LNext(&list, item) :: 다음 데이터의 참조(반환)
- LRemove(&list) ::바로 이전에 참조(반환)이 이루어진 데이터의 삭제
- LCount(&list) :: 현재 저장되어 있는 데이터 수 반환
리스트를 구현하는 방법은 2가지가 있습니다.
배열을 이용하여 만드는 방법과 동적 할당을 통해서 이용하는 방법입니다. 우선 이번에는 배열을 통한 리스트 구현에 대해서 알아보겠습니다.
1차원 배열을 이용하기 때문에 다음과 같은 특징이 있습니다. 우선 1차원 배열에 항목들을 순서대로 저장합니다. 2번째는 삽입위치부터의 항목들을 뒤로 밀어 주어야 한다는 것이고 3번쨰는 삭제 연산시에 삭제를 한 자리를 비우고 다음항목들을 앞으로 당겨 줘야 합니다. 이는 배열의 특징중 중간 데이터가 빌 수 없다는 특징에 따라서 위의 경우들을 지켜주어야합니다.
배열로 만들면 어떤게 좋고 어떤게 안좋을까요? 다음과 같이 나눠봤습니다.
- 장점
- 구현이 간단하다
- 인덱스 값 기준으로 어디든 한 번에 참조 가능(3번 자료! -> 2번 배열!) -> 데이터 참조가 쉬움
- 단점
- 삽입, 삭제 시 오버헤드 : 삽입 및 삭제 과정에서 데이터 이동(복사)가 매우 빈번하게 일어남
- 항목의 개수 제한 : 배열의 길이는 초기에 결정하고 변경할 수 없기 때문에 유한적인 데이터만 넣을 수 있다.
이제 특징과 장단점도 알아봤으나 구현을 해보겠습니다. 배열로 구현을 하기 위하여 순차 리스트 구조체를 다음과 같이 썼습니다..
typedef struct ListArray { int Array[MAX_SIZE];//배열의 크기 int length = 0;//배열에 저장된 항목 개수 }ListArray; | cs |
앞으로의 자료구조가 그렇듯 꼭 같을 필요는 없습니다. 구현해보는 것이기 때문에 데이터 참조위치 변수를 더 추가한다거나 할 수도 있습니다.
저는 배열로 리스트를 구현할 때 다음의 ADT들을 구현하였습니다.
void Add_First(ListArray *L, int Value)//배열 리스트의 가장 처음 데이터를 추가 void Add(ListArray *L, int Value, int POSITION)//배열 리스트의 특정 위치에 데이터를 추가 void Add_Last(ListArray *L, int Value)// 배열 리스트의 제일 마지막에 데이터를 추가 void Erase(ListArray *L, int POSITION)//배열 리스트의 특정 위치의 데이터를 삭제 void Array_Clear(ListArray *L)// 배열 리스트의 모든 데이터를 없앰 void Find_Value(ListArray *L, int VALUE)// 특정값을 배열 리스트에서 찾음 int Replace(ListArray *L, int POSITION, int VALUE)//배열 리스트의 특정 위치의 값을 다음 값으로 바꿈 void Return_length(ListArray *L)// 배열 리스트의 총 길이를 보여줌 void is_Full(ListArray *L)//배열 리스트가 가득 찾는지를 확인 void is_Empty(ListArray *L)//배열 리스트가 비엇는지를 확인 void Output(ListArray *L)//현재 배열 리스트에 있는 데이터를 순차적으로 모두 출력 | cs |
다른 기능을 구현해도 좋지만 제가 한 것들 하나씩 살펴보겠습니다.
- 배열 리스트의 가장 처음 데이터 추가
void Add_First(ListArray *L, int Value)
{
if (L->length >= 100)
cout << "Can not add Value in List any more." << endl;
else
{
L->Array[L->length] = Value;
L->length += 1;
}
}
cs 배열 리스트를 만들고 데이터를 처음 넣을 때 사용하는 ADT입니다. 사실 배열에서는 별로 의미는 없긴 한데 동적 할당을 통한 리스트 구현시에는 의미가 있기 떄문에 그래도 배열에서도 ADT를 만들 어 봤습니다. 이 ADT는 가득 찾는지 길이를 통해서 알아본 뒤 (사실 제일 처음 데이터를 넓는 것이기 때문에 필요없긴 합니다.) 그 다음 배열의 첫번지에 데이터를 넣어주고 길이를 1증가 시키는 ADT입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Add(ListArray *L, int Value, int POSITION)
{
if (L->length >= 100)// 가득 찼는지 검사
{
cout << "Can not add Value in List any more." << endl;
return;
}
if (L->length < POSITION)
{
Add_Last(L,Value);
return;
}
for (int i = L->length; i > POSITION; i--)
{
L->Array[i] = L->Array[i - 1];// 특정 위치부터 한칸씩 뒤로 밀어줌
}
L->Array[POSITION] = Value;
L->length += 1;
}
cs 리스트 배열을 생성후 첫 데이터를 넣은 이후의 모든 데이터는 이것으로 넣을 수 있습니다. Add_First와는 다르게 위치도 지정해서 넣을 수 있습니다. 예외 처리 검사를 합니다. 3~7번째 줄에서는 ListArray 구조체의 length를 검사하여 배열이 가득 찼는지를 확인합니다. 가득 차지 않았다면 다음은 지정 위치를 검사합니다. 만약 배열 6까지 차있는데 18번쨰 위치를 지정하였다면 위치가 어찌됐던 7번째에 넣을 수 밖에 없기 떄문에(배열의 특성상) 마지막에 넣는 Add_Last ADT를 호출해줍니다. 모든 예외 검사를 통과 해 줬다면 for문을 이용하여 들어갈 위치뒤에 모든 데이터 들을 한칸씩 밀어주며 다 밀어준뒤 빈자리에 원하는 데이터를 넣어주는 ADT 입니다. 데이터를 추가했다면 마지막에 길이를 하나 더해줍니다.
void Add_Last(ListArray *L, int Value)
{
if (L->length >= 100)
{
cout << "Can not add Value in List any more." << endl;
return;
}
else
L->Array[L->length] = Value;
}
cs 리스트 배열의 가장 마지막 (리스트의 가장 마지막에 있는 데이터 바로뒤)에 데이터를 넣어주는 ADT입니다. 이 ADT는 배열 전체를 움직이거나 할 필요가 없습니다. (배열 중간에가 비면 땡겨야 하지만 제일 마지막에 들어오는 것은 그냥 입력만 하면 되기 떄문) 그래도 살펴 보겠습니다. 간단하게 예외 처리를 해줍니다. 꽉 찼으면 더이상 넣을 수 없으므로 이를 확인해 주는 것입니다. 만약 꽉 차있지 않다면 마지막에 값을 대입하여 줍니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Erase(ListArray *L, int POSITION)
{
if (L->length == 0)
{
printf("List is empty.\n");
return;
}
if (POSITION > L->length)
{
printf("there is no data\n");
return;
}
for (int i = POSITION - 1; i < L->length - 1; i++)
{
L->Array[i] = L->Array[i + 1];
}
L->length -= 1;
}
cs 리스트 배열에 있는 데이터들 중 특정한 위치의 데이터를 삭제하는 ADT입니다. 삭제시에는 추가와는 반대로 뒤로 밀어 주는 것이 아니라 삭제되는 데 까지 차례 차례 앞으로 당겨서 삭제 된 부분을 매꿔주어야 합니다. Erase ADT는 우선 예외 사항부터 검색하여 줍니다. length를 조사하여 비었는지, 값은 5번 배열 까지만 들어가있는데 혹시나 7번 값을 삭제하라고는 하지 않는지를 조사합니다. 조사가 끝난뒤에 삭제될 데이터는 앞으로 한칸씩 삭제위치 까지 당겨서 메꿔주고 전체길이를 하나 줄이는 ADT입니다.
void Array_Clear(ListArray *L)
{
L->length = 0;
}
cs 사실 별거 없는 ADT입니다. 위에 것들을 보시면서 아셨는지는 모르겠지만 이 배열 리스트는 Length 라는 변수를 통해 제한되고 이동하고 하고 있습니다. 그렇기 떄문에 이것만 날려주면 배열에 데이터가 있던 없던 없는걸로 취급 됩니다. 뭐.. 마치 free를 안한 동적할당 메모리 같은 거라고 할까요?
void Find_Value(ListArray *L, int VALUE)
{
for (int i = 0; i < L->length - 1; i++)
if (L->Array[i] == VALUE)
cout << "입력값 " << VALUE << "가 " << i << "번째 배열에서 발견됐습니다." << endl;
}
cs 이 ADT는 모든 배열의 요소(데이터가 있는 배열부에서만) 을 모두 일일이 비교해가면서 어느 위치에 그 값이 있는 지를 찾아주는 ADT입니다.
배열 리스트의 특정 위치의 데이터를 다른 데이터로 바꿈
역시나 단순하게 위치를 넘겨받아서 그 위치에 맞는 배열 칸에 데이터를 넣어줍니다.
리스트 구조체의 length값을 출력하여 길이를 출력시켜주는 ADT입니다.
void is_Full(ListArray *L)
{
if (L->length < 100)
cout << "this List is not FULL" << endl;
else
cout << "this List is FULL" << endl;
}
void is_Empty(ListArray *L)
{
if (L->length < 100)
cout << "this List is not FULL" << endl;
else
cout << "this List is FULL" << endl;
}
cs 꽉 차있나 비었나를 확인합니다. 역시나 여기서도 구조체 내부 Length 변수를 활용하여 데이터의 상태를 알려줍니다.
void Output(ListArray *L)
{
for (int i = 0; i < L->length; i++)
cout << L->Array[i] << " ";
cout << endl;
}
cs 리스트 배열의 모든 데이터들은 하나하나 읽어가며 그 데이터 값을 출력해 줍니다.
위의 모든 ADT를 구현한 프로젝트 파일입니다. 참고하실분은 참고하세요!
->
같이 보기