자료구조와 컨테이너의 차이
- 자료구조 (Data Structure)
- 데이터를 저장하고 관리하는 구조적 방법론입니다.
- 배열, 링크드 리스트, 스택, 큐, 해시 테이블, 트리, 그래프 등이 자료구조에 포함됩니다.
- 자료구조는 데이터의 구현 원리와 알고리즘에 더 초점이 맞춰져 있습니다.
- 컨테이너 (Container)
- 데이터를 저장하고 관리하는 도구입니다.
- 예를 들어 C++ 표준 라이브러리(STL)에서 제공하는 컨테이너는 주로 여러 자료구조를 추상화하여 사용하기 쉽게 만든 것입니다. 벡터, 리스트, 덱, 맵, 셋 등이 포함됩니다.
- 컨테이너는 자료구조를 기반으로 동작하지만, 사용자 입장에서는 이를 직접 구현할 필요 없이 고수준의 인터페이스를 사용하면 됩니다.
자료구조는 데이터를 효율적으로 저장하고 관리하는 방법을 제공하는 구조입니다. 각 자료구조는 특정 작업을 수행할 때 더 빠르고 효율적인 성능을 제공합니다. 자료구조는 크게 선형 자료구조, 비선형 자료구조, 그 외로 나눌 수 있으며, 그 안에도 다양한 유형이 존재합니다. 여기서는 대표적인 자료구조들의 종류와 특징을 소개합니다.
1. 선형 자료구조 (Linear Data Structures)
선형 자료구조는 데이터가 일렬로 배열되어 있어 순차적으로 접근할 수 있는 구조입니다. 주요한 선형 자료구조는 다음과 같습니다.
1.1. 배열 (Array)
- 특징: 고정된 크기의 데이터 요소들이 연속적인 메모리 공간에 저장됩니다. 각 요소는 인덱스를 통해 접근할 수 있습니다.
- 장점: 인덱스를 통한 빠른 접근이 가능합니다.
- 단점: 크기가 고정되어 크기 변경이 어렵고, 삽입 및 삭제 시 이동이 필요합니다
1.2. 리스트 (List)
- 특징: 순차적으로 연결된 데이터 요소들을 저장하는 자료구조입니다. 동적 크기 조정이 가능하고, 요소 간 연결은 포인터로 관리됩니다.
- 종류:
- 단일 연결 리스트 (Singly Linked List): 각 노드가 다음 노드에 대한 포인터만 갖습니다.
- 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전 노드와 다음 노드에 대한 포인터를 갖습니다.
- 원형 연결 리스트 (Circular Linked List): 마지막 노드가 첫 번째 노드를 가리키는 구조입니다.
1.3. 스택 (Stack)
- 특징: 후입선출(LIFO, Last In First Out) 구조로, 마지막에 들어간 요소가 먼저 나옵니다.
- 주요 연산: push() (삽입), pop() (삭제), top() (최상위 요소 확인)
- 사용 예: 함수 호출 스택, 후위 표기법 계산 등
1.4. 큐 (Queue)
- 특징: 선입선출(FIFO, First In First Out) 구조로, 먼저 들어간 요소가 먼저 나옵니다.
- 주요 연산: enqueue() (삽입), dequeue() (삭제), front() (첫 번째 요소 확인)
- 종류:
- 일반 큐 (Queue): 기본적인 FIFO 큐
- 우선순위 큐 (Priority Queue): 우선순위가 높은 요소가 먼저 나오는 큐
- 덱 (Deque, Double Ended Queue): 양쪽 끝에서 삽입과 삭제가 가능한 큐
2. 비선형 자료구조 (Non-linear Data Structures)
비선형 자료구조는 데이터가 계층적 또는 그래프 형태로 연결된 자료구조입니다. 이 구조에서는 데이터를 직선 형태로 순차적으로 처리할 수 없습니다.
2.1. 트리 (Tree)
- 특징: 계층적 관계를 가지는 자료구조로, 각 노드가 여러 자식을 가질 수 있습니다. 트리는 루트 노드에서 시작하여 여러 가지 경로를 통해 자식 노드로 이어집니다.
- 종류:
- 이진 트리 (Binary Tree): 각 노드는 최대 2개의 자식을 가질 수 있습니다.
- 이진 검색 트리 (Binary Search Tree, BST): 이진 트리의 일종으로, 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 값을 가집니다.
- 힙 (Heap): 트리의 일종으로, 부모 노드의 값이 자식 노드의 값보다 큰(최대 힙) 또는 작은(최소 힙) 특성을 가집니다.
- AVL 트리: 균형 잡힌 이진 검색 트리로, 트리의 균형을 유지하는 특성이 있습니다.
- B-트리, B+트리: 데이터베이스 및 파일 시스템에서 사용되는 트리 구조입니다.
2.2. 그래프 (Graph)
- 특징: 노드(정점)와 그 노드를 연결하는 간선(엣지)로 구성된 자료구조입니다. 노드 간의 관계를 표현하는 데 사용됩니다.
- 종류:
- 방향 그래프 (Directed Graph): 간선이 방향을 갖는 그래프
- 무방향 그래프 (Undirected Graph): 간선이 방향이 없는 그래프
- 가중치 그래프 (Weighted Graph): 간선에 가중치가 부여된 그래프
- 단방향 그래프 (DAG, Directed Acyclic Graph): 방향 그래프이면서 순환이 없는 그래프
3. 해시 테이블 (Hash Table)
- 특징: 키-값 쌍을 저장하는 자료구조로, 키를 해시 함수를 통해 해시값으로 변환하여 빠르게 데이터를 검색할 수 있습니다.
- 장점: 평균적으로 매우 빠른 검색 속도를 제공합니다.
- 단점: 충돌(collision)이 발생할 수 있으며, 이를 처리하는 방법(체이닝, 개방 주소법 등)이 필요합니다.
4. 집합 (Set)
- 특징: 중복을 허용하지 않는 데이터 구조로, 특정 요소의 존재 여부를 빠르게 확인할 수 있습니다.
동적 자료구조와 정적 자료구조
- 동적 자료구조: 크기가 동적으로 변화할 수 있는 자료구조입니다. 예를 들면 연결 리스트, 동적 배열 등이 있습니다.
- 정적 자료구조: 크기가 고정된 자료구조입니다. 예를 들면 정적 배열이 있습니다.
결론
각 자료구조는 특정 작업을 효율적으로 처리하기 위해 설계되었습니다. 예를 들어, 스택은 후입선출(LIFO) 방식으로 동작하며, 큐는 선입선출(FIFO) 방식으로 동작합니다. 트리나 그래프는 계층적 또는 복잡한 관계를 모델링할 때 유용합니다. 자료구조의 선택은 문제의 특성에 따라 달라지며, 각 자료구조의 장단점을 잘 이해하고 적절한 선택을 해야 합니다.