안녕하세요. C++을 다루기 위한 기본 적인 자료 구조와 코딩 테스트 등에서 응용될 수 있는 알고리즘을 알아보는 시간을 가지겠습니다.
이번 게시물은 연속된 자료 구조와 연결된 자료 구조의 차이를 간단히 설명해 보려 합니다.
1) 연속된 자료 구조
연속된 자료 구조(Continuous Data Structures)는 메모리에서 원소들이 연속적으로 배치되는 자료 구조를 의미합니다.
예를 들어, C에서 사용했던 배열이 연속된 자료 구조입니다.
연속된 자료 구조는 각 원소가 메모리에서 연속된 위치를 차지하기 때문에 인덱스를 통한 빠른 접근이 가능하고, 메모리 캐시 효율성도 높아지는 장점도 가지고 있습니다.
그러나, 크기가 고정되기 때문에 크기를 변경하기 어렵고, 원소를 삽입하거나 삭제하는 작업에는 비효율적입니다.
#include <array>
#include <iostream>
int main() {
std::array<int, 5> arr = {1, 2, 3, 4, 5};
for (const auto& element : arr) {
std::cout << element << " ";
}
return 0;
}
2) 연결된 자료 구조
연결된 자료 구조(Linked Data Structrues)는 각 원소가 메모리 어디에나 위치할 수 있는 자료 구조입니다.
대표적으로 연결 리스트(Linked List)가 연결된 자료 구조의 예시입니다.
연결된 자료 구조는 각 원소가 다음 원소를 가리키는 포인터 형태로 연결되어 있으며, 메모리 공간을 효율적으로 사용할 수 있다는 장점을 가지고 있습니다. 또한, 크기가 동적으로 조정될 수 있고 원소를 삽입하거나 삭제하는 작업에 용이합니다.
그러나, 특정 원소에 빠른 접근을 위한 탐색을 할 때는 전체 데이터를 탐색해야 하므로 원하는 데이터에 접근하기 위한 시간이 느릴 수 있습니다.
#include <iostream>
struct Node {
int data;
Node* next;
};
int main() {
// 포인터로 연결하기 위해 Node 포인터를 선언해줍니다.
Node* head = nullptr;
Node* second = nullptr;
Node* third = nullptr;
// Allocate nodes in the heap
head = new Node();
second = new Node();
third = new Node();
// Assign data values and link nodes
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = nullptr;
// Traverse the linked list
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
// Free allocated memory
delete head;
delete second;
delete third;
return 0;
}
위의 예시에서 연결된 자료 구조 중 하나인 연결 리스트를 구현하고 초기화한 후, 반복문을 사용해서 연결 리스트의 각 원소를 출력합니다.
각 노드는 자신의 데이터 값을 가지고 다음 노드를 가리키는 포인터로 연결되어 있습니다.
마지막 부분에는 동적으로 할당된 메모리를 해제해 줍니다.
3) 결론
연속된 자료 구조와 연결된 자료 구조는 각각 장단점을 가지고 있습니다.
연속된 자료 구조는 인덱스를 통한 빠른 접근과 메모리 캐시 효율성을 높여준다는 장점을 가지고 있지만, 크기 변경이 어렵고 삽입 및 삭제 작업에 비효율적입니다.
연결된 자료 구조는 동적 크기 조정이 가능하고 삽입 및 삭제 작업이 효율적이지만, 원하는 데이터를 탐색하는 시간이 느리다는 단점이 있습니다.
따라서 이와 같은 특징을 인지하고 필요한 상황에 맞춰 적절한 자료 구조를 선택해서 사용하시길 바랍니다.