74. 연결리스트

#. 노드의 2가지 종류

헤드 = 머리노드 : 데이터 저장x

노드 : 데이터 저장

#include <stdio.h>
#include <stdlib.h>    // malloc, free 함수가 선언된 헤더 파일

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

int main()
{
    struct NODE *head = malloc(sizeof(struct NODE));    // 머리 노드 생성, 머리 노드는 데이터를 저장하지 않음

    struct NODE *node1 = malloc(sizeof(struct NODE));   // 첫 번째 노드 생성
    head->next = node1;                                 // 머리 노드의 next(포인터)자리에 node1 주솟값 저장
    node1->data = 10;                                   // 첫 번째 노드 data 자리에 10 저장

    struct NODE *node2 = malloc(sizeof(struct NODE));   // 두 번째 노드 생성
    node1->next = node2;                                // 첫 번째 노드 next(포인터)자리에 node2 주솟값 저장
    node2->data = 20;                                   // 두 번째 노드에 data 자리에 20 저장
    node2->next = NULL;                                 // 두 번째 노드 next(포인터)자리에 NULL 주솟값 저장, 즉, 두 번째 노드 다음은 노드가 없음(NULL)

    struct NODE *curr = head->next;    // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
    while (curr != NULL)               // 포인터가 NULL이 아닐 때 계속 반복
    {
        printf("%d\n", curr->data);    // 현재 노드의 데이터 출력
        curr = curr->next;             // 포인터에 다음 노드의 주소 저장
    }

    free(node2);    // 노드 메모리 해제
    free(node1);    // 노드 메모리 해제
    free(head);     // 머리 노드 메모리 해제

    return 0;
}

#. 구조체 Node

struct Node { // 연결 리스트의 노드 구조체

struct Node *next; // 다음 노드의 주소를 저장할 포인터

int data; // 데이터를 저장할 멤버 };

 

 

 

 

#. malloc(sizeof(struct NODE))

struct NODE 공간만큼 동적할당을 해줌

#. struct NODE *head = malloc(sizeof(struct NODE));    // 머리 노드 생성, 머리 노드는 데이터를 저장하지 않음
    struct NODE *node1 = malloc(sizeof(struct NODE));   // 첫 번째 노드 생성
    head->next = node1;                                 // 머리 노드의 next(포인터)자리에 node1 주솟값 저장
    node1->data = 10;                                   // 첫 번째 노드 data 자리에 10 저장
    struct NODE *node2 = malloc(sizeof(struct NODE));   // 두 번째 노드 생성
    node1->next = node2;                                // 첫 번째 노드 next(포인터)자리에 node2 주솟값 저장
    node2->data = 20;                                   // 두 번째 노드에 data 자리에 20 저장
    node2->next = NULL;                                 // 두 번째 노드 next(포인터)자리에 NULL 주솟값 저장

#. struct NODE *curr = head->next;    // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
    while (curr != NULL)               // 포인터가 NULL이 아닐 때 계속 반복

{printf("%d\n", curr->data);    // 현재 노드의 데이터 출력
        curr = curr->next;             // 포인터에 다음 노드의 주소 저장}

#. 연결리스트의 단점 : 배열의 인덱스처럼 특정 노드에 바로 접근 불가능

4번노드에 접근하려면 1번부터 4번까지 탐색해야만 함

#. struct NODE *curr = head->next;

즉, 현재 *curr = *node1

#. while (curr != NULL)               // 포인터가 NULL이 아닐 때 계속 반복
    {
        printf("%d\n", curr->data);    // 현재 노드의 데이터 출력
        curr = curr->next;             // 포인터에 다음 노드의 주소 저장
    }

 

#. 실행