자료구조와 동적할당
자료구조란?
Data Structure - 자료들을 저장하는 방법•
목적: 여러가지 자료를 저장하는 방법을 배우고, 많은 프로그램에 적절한 구조를 적절하게 적합한 자료구조를 선택해서 사용하려면 된다
•
프로그램 효율성: 실행 속도와 메모리 효율이 전체적으로 좌우될 수도 있다
•
대표적인 자료구조: 배열, 링크드리스트, 큐, 스택, 그래프, 트리
노드(Node)
데이터를 저장하는 최소 단위•
배열에서 노드: 각각의 번호(인덱스)를 뜻한다
•
시각적 표현:
배열: [5][3][6][2][1] ← 각 칸이 노드
Plain Text
복사
연결리스트(Linked List)
노드가 노드를 가르키고 있는 자료구조•
특징: 여러개의 노드로 이루어져 있다
•
연결 방식: 연결리스트 한 노드가 노드를 가르키는데, 그 한개를 노드라고 한다
•
구조체 포인터: 클래스 포인터를 이용해서 구현한다
연결리스트: [5]→[3]→[6]→[2]→[1]
Plain Text
복사
배열 vs 연결리스트
배열의 단점
크기 제한 문제•
10칸 짜리 배열을 만들었는데 내가 데이터를 12개를 쓰고싶다
•
심지어다. 12칸짜리 배열을 만들어서 복사해주면된다
•
그 과정이 번거이 너무 많아서기 때문에 비효율적이다
연결리스트의 장점
유연한 메모리 사용•
연결리스트는 실행도중에 추가적으로 데이터를 추가해도 큰 부담이 없다
•
노드만 생성해주고 추소만 연결해주면 되니까
•
중간에 데이터를 삽입하거나 삭제해도 큰 부담이 없다
핵심: 연결리스트를 써야 할때는 실행도중에 데이터가 자주 삽입되거나 삭제될때 사용하면 좋다.메모리의 동적 할당(Dynamic Allocation)
프로그램 실행 중에 메모리를 할당받는 것정적 할당 vs 동적 할당
•
정적 할당: 데이터 영역과 스택 영역에 할당되는 메모리의 크기는 컴파일 타임(compile time)에 미리 결정된다
•
동적 할당: 하지만 힙 영역의 크기는 프로그램이 실행되는 도중인 런 타임(run time)에 사용자가 직접 결정하게 된다
메모리 구조
new 연산자
C++에서 동적 메모리를 할당하는 연산자기본 문법
타입* 포인터이름 = new 타입;
C++
복사
특징 및 장점
•
C언어: malloc() 함수를 사용하여 동적 할당
•
C++: 더 나은 방법인 new 연산자를 이용한 방법을 제공하고 있습니다
•
C++에서 new 연산자: 다음과 같은 문법으로 사용합니다
메모리 할당 위치
•
new 연산자: 자유 기억 공간(free store)이라고 불리는 메모리 공간(memory pool)에 객체를 위한 메모리를 할당받습니다
•
특징: new 연산자를 통해 할당받은 메모리는 따로 이름이 없으므로 해당 포인터로만 접근할 수 있게 됩니다
delete 연산자
동적으로 할당받은 메모리를 해제하는 연산자기본 사용법
delete 포인터이름;
C++
복사
중요성
•
C언어: free() 함수를 이용하여 동적으로 할당받은 메모리를 다시 운영체제로 반환합니다
•
C++: delete 연산자를 사용하여, 더는 사용하지 않는 메모리를 다시 메모리 공간에 돌려줄 수 있습니다
•
메모리 누수 방지: C++에서 delete 연산자는 다음과 같은 문법으로 사용합니다
실제 코드 예제
기본 동적할당 예제
#include <iostream>
using namespace std;
int main()
{
// int 타입 동적 할당
int* ptr_int = new int;
*ptr_int = 100;
// double 타입 동적 할당
double* ptr_double = new double;
*ptr_double = 100.123;
// 값 출력
cout << "int형 숫자의 값은 " << *ptr_int << "입니다." << endl;
cout << "int형 숫자의 메모리 주소는 " << ptr_int << "입니다." << endl;
cout << "double형 숫자의 값은 " << *ptr_double << "입니다." << endl;
cout << "double형 숫자의 메모리 주소는 " << ptr_double << "입니다." << endl;
// 메모리 해제 (중요!)
delete ptr_int;
delete ptr_double;
return 0;
}
C++
복사
Node 동적할당 예제
struct Node
{
int data;
Node* next;
};
int main()
{
Node node; // 스택에 생성된 노드
// 동적으로 노드 생성
Node* pp = new Node;
pp->data = 3;
delete pp; // 메모리 해제
return 0;
}
C++
복사
동적할당 노드 하드코딩
struct Node
{
int data;
Node* next;
};
int main()
{
// 🔗 추가 확장이 매우 편리해진다
Node* head;
// 3개의 노드를 동적으로 생성하고 연결
head = new Node();
head->next = new Node();
head->next->next = new Node();
// 데이터 설정
head->data = 1;
head->next->data = 2;
head->next->next->data = 3;
// 데이터 출력
std::cout << head->data; // 1
std::cout << head->next->data; // 2
std::cout << head->next->next->data; // 3
// 🧹 해제는 조금의 역순 (뒤에서부터)
delete head->next->next;
head->next->next = nullptr;
delete head->next;
head->next = nullptr;
delete head;
head = nullptr;
return 0;
}
C++
복사
링크드리스트 구현하기
그럼 이제 앞서 만들어본 Node를 활용하여 링크드리스트를 구현해보자.
#include <iostream>
#include <list>
struct Node
{
int data;
Node* next;
};
Node* head = nullptr;
Node* tail = nullptr;
void AddNode(int data)
{
if (head == nullptr)
{
// 🏠 첫번째 추가할 해준다.
head = new Node;
head->data = data;
head->next = nullptr;
tail = head;
}
else
{
// 🔗 제일 마지막 노드에 추가를 해준다.
tail->next = new Node;
tail->next->data = data;
tail->next->next = nullptr;
tail = tail->next;
}
}
int main()
{
AddNode(3);
AddNode(4);
AddNode(5);
// while, for 문을 활용한 linked list 순회
//Node* p = head;
//while (true)
//{
// if (p == nullptr)
// break;
//
// std::cout << p->data;
// p = p->next;
//}
// 🔄 for문을 이용한 순회
for (Node* p = head; p != nullptr; p = p->next)
{
std::cout << p->data;
}
return 0;
}
C++
복사
핵심 포인트:1.
동적할당의 필요성: 컴파일 시점에 크기를 결정할 수 없는 경우
2.
new/delete 쌍: 할당한 메모리는 반드시 해제해야 함
3.
연결리스트 장점: 실행 중 데이터 추가/삭제가 용이
4.
포인터 활용: 노드들을 연결하는 핵심 도구
5.
메모리 누수 방지: delete를 통한 적절한 메모리 해제
다음 단계: 이 기본기를 바탕으로 템플릿을 활용한 제네릭 연결리스트 구현 가능! “강의는 많은데, 내 실력은 왜 그대로일까?”
혼자서 공부하다 보면
이런 생각 들지 않으셨나요?
•
강의는 다 듣고도 직접 코드는 못 짜겠고,
•
복습할 땐 어디서부터 다시 시작해야 할지 막막하고,
•
질문하려 해도 물어볼 사람이 없고,
•
유튜브 영상도 정답만 보고 따라 치는 느낌…
그렇다면 지금이 바로
“나만을 위한 코칭”이 필요한 순간입니다.
당신도 할 수 있습니다.
지금 멤버십을 넘어, 코칭에 도전해보세요.
수많은 수강생들이 얌얌코딩 코칭으로 넥슨, 크래프톤, NC 등 입사에 성공했습니다.
또는 카톡 오픈채팅: 얌얌코딩 상담방지금도 코딩을 ‘따라 치기만’ 하고 계신가요?
이젠 혼자 설계하고, 스스로 코딩하는 법을 배워야 할 때입니다.
얌얌코딩이 옆에서 함께하겠습니다.