3 # | 연결 리스트

** 자료 구조 공부법 : 그림을 그리며 이해하고 설명하자 ! *** 

배열 (자료 구조 ) 의 특징

장점 : 순차 접근이 가능하다.

단점 :  메모리의 특성이 정적이다. / 길이 변경이 불가하다. ! 

그래서 연결리스트는 ?  " 연결하며 확장한다. " 

LinkedRead.c 

연결리스트 분석 연습 하기 

#include <stdio.h>
#include <stdlib.h>
 
typedef struct _node
{
    int data;
    struct _node * next;
} Node;
 
int main(void)
{
    Node * head = NULL;    // NULL 포인터 초기화
    Node * tail = NULL;
    Node * cur = NULL;
 
    Node * newNode = NULL;
    int readData;
 
    /**** 데이터를 입력 받는 과정 ****/
    while(1)
    {
        printf("자연수 입력: ");
        scanf("%d", &readData);
        if(readData < 1)
            break;
 
        /*** 노드의 추가과정 ***/
        newNode = (Node*)malloc(sizeof(Node));
        newNode->data = readData;
        newNode->next = NULL;
 
        if(head == NULL)
            head = newNode;
        else
            tail->next = newNode;
 
        tail = newNode;
    }
    printf("\n");
 
    /**** 입력 받은 데이터의 출력과정 ****/
    printf("입력 받은 데이터의 전체출력! \n");
    if(head == NULL) 
    {
        printf("저장된 자연수가 존재하지 않습니다. \n");
    }
    else 
    {
        cur = head; 
        printf("%d  ", cur->data);   // 첫 번째 데이터 출력
        
        while(cur->next != NULL)    // 두 번째 이후의 데이터 출력
        {
            cur = cur->next;
            printf("%d  ", cur->data);
        }
    }
    printf("\n\n");
 
    /**** 메모리의 해제과정 ****/
    if(head == NULL) 
    {
        return 0;    // 해제할 노드가 존재하지 않는다.
    }
    else 
    {
        Node * delNode = head;
        Node * delNextNode = head->next;
 
        printf("%d을(를) 삭제합니다. \n", head->data);
        free(delNode);    // 첫 번째 노드의 삭제
        
        while(delNextNode != NULL)    // 두 번째 이후의 노드 삭제 위한 반복문
        {
            delNode = delNextNode;
            delNextNode = delNextNode->next;
 
            printf("%d을(를) 삭제합니다. \n", delNode->data);
            free(delNode);    // 두 번째 이후의 노드 삭제
        }
    }
 
    return 0;
}

분석 

head 가 NULL 일 때와 아닐 때로 나뉜다. 

어떤 것도 추가 되지 않았다면 당연히 head == newNode; 가 되는 것이고 

만약 헤드가 이미 있다면 

tail-> next = newNode; 이다. 

cur = head;     // cur이 리스트의 첫번째 노드를 가리킨다.

cur = cur -> next;     // cur이 다음 노드를 가리키게 한다.   위 반복문의 핵심이다. 

Node * delNode = head;

Node * delNextNode = head -> next;

포인터 변수를 추가로 선언한 사실에 주목하자 

"head가 가리키는 노드를 그냥 삭제해 버리면 , 그 다음 노드에 접근이 불가합니다. "

 4가 저장된 노드의 주소 값을 아는 것은 2가 저장된 노드가 유일한데, 이 노드를 

그냥 소멸시킨 결과로 4가 저장된 노드의 주소 값은 어디에도 존재하지 않게 된다.

그래서 위 2번째 그림처럼  삭제될 노드가 가리키는 다음 노드의 주소 값을 별도로 저장하는 것이다.