배열 리스트 (Array List)
배열의 한계와 동적 배열의 필요성
우리가 배열을 처음 배운 이유는 변수를 하나씩 선언하는 번거로움을 줄이기 위해서였다.
예를 들어 100개의 값을 student1, student2, …처럼 일일이 선언하는 대신 student[100]처럼 하나의 배열로 묶을 수 있다.
이렇게 배열을 사용하면 같은 자료형의 값을 하나의 이름으로 묶어 관리할 수 있다.
처음에는 별다른 생각 없이 사용했지만, 사실 배열은 우리가 가장 먼저 접하는 자료구조 중 하나다.
자료구조란 자료를 특정한 구조로 저장하고 관리하는 방식을 말한다.
배열은 같은 자료형의 값을 메모리에 연속해서 배치하고, 각 위치를 인덱스로 구분한다.
이 구조 덕분에 인덱스만 알면 원하는 위치의 값에 빠르게 접근할 수 있다.
이처럼 배열은 단순하고 빠르지만, 사용하다 보면 불편한 점이 있다.
바로 선언할 때 크기를 미리 정해야 하고, 한 번 정한 크기는 나중에 바꿀 수 없다.
처음부터 자료의 개수를 정확히 알기도 어렵고, 안다고 하더라도 나중에 공간이 더 필요해질 수 있다.
그래서 배열을 작게 선언하면 공간이 부족하고, 크게 선언하면 공간이 낭비되니 처음부터 적절한 크기를 정하기가 쉽지 않다.
동적 배열을 이용하면 이 문제를 해결할 수 있다.
동적 배열은 리스트를 구현하는 방법 중 하나이므로, 먼저 리스트가 무엇인지 알아보자.
리스트와 동적 배열의 관계
리스트(List)는 원소의 순서를 유지하면서 저장하고, 접근·삽입·삭제와 같은 연산을 정의한 추상 자료형(Abstract Data Type, ADT)이다.
리스트는 어떤 연산을 제공하는지만 정할 뿐, 데이터를 실제로 어떻게 저장할지는 정하지 않는다.
따라서 정해진 연산만 제공한다면 구체적인 구현 방법은 자유롭게 선택할 수 있다.
리스트를 구현하는 대표적인 방법에는 배열 기반 리스트(Array-based List)와 연결 리스트(Linked List)가 있다.
배열 기반 리스트는 고정 크기 배열(Fixed-size Array)로 구현하거나, 필요할 때 크기를 늘리는 동적 배열(Dynamic Array)로 구현할 수 있다.
각 개념의 관계를 나타내면 다음과 같다.
리스트 (List)
|-- 배열 기반 리스트 (Array-based List)
| |-- 고정 크기 배열 (Fixed-size Array)
| |-- 동적 배열 (Dynamic Array)
|-- 연결 리스트 (Linked List)이 글에서는 동적 배열을 이용해 리스트를 구현하고, 배열의 크기를 늘리거나 데이터를 순회하고 삭제하는 과정을 살펴본다.
먼저 소스 코드를 확인한 뒤, 주요 기능이 어떻게 동작하는지 하나씩 알아보자.
소스 코드
main.c
// main.c
#include <stdio.h>
#include <stdlib.h>
#include "array_list.h"
void print_list(List* list)
{
ListData data;
printf("List (size: %d, capacity: %d)\n", list_size(list), list_capacity(list));
printf(" data: ");
if (list_first(list, &data))
{
printf("%d", data);
while (list_next(list, &data))
printf(", %d", data);
}
printf("\n");
}
int main(void)
{
List list;
ListData data;
/* 1. Initialize the list. */
list_init(&list);
printf("1) Empty list\n");
print_list(&list);
/* 2. Append data. The capacity grows automatically when necessary. */
list_append(&list, 10);
list_append(&list, 20);
list_append(&list, 30);
list_append(&list, 40);
printf("\n2) After appending 10, 20, 30, and 40\n");
print_list(&list);
/* 3. Prepend data and insert data at a specified index. */
list_prepend(&list, 5);
list_insert_at(&list, 3, 25);
printf("\n3) After prepending 5 and inserting 25 at index 3\n");
print_list(&list);
/* 4. Read data by index. */
if (list_get(&list, 3, &data))
{
printf("\n4) Data at index 3: %d\n", data);
}
/* 5. Remove data by index and receive the removed value. */
if (list_remove_at(&list, 2, &data))
{
printf("\n5) Removed data at index 2: %d\n", data);
print_list(&list);
}
/* 6. Iterate with the cursor and remove every value of 30 or greater. */
if (list_first(&list, &data))
{
do
{
if (data >= 30)
{
list_remove_current(&list, &data);
}
}
while (list_next(&list, &data));
}
printf("\n6) After removing values greater than or equal to 30\n");
print_list(&list);
/* 7. Release the dynamically allocated memory. */
list_destroy(&list);
return EXIT_SUCCESS;
}array_list.h
// array_list.h
#ifndef ARRAY_LIST_H
#define ARRAY_LIST_H
#include <stdbool.h>
#define LIST_INITIAL_CAPACITY 2
typedef int ListData;
typedef struct ArrayList
{
ListData* arr;
int capacity;
int size;
int cursor;
} ArrayList;
typedef ArrayList List;
bool list_init(List* list);
void list_destroy(List* list);
int list_capacity(const List* list);
int list_size(const List* list);
/* Insertion operations */
bool list_prepend(List* list, ListData data);
bool list_append(List* list, ListData data);
/* Index-based operations */
bool list_get(const List* list, int index, ListData* out_data);
bool list_insert_at(List* list, int index, ListData data);
bool list_remove_at(List* list, int index, ListData* out_data);
/* Cursor-based iteration */
bool list_first(List* list, ListData* out_data);
bool list_next(List* list, ListData* out_data);
bool list_remove_current(List* list, ListData* out_data);
#endif /* ARRAY_LIST_H */array_list.c
// array_list.c
#include <stdlib.h>
#include <string.h>
#include "array_list.h"
bool list_init(List* list)
{
list->arr = malloc(sizeof(ListData) * LIST_INITIAL_CAPACITY);
if (list->arr == NULL)
return false;
list->capacity = LIST_INITIAL_CAPACITY;
list->size = 0;
list->cursor = -1;
return true;
}
void list_destroy(List* list)
{
free(list->arr);
list->arr = NULL;
list->capacity = 0;
list->size = 0;
list->cursor = -1;
}
int list_capacity(const List* list)
{
return list->capacity;
}
int list_size(const List* list)
{
return list->size;
}
bool list_get(const List* list, int index, ListData* out_data)
{
if (index < 0 || index >= list->size || out_data == NULL)
return false;
*out_data = list->arr[index];
return true;
}
bool list_prepend(List* list, ListData data)
{
return list_insert_at(list, 0, data);
}
bool list_append(List* list, ListData data)
{
return list_insert_at(list, list->size, data);
}
bool list_insert_at(List* list, int index, ListData data)
{
if (index < 0 || index > list->size)
return false;
if (list->size >= list->capacity)
{
int new_capacity = list->capacity * 2;
ListData* new_arr = malloc(sizeof(ListData) * new_capacity);
if (new_arr == NULL)
return false;
memcpy(new_arr, list->arr, sizeof(ListData) * list->size);
free(list->arr);
list->arr = new_arr;
list->capacity = new_capacity;
}
for (int i = list->size; i > index; i--)
{
list->arr[i] = list->arr[i - 1];
}
list->arr[index] = data;
list->size++;
if (index <= list->cursor)
list->cursor++;
return true;
}
bool list_remove_at(List* list, int index, ListData* out_data)
{
if (index < 0 || index >= list->size || out_data == NULL)
return false;
*out_data = list->arr[index];
for (int i = index; i < list->size - 1; i++)
list->arr[i] = list->arr[i + 1];
list->size--;
if (index <= list->cursor)
list->cursor--;
return true;
}
bool list_first(List* list, ListData* out_data)
{
if (list->size <= 0)
return false;
list->cursor = 0;
*out_data = list->arr[0];
return true;
}
bool list_next(List* list, ListData* out_data)
{
if (list->cursor + 1 >= list->size)
return false;
list->cursor++;
*out_data = list->arr[list->cursor];
return true;
}
bool list_remove_current(List* list, ListData* out_data)
{
return list_remove_at(list, list->cursor, out_data);
}동적 배열의 구조와 확장
구조체 ArrayList는 원소를 저장할 배열과 배열의 상태를 관리하는 값으로 구성된다.
이 예제에서는 typedef를 사용해 ArrayList를 List라는 이름으로도 사용할 수 있게 했다.
arr는 동적으로 할당한 배열을 가리키고, capacity는 현재 배열에 저장할 수 있는 원소의 최대 개수를 나타낸다.
size는 실제로 저장된 원소의 개수이며, cursor는 원소를 순회할 때 현재 위치를 나타낸다.
앞에서 말했듯이 배열은 한 번 정한 크기를 나중에 바꿀 수 없다.
따라서 동적 배열은 size가 capacity에 도달하면 더 큰 배열을 새로 할당하고,
기존 원소를 모두 복사한 뒤 기존 배열을 메모리에서 해제하고 새 배열을 사용한다.
저장 공간이 부족할 때마다 이 과정이 반복되어 원소를 저장할 공간이 자동으로 늘어난다.
이 예제에서는 배열이 확장되는 과정을 쉽게 확인할 수 있도록 초기 capacity를 일부러 작게 설정했다.
시간 복잡도
앞서 리스트를 동적 배열로 구현했으므로, 이 리스트의 시간 복잡도는 배열의 특성을 따른다.
이후 언급하는 리스트는 동적 배열로 구현한 리스트를 의미한다.
조회
배열은 원소를 메모리에 연속해서 저장하므로 인덱스만 알면 원소에 바로 접근할 수 있다.
따라서 인덱스로 원소에 접근하는 시간 복잡도는 O(1)이다.
삽입
배열의 처음이나 중간에 원소를 삽입하려면 먼저 삽입할 위치에 빈 공간을 만들어야 한다.
삽입할 위치에 새 값을 곧바로 대입하면 그 자리에 있던 기존 값이 덮어써진다.
따라서 기존 값을 보존하려면 삽입 위치 이후의 원소를 한 칸씩 뒤로 옮겨야 한다.
최대 n개의 원소를 옮겨야 하므로 처음이나 중간에 삽입하는 시간 복잡도는 O(n)이다.
배열의 마지막에 원소를 삽입할 때는 기존 원소를 옮길 필요가 없으므로, 저장 공간이 충분하다면 O(1)에 새 원소를 저장할 수 있다.
반면 저장 공간이 부족하면 더 큰 배열을 할당하고 기존 원소를 모두 복사해야 한다.
이때 기존 원소 n개를 복사해야 하므로 마지막 삽입이라도 최악의 경우 O(n)이 걸린다.
삭제
리스트의 유효한 범위 안에서는 원소 사이에 빈 공간이 없어야 한다.
따라서 원소를 삭제하는 방법은 그 뒤에 있는 원소들을 한 칸씩 앞으로 옮기는 것이다.
이 과정이 끝나면 내부 배열의 마지막 두 칸에 같은 값이 남지만, size를 하나 줄이면 마지막 칸이 리스트의 유효한 범위에서 제외되므로 안전하다.
원소가 n개인 리스트에서 인덱스 i의 원소를 삭제하면 n - 1 - i개의 원소를 옮겨야 한다.
처음이나 중간에서 삭제하는 시간 복잡도는 O(n)이다.
반면 마지막 원소를 삭제할 때는 옮길 원소가 없으므로 size만 줄이면 되어 O(1)에 동작한다.