1. 벡터(Vector)
벡터의 개념을 알기 위해서는 먼저, 배열을 알아야 합니다. 배열은 모두 동일한 유형을 갖는 요소들을 저장하는 데이터 구조입니다. 이 요소들은 저장 될 때 메모리에 연속적으로 저장됩니다. 즉, 요소와 요소 사이에 간격이 없이 차례로 메모리에 배치됩니다.
배열은 배열의 위치(인덱스(index))에 따라 배열 개별 요소에 효율적으로 액세스할 수 있는 간단한 데이터 구조입니다. 배열에 있는 요소의 인덱스는 배열에 있는 요소의 위치에 해당하는 음이 아닌 정수입니다. 즉, 첫 번째 요소는 인덱스가 0이고 두 번째 요소는 인덱스가 1인 식입니다. 배열의 각 요소는 배열 표기법을 사용하여 인덱스로 액세스할 수 있습니다. 예를 들어 myArray[i]는 myArray의 i번째 요소를 반환합니다.
또한 배열은 배열의 크기가 결정되는 방식에 따라 정적배열과 동적배열이 있습니다. 정적 배열에는 배열이 생성될 때 결정되는 고정 크기가 있습니다. 즉, 정적 배열의 크기는 생성된 후에 변경할 수 없습니다. 정적 배열의 모든 메모리는 배열이 생성될 때 할당되므로 매우 효율적인 데이터 구조가 됩니다.
반면에 동적 배열은 런타임 시 크기가 변경될 수 있습니다. 즉, 생성 후 크기를 수정할 수 있습니다. 이렇게 하려면 런타임에 메모리 할당 및 할당 해제가 필요하며 이는 정적 배열을 사용하는 것보다 덜 효율적일 수 있습니다. 요약하면 배열은 동일한 유형의 요소 모음을 저장하는 데이터 구조이며 인덱스를 사용하여 배열의 위치에 따라 개별 요소에 효율적으로 액세스할 수 있습니다. 배열의 크기는 고정(정적) 또는 동적(런타임 시 변경 가능)일 수 있습니다.
C++ 언어 환경에서 STL에 '벡터(Vector)'라는 컨테이너가 있습니다. 이 벡터(Vector)의 내부 구조가 동적 배열로 이루어져 있습니다. 즉, 벡터는 동적 배열이라 할 수 있습니다. 그래서 벡터를 알기 전 배열을 먼저 알아야 한다고 말씀드린 것입니다. 위에서 말한 것처럼 벡터 = 동적 배열이므로 필요에 따라 크기를 늘리거나 줄일 수 있습니다. 또한 정적 배열과 마찬가지로 벡터는 모두 동일한 유형을 가진 요소 모음을 저장하며 요소는 메모리에 연속적으로 저장됩니다.
정적 배열보다 벡터(동적 배열)를 사용하는 주요 이점 중 하나는 벡터(동적 배열)에 새 요소를 추가할 때 필요에 따라 더 많은 메모리를 할당하고 요소가 제거될 때 메모리 할당을 해제함으로써 벡터(동적 배열)가 메모리 관리를 자동으로 처리할 수 있다는 것입니다. 즉, 수동으로 메모리를 할당하고 할당 해제하는 것에 대해 걱정할 필요가 없으며 메모리 부족이나 메모리 누수를 걱정하지 않고 벡터(동적 배열)에서 요소를 추가하고 제거할 수 있습니다.
또한 벡터(동적 배열)에는 일반적으로 벡터(동적 배열)의 요소를 쉽게 사용할 수 있는 여러 가지 유용한 방법이 있습니다. 예를 들어 push_back 메서드를 사용하여 벡터의 끝에 새 요소를 추가하고, pop_back 메서드를 사용하여 벡터에서 마지막 요소를 제거하고, front 및 back 메서드를 이용해 각각 벡터의 첫 번째 요소와 마지막 요소에 액세스할 수 있습니다. 또한 size 및 capacity 메서드는 각각 벡터의 요소 수와 벡터에 할당된 메모리 양을 가져옵니다.
이점에도 불구하고 벡터(동적 배열)에는 장단점이 있으며 주로 크기 조정으로 인한 성능 저하가 있습니다. 배열의 크기를 미리 알고 있고 이가 변경되지 않을 경우 정적 배열을 사용하는 것이 좋습니다. 벡터는 복잡성은 O(1) - O(n) 시간을 가지며, 이는 연속적으로 나열된 자료구조 특성 상 빠른 접근이 가능하기 때문입니다.
2. 리스트(List)
리스트(list) 또한 배열과 같이 요소들의 집합을 저장하는 데이터 구조입니다. 배열과 마찬가지로 리스트는 메모리에 요소를 연속적으로 저장하지만, 배열과 달리 리스트는 일반적으로 고정된 크기를 갖지 않으며, 필요에 따라 크기가 증가하거나 축소될 수 있습니다. 리스트는 종종 각 요소가 리스트의 다음 요소에 대한 참조(또는 "링크")를 포함하는 요소의 선형 컬렉션인 연결된 리스트로 구현됩니다.
연결된 리스트의 각 요소는 일반적으로 "노드"라고 하며 부르며, 일반적으로 두 개의 필드를 포함합니다. 하나는 요소의 값을 저장하고 다른 하나는 다음 노드에 대한 정보(링크)를 저장합니다. 아울러 리스트의 첫 번째 노드를 리스트의 "헤드"라고 하고 리스트의 마지막 노드를 리스트의 "꼬리"라고 합니다.
리스트의 주요 장점 중 하나는 언제든지 쉽게 크기를 조정할 수 있다는 것입니다. 리스트 중간에서도 요소를 삽입하거나 삭제하는 작업은 배열보다 효율적으로 수행할 수 있습니다. 이는 배열에서 비용이 많이 드는 작업입니다. 또한 리스트는 일반적으로 리스트에 요소 추가 및 제거, 리스트에서 요소 검색, 리스트 요소 반복과 같은 일반적인 작업을 허용하는 추상 인터페이스로 구현됩니다.
리스트에는 이점이 있지만 장/단점도 있다는 점에 유의해야 합니다. 리스트는 노드 사이의 링크를 저장해야 하기 때문에 배열에 비해 메모리 오버헤드가 더 높습니다. 또한 리스트의 요소에 액세스하는 것은 복잡도는 선형 시간을 갖지만 배열에서는 일정한 시간입니다.
3. 벡터(Vector)와 리스트(List)의 차이점
벡터와 리스트는 모두 요소들의 모음을 저장하고 개별 요소에 대한 효율적인 액세스를 허용하는 데이터 구조이지만 몇 가지 중요한 차이점이 있습니다.
구현 :
벡터는 일반적으로 동적 배열로 구현됩니다. 즉, 요소들이 메모리에 연속적으로 저장하고 벡터의 크기는 필요에 따라 늘리거나 줄일 수 있습니다. 반면 리스트는 일반적으로 연결된 목록으로 구현되며 각 요소에는 목록의 다음 요소(노드)에 대한 정보(= 참조, 링크)가 포함됩니다.
메모리 :
벡터는 배열로 구현되기 때문에 벡터의 요소에 액세스하는 것은 상수 시간 복잡도를 갖는 반면, 리스트는 해당 요소[N번]에 액세스하는 것은 서로가 서로에게 연결되어 있기 때문에 노드에 노드를 타고 들어가야 합니다. 그러므로 해당 리스트 목록의 전체를 탐색해야 하기 때문에 선형 시간 복잡성이 있습니다. 반면에 벡터는 크기 조정 시 크기 변경을 처리하기 위해 추가 메모리를 예약해야 합니다. 이는 요소 간의 링크만 저장하면 되는 리스트보다 메모리 오버헤드가 더 큽니다.
삽입 및 삭제 :
벡터에서 요소를 삽입하거나 삭제하는 것은 비용이 많이 드는 작업입니다. 벡터의 용량이 부족하면 새 메모리 블록을 할당하고 이전 블록의 모든 요소를 새 블록으로 복사한 다음 이전 블록을 할당 해제해야 하기 때문입니다.
반면에 리스트에서 요소를 삽입 및 삭제하는 것은 새 노드를 생성하거나 제거하고 이웃을 연결하기만 하면 되기 때문에 상대적으로 벡터에 비해 저렴합니다.
반복 :
벡터의 요소에 대한 반복은 요소가 메모리에 연속적으로 저장되기 때문에 일반적으로 빠른 작업이므로 간단한 루프를 사용하여 요소를 순차적으로 반복할 수 있습니다. 리스트를 사용하면 각 요소 뒤에 링크가 있어야 하므로 요소에 대한 반복이 상대적으로 벡터에 비해 느려 캐시 친화적이지 않습니다.
표준 라이브러리 가용성 :
벡터는 C++에서 std::vector라고 하는 표준 템플릿 라이브러리(STL)의 일부로 사용할 수 있습니다. Java, Python 및 C#과 같은 많은 언어도 벡터와 유사한 데이터 구조를 구현합니다. 반면에 리스트는 C++의 STL에서 std::list로 사용할 수도 있습니다.
요약하면 벡터는 동적 배열로 구현되며 메모리 오버헤드가 낮고 일정한 시간 액세스가 가능하지만 요소 삽입 및 삭제 비용이 많이 듭니다. 리스트는 연결 목록으로 구현되며 메모리 오버헤드와 선형 시간 액세스가 높지만 삽입 및 삭제 비용이 저렴합니다.
'공부 > C++' 카테고리의 다른 글
| 우선순위 큐(period_queue)의 개념 (0) | 2023.01.13 |
|---|---|
| 맵(map)과 unordered_map의 개념과 차이 (0) | 2023.01.13 |
| static_cast와 dynamic_cast의 개념 및 차이점 (0) | 2023.01.10 |
| 스마트 포인터와 스마트 포인터의 종류 (0) | 2023.01.06 |
| Static과 extern의 개념 및 차이 (0) | 2022.12.29 |