C언어 구조체 노드 삽입

C언어 구조체 노드 삽입


이번에는 자료구조의 기본적인 노드와 삽입에 대해서 알아보겠다.

노드는 일단 이렇게 생겼다.


 데이터

 다음 노드를 가리키는 포인터


이렇게 생겼다.

이거를 C언어로 표현을 하면

1
2
3
4
5
struct Node
{
    int data;
    struct Node *nextNode;
}
cs

이렇게 생겼다.
이런 노드는 배열 중간에 값을 추가하거나 삭제를 할 때 유용하게 사용할 수 있다.
배열은 중간에 값을 추가하거나 삭제를 하면 배열을 또 하나 만들어줘야 한다.
그렇기 때문에 우리는 이 Node로 해결해줄 것이다.
그림 상으로 보면 이렇다.

이 밑에 있는 노드를 추가시키려고 한다. 각 노드 오른쪽 공간에는 다음 노드를 가리키는 포인터가 있다.

이렇게 추가를 시키면 된다.

두 번째 노드에서 주소를 가리키는 포인터를 추가시키려고 하는 노드의 첫 주소를 넣어주고

추가시키려고 하는 포인터에 3번째 노드 첫 주소를 넣어주면 된다.

방법은 간단하다. 이것을 C언어로 표현해보자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node *nextNode;
};
struct Node* CreateNode(int data)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->nextNode = NULL;
    return newNode;
}
int main()
{
    struct Node *Node1 = CreateNode(100;)
    return 0;
}
cs


일단 이렇게 Node 구조체를 만들어주고 노드 추가 함수를 만들어주자.
10행에서 neNode에 힙(heap) 메모리에 메모리를 생성해주었다.
그리고 값을 넣어주고 다음 포인터를 가르키는 주소값에 NULL을 넣어주었다.
17행에서는 Node1에 newNode 주소값을 넣어주었다.
일단 그림으로 이 코드를 분석해보자.

현재 이렇게 되어있다. 여기서 나는 처음에 newNode는 함수가 끝나면 사라지는 거 아닌가?라고 생각을 했다.

근데 malloc는 힙(heap) 메모리에 저장이 되어서 우리가 삭제하기 전까지는 사라지지가 않는다.

함수가 끝나면 자동으로 없어지는 것은 스택(Stack) 메모리에 저장되는 경우를 말한다.

그리고 이제 추가를 해주는 함수를 만들어보자.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node *nextNode;
};
struct Node* CreateNode(int data)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->nextNode = NULL;
    return newNode;
}
struct Node* InsertNode(struct Node *current, int data)
{
    struct Node *after = current->nextNode;
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    
    newNode->data = data;
    newNode->nextNode = after;
    current->nextNode = newNode;
    return newNode;
}
int main()
{
    struct Node *Node1 = CreateNode(100);
    struct Node *Node2 = InsertNode(Node1, 100);
    return 0;
}
cs

17행에서 after 포인터 변수를 만들고 NULL(nextNode 값) 값을 넣어준다.
그리고 힙(heap) 메모리에 메모리를 생성하고 주소값을 newNode에 넣어준다.
data에 값을 넣어주고, nextNode에는 NULL 값을 넣어준다.
Node1 nextNode에는 newNode 첫 시작 주소를 넣어준다.
그리고 newNode 주소값을 Node2한테 넣어준다.
그림으로 보면 이렇다.

이렇게 된다.

Node1을 통해 InsertNode 부분에 있는 newNode까지 접근이 가능하다.

이제 이 방식으로 몇개 더 생성해주고 값이 정말로 나오는지 확인해보자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int data;
    struct Node *nextNode;
};
struct Node* CreateNode(int data)
{
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->nextNode = NULL;
    return newNode;
}
struct Node* InsertNode(struct Node *current, int data)
{
    struct Node *after = current->nextNode;
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    
    newNode->data = data;
    newNode->nextNode = after;
    current->nextNode = newNode;
    return newNode;
}
void PrintNodeFrom(struct Node *from)
{
    while (from) //from이 NULL일때까지, 즉 끝부분에 도달할 때 까지
    {
        printf("노드의 데이터 : %d\n", from->data);
        from = from->nextNode;
    }
}
int main()
{
    struct Node *Node1 = CreateNode(100);
    struct Node *Node2 = InsertNode(Node1, 200);
    struct Node *Node3 = InsertNode(Node2, 300);
    //Node2 뒤에 Node4 넣기
    struct Node *Node4 = InsertNode(Node2, 400);
    PrintNodeFrom(Node1);
    return 0;
}
cs

< 출력 >
노드의 데이터 : 100
노드의 데이터 : 200
노드의 데이터 : 400
노드의 데이터 : 300

출력 결과는 이렇게 나온다.
노드에 대해서 알아보았다.

댓글

Designed by JB FACTORY