ArrayList와 HashSet 만들어보기.. C++
ADT (Abstract Data Type)
What은 설명하지만 How는 설명하지 않음
- What: 데이터의 속성과 행위(인터페이스)를 정의.
- How: 구현 방법은 설명 안 함. 추상적인 개념만 제공
DS (Data Structure)
What과 How가 명확함
- What + How: ADT를 실제로 구현한 것. 구체적인 메모리 구조와 알고리즘이 포함됨.
List
중복을 허용하고,
순서를 보장한다.
(내부적으로 어떻게 구현했는지 설명하지 않는다.)
Set
중복을 허용하지 않고,
순서를 보장하지 않는다.
이런 List와 Set은 ADT이다.
Array
연속적인 메모리에서 같은 종류의 아이템들을 저장할 수 있는 자료구조 (What과 How가 명확하다.)
[] 인덱스를 활용할 수 있다. (ex: items[3], size())
List는 크게 Array와 Linked node를 사용해서 구현하는 방법을 예로 들 수 있다.
List라는 ADT를 구현할 수 있는 방식이 2가지 있고,
- Array로 구현 --> ArrayList
- Linked node로 구현 --> LinkedList
==> 이렇게 List를 구현한 것을 자료구조라고 한다.
MyList와 MySet으로 ArrayList와 HashSet의 기본적인 개념을 구현해보았다.
//
// Created by Tars on 3/3/25.
//
#ifndef MYLIST_H
#define MYLIST_H
#include <iostream>
#include <stdexcept>
class MyList {
private:
int* array; // 동적 배열을 가리키는 포인터
size_t size; // 현재 요소 개수
size_t capacity; // 배열의 최대 용량
// 용량이 꽉 찼을 때 배열의 크기를 2배로 확장
void resize() {
capacity *= 2; // 용량을 2배로 늘림
int *newArray = new int[capacity]; // 새 배열 데이터 할당
for (size_t i=0; i<size; i++) { // 기존 데이터를 새 배열로 복사
newArray[i] = array[i];
}
delete[] array; // 기존 배열 메모리 해제
array = newArray; // 포인터를 새 배열로 업데이트
}
public:
// 생성자: 초기용량 4로 배열 생성
MyList() {
capacity = 4;
size = 0;
array = new int[capacity];
}
// 소멸자: 동적 할당된 메모리 해제
~MyList() {
delete[] array;
}
// 요소를 리스트 끝에 추가 (평균 O(1), resize시 O(n))
void append(int item) {
if (size == capacity) { // 용량이 꽉 차면 확장
resize();
}
array[size] = item; // 새 요소 추가
size++; // 크기 증가
}
// 인덱스 요소로 접근 O(1)
int get(size_t index) const {
if (index < size) {
return array[index];
}
throw std::out_of_range("Index is out of range"); // 잘못된 인덱스 예외
}
// 리스트 내용 출력
void print() const {
std::cout << "<";
for (size_t i = 0; i < size; i++) {
std::cout << array[i];
if (i < size - 1) std::cout << ", ";
}
std::cout << ">" << std::endl;
}
};
#endif //MYLIST_H//
// Created by Tars on 3/3/25.
//
#ifndef MYSET_H
#define MYSET_H
#include <iostream>
class MySet {
private:
static const int EMPTY = -1; // 빈 솔롯을 나타내는 값
int* table; // 해시 테이블 배열
size_t capacity; // 테이블 용량
size_t size; // 현재 요소 개수
// 간단한 해시 함수: 값을 용량으로 나눈 나머지
size_t hash(int value) const {
return static_cast<size_t>(value) % capacity;
}
// 용량이 꽉 차면 테이블 크기를 2배로 확장하고 요소 재배치
void resize() {
size_t oldCapacity = capacity;
int* oldTable = table;
capacity *= 2; // 용량 2배 증가
table = new int[capacity]; // 새 테이블 할당
size = 0; // 요소 개수 초기화
for (size_t i = 0; i < capacity; i++) {
table[i] = EMPTY; // 새 테이블을 빈 값으로 채움
}
// 기존 요소를 새 테이블에 재삽입
for (size_t i = 0; i < oldCapacity; i++) {
if (oldTable[i] != EMPTY) {
add(oldTable[i]);
}
}
delete[] oldTable; // 기존 테이블 메모리 해제
}
public:
// 생성자: 초기 용량 8로 테이블 생성
MySet() {
capacity = 8;
size = 0;
table = new int[capacity];
for (size_t i = 0; i < capacity; i++) {
table[i] = EMPTY; // 모든 솔롯을 빈 상태로 초기화
}
}
// 소멸자 : 동적 할당 된 메모리 해제
~MySet() {
delete[] table;
}
// 요소 추가 (평균 O(1), 충돌 심할 시 O(n))
void add(int value) {
if (size >= capacity * 0.75) { // 로드 팩터 0.75 초과 시 확장
resize();
}
size_t index = hash(value); // 해시값 계산
while (table[index] != EMPTY) { // 선형 탐사로 빈 솔롯 찾기
if (table[index] == value) return; // 중복이면 추가 안함
index = (index + 1) % capacity; // 다음 솔롯으로 이동
}
table[index] = value; // 빈 솔롯에 값 삽입
size++; // 크기 증가
}
// 요소 존재 여부 확인 (평균 O(1))
bool contains(int value) const {
size_t index = hash(value);
size_t start = index;
while (table[index] != EMPTY) {
if (table[index] == value) return true; // 값 발견
index = (index + 1) % capacity; // 다음 솔롯 확인
if (index == start) break; // 한 바퀴 돌면 종료
}
return false;
}
// 셋 내용 출력
void print() const {
std::cout << "{";
bool first = true;
for (size_t i = 0; i < capacity; i++) {
if (table[i] != EMPTY) {
if (!first) std::cout << ", ";
std::cout << table[i];
first = false;
}
}
std::cout << "}" << std::endl;
}
};
#endif //MYSET_H
1. MyList = ArrayList의 기본원리
공통점 :
- 동적 배열: MyList는 배열(int* array)을 기반으로 하고, 용량이 부족하면 resize()로 크기를 2배씩 늘린다. 이건 Java의 ArrayList나 C++의 std::vector가 내부적으로 동작하는 방식과 똑같다.
- 시간 복잡도:
요소 추가(append): 평균 O(1), 리사이즈 시 O(n).
인덱스 접근(get): O(1).
- 순서 유지: 추가한 순서대로 요소가 저장된다.
다른점 :
- 리사이즈 전략이나 초기 용량 설정에서 미세한 차이가 있을 수 있다. (ex: Java는 기본 용량 10, 증가율 1.5배)
- (실제 ArrayList는 제네릭(Generic) 타입을 지원해서 int뿐만 아니라 어떤 객체라도 저장할 수 있다. 위에서 구현해본 코드는 int에 특화된 버전이다..)
2. MySet = HashSet의 기본원리
공통점 :
- 해시 테이블: MySet은 해시 함수(hash())와 선형 탐사(linear probing)를 사용해서 요소를 저장하낟. 이건 Java의 HashSet이나 C++의 std::unordered_set가 내부적으로 사용하는 해시 테이블 기반 구조와 같다.
- 중복 제거: add()에서 중복 체크를 해서 같은 값은 추가 안 한다.
- 시간 복잡도:
추가(add): 평균 O(1), 충돌 심할 시 O(n).
검색(contains): 평균 O(1).
- 순서 없음: 해시값에 따라 저장 위치가 결정되니 순서가 보장되지 않는다.
다른점 :
- 충돌 처리: 간단히 선형 탐사를 썼지만, 실제 HashSet은 더 효율적인 충돌 해결 방법(ex: 체이닝이나 더 복잡한 오픈 어드레싱)을 사용할 수 있음
- (해시 함수: 위에서 작성한 hash()는 % capcity인데, 실제 구현은 더 정교한 해시 알고리즘을 써서 충돌을 최소화 한다.)
- (제네릭: HashSet도 어떤 타입이든 저장 가능하지만, 여기서는 int만 다뤘다.)
∴
ArrayList: 순서가 있고 중복을 허용하는 동적 배열 기반 리스트 (동적 배열로 List ADT를 구현한 DS)
HashSet: 순서가 없고 중복을 허용하지 않는 해시 테이블 기반 집합 (해시 테이블로 Set ADT를 구현한 DS)