[YYBASIC0303/얌얌코딩] 링크드 리스트 설명, 동적 할당 설명

프로그래밍에서 데이터를 저장하는 방법에는 여러 가지가 있으며, 이를 자료구조(Data Structure) 라고 합니다. 프로그램을 작성할 때 적절한 자료구조를 선택하는 것은 성능과 메모리 사용 효율성을 높이는 중요한 요소입니다.

---

자료구조란?

자료구조는 데이터를 효율적으로 저장하고 관리하는 방법을 의미합니다. 대표적인 자료구조로는 다음과 같은 것들이 있습니다.

• 배열(Array)
• 링크드 리스트(Linked List)
• 큐(Queue) & 스택(Stack)
• 그래프(Graph) & 트리(Tree)

이 중에서 링크드 리스트는 연결된 노드(Node)들로 이루어진 자료구조로, 데이터의 삽입과 삭제가 빈번한 경우 유용하게 사용됩니다.

---

노드(Node)란?

노드(Node)는 데이터를 저장하는 최소 단위입니다.

배열에서의 노드는 배열의 한 칸을 의미하며, 링크드 리스트에서는 데이터(data)와 다음 노드를 가리키는 포인터(next)로 이루어진 구조체(Struct) 혹은 클래스(Class)로 정의됩니다.

struct Node
{
    int data;
    Node* next;
};

위와 같은 구조를 가진 노드가 여러 개 연결되면서 링크드 리스트가 형성됩니다.

---

배열 vs 링크드 리스트 비교

// 접근 속도

자료구조	접근 속도	시간 복잡도
배열(Array)	인덱스(index)를 이용해 O(1)의 속도로 특정 요소에 접근 가능	O(1)
링크드 리스트(Linked List)	처음부터 차례대로 탐색해야 하므로 속도가 느림	O(n)

배열은 랜덤 접근(Random Access) 이 가능하지만, 링크드 리스트는 원하는 데이터를 찾기 위해 첫 번째 노드부터 순차 탐색해야 합니다.

 

// 삽입 / 삭제 속도

자료구조	삽입/삭제 속도	시간 복잡도
배열(Array)	중간에 데이터를 삽입하거나 삭제하면 다른 요소들을 이동해야 함	O(n)
링크드 리스트(Linked List)	중간에 삽입/삭제해도 포인터만 변경하면 되므로 빠름	O(1)

링크드 리스트는 삽입과 삭제가 자주 발생하는 경우 배열보다 훨씬 효율적입니다.

 

// 메모리 사용

자료구조	메모리 활용성
배열(Array)	정해진 크기의 연속된 메모리를 사용해야 하므로, 크기를 초과하면 새로운 배열을 만들어야 함
링크드 리스트(Linked List)	필요한 만큼 동적으로 메모리를 할당하므로, 메모리 활용이 유연함

배열은 크기가 정해져 있지만, 링크드 리스트는 필요한 만큼 동적 할당이 가능하므로 메모리를 효율적으로 사용할 수 있습니다.

 

// YYBASIC03_03
#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* next;
};


int main(void)
{
#pragma region 자료구조 / 노드 
    /* 자료구조(Data Structure) */
    // : 자료들을 저장하는 방법
    // 여러가지 자료를 저장하는 방법을 배우고
    // 만들 프로그램에 적절한 곳에 적절하게 적합한 자료구조를 선택해서 사용하면 됨

    // 대표적인 자료구조 : 배열, 링크드리스트, 큐, 스택, 그래프, 트리

    /* 노드(Node) */
    // : 데이터를 저장하는 최소 단위
    // 배열에서의 노드 : 각각의 변수 1개(한 칸)을 뜻한다

    /* 링크드 리스트 */
    // : 한 노드가 다른 노드를 가리키는 자료구조
    // 여러 개의 노드로 이루어져 있다
    // 구조체(클래스) 포인터를 이용해서 구현한다


    /* 배열 vs 링크드 리스트 */
    // [접근 속도]
    // 배열 : index 이용 - O(1)의 속도로 특정 요소에 접근 가능 (빠름)
    // 링크드 리스트 : 처음부터 순차 탐색을 해야 함 - O(n) (느림)

    // [삽입/삭제 속도]
    // 배열 : 중간에 삽입/삭제 시 O(n)의 연산이 필요함 (∵ 데이터 이동 필요)
    // 링크드 리스트 : 중간에 삽입/삭제 시 O(1)의 연산이 필요함 (∵포인터 조작만 하면 됨)

    // [메모리 사용]
    // 배열 : 정해진 크기의 연속된 메모리를 사용해야 함 - 메모리 낭비 가능성 O
    // 링크드 리스트 : 동적 할당을 - 공간 활용이 유연함

    // 배열을 사용하는 게 적합한 경우 : 랜덤 접근(random access)이 필요할 때
    // 링크드 리스트를 사용하는 게 적합한 경우 : 데이터의 잦은 삽입/삭제가 발생할 때

#pragma endregion


    return 0;
}

 

