CS/자료구조

[자료구조 및 프로그래밍] 6. 메모리 관리 시스템

2023. 10. 18. 23:56
반응형

지난 글에서는 연결리스트를 이용해 스택과 큐를 구현하였다.

이번 글에서는 연결리스트를 이용하는 과정에서 new(), free() 기능을 사용했는데, 이 기능을 직접 구현해본다.


사실 직접 구현이라고 해서 나도 처음엔 메모리를 직접 다루는 거창한 걸 기대했는데, 그런건 아니다.

그냥 배열을 이용해서 전체 memory pool 을 세팅해두고, 그 세팅된 pool 내 메모리를 주고 받고 하는 방식이다.

 

메모리 풀은 연결리스트 노드의 데이터 형태로 배열에 세팅해두고, 이를 스택처럼 활용하여 메모리를 주고 받는다.

메모리 풀은 이런 구조로 존재한다.

만약 new 함수로 메모리 공간을 요청하면 top이 가리키는 노드를 제공해준다.

제공을 마친 모습이다.

제공된 메모리는 연결리스트에서 자유롭게 Item 부분에도 값을 할당하고, Link 부분에도 값을 할당했을 것이다.

 

여기에서 또 새로운 값을 요청받았다고 해보자.

이렇게 top 이 가리키는 노드를 또 할당해주고, 할당된 노드들끼리는 알아서 연결관계를 막 생성한다.

 

이번엔 노드를 반환(free)해보자.

노드를 반환하게 되면, 반환된 노드는 새로운 top이 된다.

한번 data1 이 들어있는 노드를 반환해본 결과를 그려보면 아래와 같이 된다.

data1 을 지우고 그런건 구현하기 나름이겠다.

이제 이를 코드로 구현해보자.

 

처음에 배열에 linked list 노드 배열을 선언해주고, 각 노드는 다음 인덱스의 노드를 가리키도록 초기화한다.

배열로 구현되어 있기 때문에, 연결할 배열을 인덱스로 접근하면 된다.

 

이번 글에서는 직접 C언어로 구현을 해본다.

#include <cstdio>

struct node {
    int item;
    struct node * link;
};
const int NODE_SIZE = 5;
struct node node_pool[NODE_SIZE];

int main() {
    for (int i = 0; i < NODE_SIZE-1; i++) {
        node_pool[i].link = node_pool + sizeof(struct node)*(i+1);
    }

    node_pool[NODE_SIZE-1].link = NULL;

    printf("%d\n", sizeof(struct node));
    for (int i = 0; i < NODE_SIZE; i++) {
        printf("%p\n", node_pool[i].link);
    }
    return 0;
}

16바이트씩 순차적으로 메모리 주소가 link 에 저장되었다.

마지막 노드는 Link 가 null 이다.

 

이제 메모리 pool 에서 메모리를 제공하는 new_node() 를 구현해보자.

위와 같이 간단하게 구현된다.

만약 모든 메모리의 할당이 끝났다면 null 을 반환한다.

 

이제 메모리 반환도 구현해보자.

더 간단하게 구현된다.

 

이제 연결리스트에서 메모리 풀을 사용하여 데이터를 삽입하고 생성하는 과정을 살펴보는 것으로 마무리한다.

#include <cstdio>

struct node {
    int item;
    struct node * link;
};

const int NODE_SIZE = 5;
struct node node_pool[NODE_SIZE];
struct node * memory_top = node_pool;

void print_all_memory_pool() {
    for (int i = 0; i < NODE_SIZE; i++) {
        printf("%p %p\n", node_pool+i, (node_pool+i)->link);
    }
}

struct node * new_node() {
    struct node* p = memory_top;
    if (p == NULL) {
        return NULL;
    }
    memory_top = p->link;
    return p;
}

void free_node(struct node* _node) {
    _node->link = memory_top;
    memory_top = _node;
}

void memory_pool_init() {
    for (int i = 0; i < NODE_SIZE-1; i++) {
        node_pool[i].link = &node_pool[i+1];
    }

    node_pool[NODE_SIZE-1].link = NULL;
    print_all_memory_pool();
}

////////////////////////////////////////////////////////

struct node * head = NULL;

void add(int x) {
    struct node* p = new_node();
    if (p == NULL) {
        printf("overflow!\n");
        return;
    }
    p->item = x;
    p->link = head;
    printf("add %d to %p, and next link is %p\n", x, p, p->link);
    head = p;
    printf("added!\n");
}

