WEEK05 - TIL 연결 리스트 구조체

struct NODE {   // 연결 리스트의 노드 구조체
    struct NODE *next;    // 다음 노드의 주소를 저장할 포인터
    int data;             // 데이터를 저장할 멤버
};

연결리스트는 노드들의 집합이라 실제로는 노드의 구조체만 정의하면 된다.

node 구조체에서 가장 중요한 부분은 struct NODE *next이다. 얼핏 보면 구조체 자기 자신의 포인터를 멤버로 가지고 있는데, 전혀 어려운 게 아니다!

next에는 NODE구조체로 만든 다른 노드의 메모리 주소를 저장한다. 즉, 자기 자신이 아닌 다른 노드의 메모리 주소를 저장한다는 점!!!

 

단일 연결 리스트에서 노드 종류 [노드 역할에 따라 두 가지로 나뉨]

- 머리노드(head node): 단일 연결 리스트의 기준점, 첫 번째 노드를 가리키는 용도라 데이터를 저장하지 않는다.

- 노드: 단일 연결 리스트에서 데이터가 저장되는 실제 노드

=> 두 종류의 노드는 역할만 다를 뿐 모두 NODE 구조체를 사용한다.

 

머리 노드를 만들고 노드가 2개인 연결리스트를 만들면 다음과 같다.

#include <stdio.h>
#include <stdlib.h> //malloc, free 함수를 사용하기 위해 헤더파일 실행

struct NODE //연결 리스트의 노드 구조체 정의
{
    struct NODE *next; //다음 노드의 주소를 저장할 포인터
    int data; //데이터를 저장할 멤버
};

int main(){
    struct NODE *head = malloc(sizeof(struct NODE)); // malloc함수로 메모리 할당, 크기는 sizeof~지정
    struct NODE *node1 = malloc(sizeof(struct NODE));

    head->next = node1;
    node1->data = 10;

    struct NODE *node2 = malloc(sizeof(struct NODE));
    node1->next = node2;
    node2->data = 20;

    node2->next = NULL; //2번째 노드 다음은 노드가 없어서 null값

    //curr == current
    struct NODE *curr = head->next; //연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
    while (curr != NULL){ //curr 포인터가 null이 아닐 때까지 계속 반복
        printf("%d\n", curr->data); //1번째부터 도니까 10 > 20 출력
        curr = curr->next;
    }
    // free 함수를 써서 해당 메모리들을 해제하는 작업
    free(node2);
    free(node1);
    free(head);

    return 0;
}

-> 첫 번째 노드를 생성한 뒤 머리 노드의 next에 첫 번째 노드의 주소를 저장

-> 두 번째 노드를 생성한 뒤 첫 번째 노드의 next에 두 번째 노드의 주소를 저장

 

☞ ->의 의미는 구조체 안에 접근한다는 의미 == .으로도 쓸 수 있다.

 

반복문에서 마지막 노드의 다음(next)는 null이라는 점을 이용한다.

 

 

- 연결 리스트에서 노드를 추가하는 규칙

1. 노드에 메모리 할당

2. next 멤버에 다음 노드의 메모리 주소 저장

3. data 멤버에 데이터 저장

4. 마지막 노드라면 next 멤버에 null 저장