[C++] 배열과 리스트, 벡터

 

 

알고리즘에 대해서 공부하기에 앞서 데이터를 저장할 수 있는 다양한 형태에 대해서 파악할 필요가 있겠다. C++에서 데이터를 다루기 위해 쓰는 컨테이너에는 배열과 리스트, 벡터가 있으며 이들은 가장 기본적이면서도 중요한 컨테이너다. 각 컨테이너는 서로 다른 특성을 가지며, 상황에 따라 적절한 선택이 필요하다. 이번 글에서는 배열, 리스트, 벡터의 차이점과 각각의 장단점을 살펴본다.

---

배열과 리스트, 벡터를 구분하는 차이점은 크기 변경 가능 여부와 삽입/삭제 속도, 메모리 구조 등이 있다.

- 배열 (Array)

배열은 고정된 크기의 연속된 메모리 블록을 사용하는 자료구조다. C++에서는 전통적인 C 스타일 배열과 std::array를 제공한다.

#include <iostream>
#include <array>
using namespace std;

int main() {
    int arr1[5] = {1, 2, 3, 4, 5};
    cout << "C Style: " << arr1[2] << endl;

    array<int, 5> arr2 = {10, 20, 30, 40, 50};
    cout << "C++ Style : " << arr2.at(2) << endl;

    return 0;
}

배열은 연속적인 메모리를 사용하기 때문에 빠른 인덱스 접근이 가능하다. 이를 시간 복잡도로 표현하면 \( O(1) \)이다. 하지만 크기가 고정되어 있어 동적으로 크기를 조절할 수 없으며, 삽입과 삭제가 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변의 값을 이동시키는 과정이 필요하다. 또한, 배열을 직접 사용할 경우 범위를 벗어난 접근을 방지하기 위한 추가적인 예외 처리가 필요하다.

C++에서 제공되는 std::array를 제공하여 이러한 단점을 어느 정도 보완할 수 있으며, at() 함수 통해 안전한 요소 접근이 가능하다.

- 리스트 (List)

리스트는 노드들이 연결된 구조(연결 리스트)로 이루어져 있으며, std::list를 사용하면 쉽게 구현할 수 있다.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList = {10, 20, 30};
    myList.push_front(5);
    myList.push_back(40);
    
    myList.pop_front();
    myList.pop_back();
    
    for (int val : myList) {
        cout << val << " ";
    }
    return 0;
}

리스트는 중간 삽입과 삭제가 빠른 것이 가장 큰 장점이다. 이는 각 노드가 독립적으로 존재하며 다음 노드를 가리키는 포인터를 포함하고 있기 때문이다. 하지만 연속된 메모리를 사용하지 않기 때문에 캐시 효율이 떨어지며, 특정 인덱스에 접근하려면 처음부터 순차적으로 탐색해야 한다. 특정 요소를 찾는 데 시간복잡도가 \( O(n) \)이다.

- 벡터 (Vector)

벡터는 배열과 유사하지만 크기를 동적으로 조절할 수 있으며, std::vector를 사용하여 구현할 수 있다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> vec = {1, 2, 3, 4, 5};
    vec.push_back(6);
    vec.pop_back();
    vec.insert(vec.begin() + 2, 10);
    vec.erase(vec.begin() + 1);
    
    for (int val : vec) {
        cout << val << " ";
    }
    return 0;
}

벡터는 내부적으로 동적 배열을 사용하며, 크기를 초과할 경우 기존 배열보다 더 큰 배열을 할당하고 데이터를 복사하는 방식으로 크기를 확장한다. 따라서 크기 증가 시 추가적인 비용이 발생할 수 있다. 하지만 연속적인 메모리를 사용하므로 캐시 효율이 높으며, 배열과 동일한 \( O(1) \)시간에 임의 접근이 가능하다.

- 어떤 컨테이너를 선택해야 할까?

컨테이너	메모리 구조	크기 변경	임의 접근	삽입/삭제 속도
배열	연속적	불가능	\( O(1) \)	\( O(n) \) (중간 삽입/삭제)
리스트	연결 리스트 (Linked-List)	가능	\( O(n) \)	\( O(1) \) (중간 삽입/삭제)
벡터	연속적	가능	\( O(1) \)	\( O(n) \) (중간 삽입/삭제)

 

빠른 인덱스 접근이 필요한 경우 벡터를 사용하고, 중간 삽입/삭제가 많다면 리스트를 사용하는 편이다. 그리고 데이터의 크기가 고정되어 있는 경우는 배열을 사용하는 식으로 기준을 만들 수 있다.

공부를 위해 이것저것 찾아봤을 때 코딩 테스트에서는 벡터를 일반적으로 많이 사용하는 것 같다. 크기 변경이 용이하면서 배열과 같은 구조를 갖는다는 것이 편리해서 그런 것 같다.

---

C언어로 펌웨어 만들거나 하는 임베디드 시스템 프로그래밍을 할 때에는 데이터의 크기를 정하고 센서나 제어 데이터를 저장하기 때문에 (+ 그나마 알고 있던게 배열이라서 다른 컨테이너를 사용할 생각조차 못해봄) 배열을 주로 사용했고, 특별한 어려움이 있거나 하지는 않았던 것 같다. 이제 리스트와 벡터도 알게 되었으니 시스템 개발을 할 때에 더 다양하게 생각할 수 있을 것 같다는 생각이 든다.