void remove(int x) {
    struct node* prev_check = NULL;
    struct node* now_check = head;
    while (now_check != NULL) {
        if (now_check->item == x) {
            if (prev_check != NULL) {
                prev_check->link = now_check->link;
            } else {
                prev_check = now_check;
                now_check = now_check->link;
            }
            free_node(now_check);
            printf("delete node has %d\n", x);
            return;
        } else {
            prev_check = now_check;
            now_check = now_check->link;

        }
    }
    printf("no node has %d\n", x);
}

void print_all() {
    struct node * p = head;
    while (p != NULL) {
        printf("%p %d\n",p, p->item);
        p = p->link;
    }
}

int main() {
    memory_pool_init();

    add(1);
    print_all();
    print_all_memory_pool();
    printf("\n");

    add(2);
    print_all();
    add(3);
    print_all();
    add(4);
    print_all();
    add(5);
    print_all();

    printf("overflow\n");
    add(6); // 오류가 나야함.
    print_all();

    remove(1);
    print_all();

    remove(3);
    print_all();

    return 0;
}

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'CS > 자료구조' 카테고리의 다른 글

[자료구조 및 프로그래밍] 8. 이진 트리의 순회  (0) 2023.10.22
[자료구조 및 프로그래밍] 7. 트리와 이진트리  (0) 2023.10.20
[자료구조 및 프로그래밍] 5. Stack & Queue With Linked List  (0) 2023.10.17
[자료구조 및 프로그래밍] 4. Linked List  (0) 2023.10.12
[자료구조 및 프로그래밍] 3. Queue (Circular Queue) - 2  (0) 2023.10.04
'CS/자료구조' 카테고리의 다른 글
  • [자료구조 및 프로그래밍] 8. 이진 트리의 순회
  • [자료구조 및 프로그래밍] 7. 트리와 이진트리
  • [자료구조 및 프로그래밍] 5. Stack & Queue With Linked List
  • [자료구조 및 프로그래밍] 4. Linked List
에버듀
에버듀
개발은 좋은데 뭘로 개발할까
에버듀
Blog. 에버듀
에버듀
전체
오늘
어제
  • 분류 전체보기 (607)
    • 개인 프로젝트 (43)
      • [2020] 카카오톡 봇 (9)
      • [2021] 코드악보 공유APP (22)
      • [2022] 유튜브 뮤직 클론코딩 (9)
      • [2025] 고성능 에코서버 만들기 (0)
      • 간단한 프로젝트 (3)
    • 팀 프로젝트 (22)
      • [2020] 인공지능 숫자야구 (4)
      • [2022] OSAM 온라인 해커톤 (10)
      • [2024] GDSC 프로젝트 트랙 (6)
      • [2025] 큰소리 웹 페이지 (2)
    • 알고리즘 (PS) (107)
      • BOJ (101)
      • Programmers (5)
      • 알고리즘 이모저모 (1)
    • CS (329)
      • 자료구조 (19)
      • 어셈블리 (41)
      • 멀티미디어응용수학 (7)
      • 컴퓨터 구조 (29)
      • 알고리즘 분석 (4)
      • 컴퓨터 네트워크 (38)
      • 프로그래밍언어론 (15)
      • HCI 윈도우즈프로그래밍 (26)
      • 기초데이터베이스 (29)
      • 운영체제 (23)
      • 오토마타 (24)
      • 문제해결기법 (11)
      • 블록체인 (22)
      • 소프트웨어공학 (21)
      • 기계학습심화 (12)
      • 컴퓨터그래픽스와 메타버스 (8)
    • 자기계발 (38)
      • 동아리 (7)
      • 자격증 (3)
      • 코딩테스트, 대회 (8)
      • 생각 정리 (19)
      • 머니 스터디 (1)
    • WEB(BE) (5)
      • express.js (1)
      • flask (0)
      • Spring & Spring Boot (4)
    • WEB(FE) (2)
      • html, css, js (1)
      • React.js (1)
    • Tool & Language (6)
      • Edit Plus (1)
      • Git (1)
      • Python3 (2)
      • Java (2)
    • Infra (12)
      • AWS (1)
      • Oracle Cloud (8)
      • Firebase (2)
      • Network (1)
    • Android (18)
      • Java (6)
      • Flutter (12)
    • Window (2)
      • Visual Studio 없이 WPF (1)
      • MFC (1)
    • 독서 (14)
      • Inside Javascript (7)
      • Database Internals (6)
      • 한 글 후기 (1)
    • 인턴 (8)
      • 델파이 (7)
      • Oracle (1)

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.1.4
에버듀
[자료구조 및 프로그래밍] 6. 메모리 관리 시스템
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.