단일 연결 리스트 -Linked List(1) (노드생성, 삭제, 추가) - C 언어

단일연결리스트는 크기를 가변적으로 만들 수 있다는 장점이 있다. 

예를들어 파일 목록을 가져 오려하는데 어떤 임의의 디렉토리에서 파일이 몇개 있는지

알 수 없을때. 고정적인 배열을 사용하여 가져오기에는 한계가 있다.

 

char* FileList[20]; 이라고 선언해놓고 파일이 20개이상이 되면 불러오지 못한다거나,

char* FileList[65535]; 라고 선언해놓고 파일목록이 이 숫자에 미치지 못한다면 메모리가

아까울 뿐이다.

 

이런 경우 정적인 배열말고 동적인 1차원 리스트를 생성할 수 있는데

단점은 효율이 안좋으므로 다른걸 씁시다. 그래도 알아두면 이중연결리스트를 기반으로

이진트리나,다른 기타 자료구조나 알고리즘과 C언어의 포인터를 이해하는데 조금은 도움이 되기 때문이다.

 

typedef struct
{
    uint16_t Data;
    struct Node* Next;
}Node;

 

기본적인 노드의 구조체는 이렇다.

노드라는건 쉽게말해 기차로 비유하면 된다.

기차는 1호선 2호선 3호선 . . .으로 되어있다면 하나의 노드는 그 n호선을 뜻한다.

 

여기서 Data는 차안에 있는 사람이나 의자 와같은 내용물이라고 생각하면 편하고

Next는 흔히말해 링크라고 부르기도 하고 tail(꼬리)라고 부르기도 하는데 이건 n호선과 n+1호선을 연결시켜주는 연결고리라 생각하면 편하다

 

노드를 생성하는 부분 Create_node

반환 타입은 새로운 노드의 포인터를 반환한다.

1. 노드 생성

Node* Create_Node(uint16_t NewData)
{
    Node* NewNode = (Node*)malloc(sizeof(Node));
 
    NewNode->Data = NewData; // 새로운 데이터를 생성된 노드의 데이터에 저장
    NewNode->Next = NULL; //다음 노드의 포인터는 NULL로 초기화
 
    return NewNode; // 노드 주소 반환
}

 

여기서 노드를 만드는데 malloc으로 메모리를 할당해주는 이유는

메모리 구조때문에 그렇다. 쉽게 설명해서

 

malloc 없이 새로운 노드를 만든다보면

Node* HNode = Create_Node(18);

 

이 코드는 에러가 발생한다 왜냐하면, 

Create_Node 함수가 종료되면서 반환되는 NewNode는 stack에서 사라지기 때문이다.

메모리 구조에대해서는 추후 포스팅 하겠음.

 

malloc을하여 흔히말해 자유저장소 힙영역에 할당하여 함수가 종료되도 메모리상에 남아있어야

Node* HNode에서 HNode가 할당된 메모리를 가리키기 때문이다.

 

 

2. 노드 삭제

void DeleteNode(Node* Node)
{
    free(Node);
}

할당된 노드의 메모리를 해제 시켜준다. 메모리를 할당시켜주지 않으면

메모리 누수의 원인이 되기 떄문이다. free함수는 기본적으로 표준라이브러리 stdlib.h 에 정의되어있다. (c++의 delete와 유사한기능이지만 연산자와는 다르다. )

 

3. 노드 추가

void AddNode(Node** head, Node* NewNode)
{
    if ((*head) == NULL)
    {
        *head = NewNode; //헤드 노드가 Null이면 새 노드가 head가 됨.
    }
    else
    {
        Node* Tail = (*head);
        
        while (Tail->Next != NULL)
        {
            Tail = Tail->Next;
        }
        Tail->Next = NewNode;
    }
}

이 부분이 중요한데, 포인터의 개념이 확실하면 어렵지 않은 부분이다.

함수의 파라미터를 보면 Node** head는 이중포인터만 잘 이해하면 

연결리스트는 다 이해했다 보면 된다.

 

예를들어

Node* Node_1 = NULL;
 
Node* Node_2 = NULL;
 
Node_2 = Create_Node(100);
 
AddNode(&Node_1,Node_2)

 

이 코드에서 AddNode의 첫번째 파라미터로 &Node_1 즉

 

Node_1의 주소를 전달 해주는데, 

 

&Node_1의 주소가 0x01 이라면,

&head가 가리키는 값은  &Node_1 과 같다고 보면된다. 

 

-> 가리키는 값

1. &head -> head -> &Node_1 -> NULL ;

2.  Node_1 == *head == NULL

 

head는 0x02번지라면

&head(0x02) -> 0x01 -> NULL 을 가리키게된다.

 

즉, 첫번째 파라미터 Node** head는 (Node 포인터의 주소를 가리키는) 포인터가 된다.

 

&head = 0x02

 

0x02 -> [0x01]

 

[0x01] ->{data,Next}

 

 

즉....