---

동적 할당(Dynamic Allocation)

// 정적 할당 vs 동적 할당

• 정적 할당(Static Allocation)
  • 프로그램 실행 전에 미리 메모리를 할당함
  • 지역 변수는 스택(Stack) 영역에 저장됨
  • 함수가 종료되면 자동으로 해제됨
• 동적 할당(Dynamic Allocation)
  • 프로그램 실행 중에 필요한 만큼 메모리를 할당함
  • 힙(Heap) 영역에 저장됨
  • 삭제하지 않으면 메모리가 계속 유지되므로 직접 해제해야 함

 

// new 연산자를 이용한 동적 할당

C++에서는 `new` 연산자를 이용하여 힙 영역에 메모리를 할당할 수 있습니다.

예를 들어, 아래 코드에서는 `Node` 구조체 크기만큼 메모리를 동적으로 할당합니다.

Node* node2 = new Node;  // 동적 할당
node2->data = 1;

 

이렇게 하면 `node2`는 힙 영역에서 할당된 메모리의 시작 주소를 저장하게 됩니다.

 

// 동적 할당한 메모리 해제 (`delete` 연산자)

힙 영역에 동적으로 할당된 메모리는 프로그래머가 직접 해제해야 합니다.

이를 위해 `delete` 연산자를 사용합니다.

delete node2;   // node2가 가리키는 힙 메모리 해제
node2 = nullptr;    // 댕글링 포인터 방지

 

// delete 후 반드시 `nullptr`로 초기화해야 하는 이유

• 삭제된 메모리에 접근하는 것을 방지하기 위해
• 이후 코드에서 해당 포인터를 사용하려 하면 오류를 쉽게 감지할 수 있음

// YYBASIC03_03
#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node* next;
};


int main(void)
{
#pragma region 동적 할당
    /* 동적 할당 */
    // : pgm 실행 중간(= runtime)에 사용자(== user)가 직접 메모리 할당을 결정하게 해서
    //   필요한 만큼 runtime 중에 메모리를 할당한다
    // new 연산자 활용


    /* 정적 할당 */
    // 정적 할당한 변수 : 프로그램 실행 전 미리 메모리 할당 - pgm 실행 시작 시 자동 할당
    // 지역 변수 - 스택 영역에 할당됨 - 해당 지역(함수)을 벗어나면 자동 해제
    Node node1;    
    // node1 : 스택 영역에 있음  (∵ main() 안에서 선언)
    node1.data = 1;
    // node1.data : 스택 영역에 있음  (∵ main() 안에서 정의됨)

    
    /* 동적 할당 */
    // 동적 할당한 변수 : 프로그램 실행 중간에 메모리 할당 - pgm 실행 중간에 할당
    // 프로그래머가 new 연산자를 사용해 직접 메모리 관리
    // 힙 영역에 할당됨 - 메모리 해제 명령어가 실행되어야 메모리에서 해제됨 (자동 X)
    
    // new 연산자 : 힙 영역에 지정한 자료형 크기만큼 메모리 공간을 
    //             동적으로 할당하고, 할당한 공간의 시작 주소를 반환하는 함수

    Node* node2 = new Node;
    // node2 : 스택 영역에 있음  (∵ main() 안에서 선언 및 정의됨)
    // new Node : 힙 영역에 있음 (∵ new 연산자를 이용해 동적 할당함)
    // 즉, node2는 Node 자료형 크기만큼 동적 할당한 메모리 공간의 '시작 주소'를 가짐
    node2->data = 1;
    // node2->data : 힙 영역에 있음 (∵ new 연산자를 이용해 동적 할당함)
    // └ 즉, 이 값은 main()을 빠져나가도 메모리 해제를 하기 전까지 힙 영역에 남아 있음


    /* 동적 할당한 공간 해제 */
    delete node2;   // node2가 가리키는 힙 영역의 메모리를 해제함
    node2 = nullptr;    // 삭제 후 node2를 nullptr로 초기화 (dangling pointer 방지)

    // nullptr로 초기화하는 이유
    // : 삭제된 메모리에 접근하는 것을 방지하여 dangling pointer 문제를 해결함
    // └ 이후 코드에서 해당 포인터를 사용하려 하면 오류를 쉽게 감지할 수 있음
#pragma endregion


    return 0;
}

 

 

LV10 링크드리스트 설명, 동적할당 설명