동적 메모리를 활용한 데이터 구조 구현
실습 개요
이번 실습에서는 7장에서 학습한 포인터, 동적 메모리 할당, 참조자 등의 개념을 종합적으로 적용하여 간단한 데이터 구조를 구현해보겠습니다.
이를 통해 메모리 관리와 포인터 조작 능력을 향상시킬 수 있습니다.
동적 배열 구현
먼저, 크기가 동적으로 조절되는 정수 배열을 구현해보겠습니다.
#include <iostream>
#include <stdexcept>
class DynamicArray {
private:
int* data;
int size;
int capacity;
void resize() {
int newCapacity = capacity * 2;
int* newData = new int[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
delete[] data;
data = newData;
capacity = newCapacity;
}
public:
DynamicArray(int initialCapacity = 10) : size(0), capacity(initialCapacity) {
data = new int[capacity];
}
~DynamicArray() {
delete[] data;
}
void add(int element) {
if (size == capacity) {
resize();
}
data[size++] = element;
}
int get(int index) const {
if (index < 0 || index >= size) {
throw std::out_of_range("Index out of bounds");
}
return data[index];
}
int getSize() const {
return size;
}
void print() const {
for (int i = 0; i < size; i++) {
std::cout << data[i] << " ";
}
std::cout << std::endl;
}
};
int main() {
DynamicArray arr;
for (int i = 0; i < 15; i++) {
arr.add(i * 10);
}
std::cout << "Array contents: ";
arr.print();
std::cout << "Array size: " << arr.getSize() << std::endl;
return 0;
}이 예제에서는 동적 배열을 클래스로 구현하여 메모리 관리를 캡슐화했습니다.
resize() 함수를 통해 배열의 크기를 동적으로 조절할 수 있습니다.
연결 리스트 구현
단일 연결 리스트를 구현해보겠습니다.
#include <iostream>
struct Node {
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
~LinkedList() {
Node* current = head;
while (current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
}
void add(int value) {
Node* newNode = new Node(value);
if (head == nullptr) {
head = newNode;
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
void remove(int value) {
if (head == nullptr) return;
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
while (current->next != nullptr && current->next->data != value) {
current = current->next;
}
if (current->next != nullptr) {
Node* temp = current->next;
current->next = temp->next;
delete temp;
}
}
void print() const {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " -> ";
current = current->next;
}
std::cout << "nullptr" << std::endl;
}
};
int main() {
LinkedList list;
list.add(10);
list.add(20);
list.add(30);
list.add(40);
std::cout << "Initial list: ";
list.print();
list.remove(20);
std::cout << "After removing 20: ";
list.print();
list.add(50);
std::cout << "After adding 50: ";
list.print();
return 0;
}이 연결 리스트 구현에서는 동적 메모리 할당을 사용하여 노드를 생성하고, 소멸자에서 메모리를 적절히 해제하고 있습니다.
실습
- 동적 배열 클래스에 삭제 기능을 추가하세요. 특정 인덱스의 요소를 삭제하고 배열을 재정렬하는 기능을 구현하세요.
- 연결 리스트를 이용하여 간단한 스택을 구현하세요. push와 pop 연산을 지원해야 합니다.
- 동적 배열을 사용하여 간단한 문자열 클래스를 만드세요. 문자열 연결, 부분 문자열 추출 등의 기능을 구현하세요.
주의사항
- 메모리 누수에 주의하세요. 동적으로 할당한 메모리는 반드시 해제해야 합니다.
- 댕글링 포인터와 이중 해제 문제를 피하기 위해 포인터를 null로 설정하는 습관을 들이세요.
- 예외 안전성을 고려하세요. 예외가 발생했을 때도 메모리가 적절히 해제되도록 해야 합니다.
- 깊은 복사와 얕은 복사의 차이를 이해하고, 필요에 따라 복사 생성자와 대입 연산자를 적절히 구현하세요.
참고자료
- "Introduction to Algorithms" by Thomas H. Cormen et al. (Chapter 10 : Elementary Data Structures)
- "Effective C++" by Scott Meyers (항목 13 : 자원 관리에는 객체가 그만!)
- "C++ Primer" by Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo (Chapter 13 : Copy Control)
- C++ 표준 라이브러리의 컨테이너 구현 방식 살펴보기 : C++ Standard Library Containers
- "Modern C++ Design" by Andrei Alexandrescu (Chapter 4 : Small-Object Allocation)