C++로 구현하는 자료구조 (1) - ArrayList

C++로 구현하는 자료구조

 

나는 C++와 같은 unmanaged 언어를 실무에서 다뤄볼 수 있는 기회가 지금까지 없었다. 컴퓨터 공학의 기본기를 익히기 위해서 C/C++같은 언어를 꾸준히 수련하는 것이 필요하다고 생각되어 이 포스팅을 시작해보려고 한다. C++로 기본적인 자료구조를 구현해보면서 컴퓨터 공학의 기본기를 수련해보자!

 

---

1. ArrayList (동적배열)

오늘의 주제는 동적배열이다. 동적배열은 크기가 가변적으로 늘어나는 배열이다. 초기화한 배열의 크기가 모자르게 되면 현재 배열보다 2배 큰 배열을 할당하고, 기존에 있던 값을 복사한다. 이렇게 배열크기를 조정하면 삽입과 인덱스 접근에서 시간복잡도 O(1)을 보장할 수 있다. 여기서 중요하게 볼 점은 동적배열의 크기가 입력에 비례해서 커진다는 점이다. 그렇기 때문에 입력과 대비해서 복사연산을 상대적으로 O(1)로 볼 수 있다.

 

2. 구현소스

구현은 헤더파일과 실행파일로 나누어 구현했다. 앞으로 헤더에는 자료구조를 구현한 class가, 실행파일에서는 자료구조를 테스트 해보는 방식으로 설명을 해보려고 한다.

 

// 파일명: ArrayList.h
#pragma once

template <typename T>
class ArrayList {
private:
    int currentSize = 0;
    int containerSize = 2;
    T* container;
public:
    ArrayList() {
        this->container = new T[this->containerSize];
    }

    void add(const T& element) {
        if (this->currentSize >= this->containerSize) {
            this->containerSize *= 2;
            T* tmp = new T[this->containerSize];

            int idx = 0;
            for (int i = 0; i < this->currentSize; i++) {
                tmp[idx] = this->container[i];
                idx++;
            }

            delete[] this->container;
            this->container = tmp;
        }

        this->container[this->currentSize] = element;
        this->currentSize++;
    }

    void pop_back() {
        this->currentSize--;
    }

    T get(const int& index) {
        return this->container[index];
    }
    
    int size() {
        return currentSize;
    }

    ~ArrayList() {
        delete[] container;
    }
};

앞서 설명한 바와 같이 add 메서드에서 현재 크기보다 큰 공간이 필요하다면 복사를 수행한다. 복사할 사이즈는 2배씩 커져가면서 크기를 충분히 확보한다.

 

#include "datastructure/ArrayList.h"
#include <iostream>
#include <string>

using namespace std;

int main() {

    ArrayList<string>* list = new ArrayList<string>();
    
    for (int i = 0; i < 5; i++)
        list->add("test");

    list->pop_back();

    for (int i = 0; i < list->size(); i++)
        cout << list->get(i) << endl;

    return 0;
}

실제로 테스트해보면 초기 크기를 2로 설정했는데도 크기가 늘어남을 알 수 있다. 뒤에 있던 요소를 제거하는 메소드는 현재크기를 1씩 줄이는 방식으로 구현해봤다.