연결 리스트(Linked List) 개념 (4) - 최종 코드 및 과정 수록

[ 구조체(C) 및 클래스(C++) 두가지 방식으로 구현하는 연결 리스트 ] 

이 게시물에서 연결 리스트의 삭제, 출력 방식을 통해 기본적인 과정이 끝이 난다.

[ 구조체를 통한 표현 ]

#include <stdio.h>
#include <malloc.h>
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:4996)
 
typedef struct Node
{
    int data;
    Node *next;
}node;
 
int main()
{
    node *head = NULL; // 이것은 구조체를 만든 것이 아닌 node 구조체를 가리킬 수 있는 포인터를 만든 것이다.
    node *tail = NULL; // node node1; 과는 다르다.
    node *cur = NULL;
    node *newnode = NULL;
    node *delnode;
    node *delnextnode;
 
    int value;
 
    printf("예외 : 0 입력시 연결 리스트 모든 값이 출력됩니다.\n");
    printf("예외 : -1 입력시 연결 리스트 모든 값이 출력됩니다.\n\n");
 
    while (1)
    {
        printf("자연수를 입력해 주세요 : ");
        
        scanf("%d", &value);
 
        // 연결 리스트 값 출력 ( value == 0 ) 
        if (value == 0)
        {
            if (head == NULL)
            {
                printf("연결 리스트에 값이 존재하지 않습니다.\n");
                continue;
            }
 
            else
            {
                
                cur = head;
                printf("%d ", cur->data);
                while (cur->next != NULL) // tail->next는 NULL이다.
                {
                    cur = cur->next;
                    printf("%d ", cur->data);
                }  printf("\n");
            }
        }
 
 
        // 연결 리스트 삭제 과정 ( value == -1 ) 
        else if (value == -1)
        {
            if (head == NULL)
            {
                printf("삭제할 노드가 없습니다.\n");
                continue;
            }
 
            else
            {
                delnode = head;
                delnextnode = head->next;
 
                printf("%d를 삭제합니다.\n", delnode->data); 
                free(delnode);
 
                while (delnextnode != NULL)
                {
                    delnode = delnextnode; // delnode는 그다음 노드를 가리키게된다.
                    delnextnode = delnextnode->next; // delnextnode는 delnode 다음 노드를 가리킨다.
                    
                    printf("%d를 삭제합니다.\n", delnode->data);
                    free(delnode);
                }
                // 모든 노드를 삭제하면서 free(delnode);를 시행했으니 결국 head가 가리키던 node 및 tail이 가리키던 node가 다 메모리 헤제가 되면서
                // head와 tail이 쓰레기 값을 보고 있게된다. 그것을 방지해주기 위해 모두 NULL로 초기화 한다.
                head = NULL;
                tail = NULL;
                cur = NULL;
            }
 
        }
 
 
        else if (value < 1) // 예외처리는 모든 코딩에서 아주 중요하다.
        {
            printf("다시 입력해 주세요.\n");
            continue;
        }
 
 
        else
        {
            // 노드의 추가 과정
            newnode = (node*)malloc(sizeof(node));
            newnode->data = value; // 새로 생긴 node에 data를 넣는다.
            newnode->next = NULL; // 새로 생긴 node의 next 포인터는 NULL을 가리키도록 한다. 
            if (head == NULL)
                head = newnode; // 만약 head가 아무것도 가리키지 않고있다면 newnode를 가리키게 한다.
            else
                tail->next = newnode; // 그렇지 않다면 tail의 next 즉, tail은 node를 가리키니 node의 next가 newnode를 가리키게 한다.
        
            tail = newnode;
        }
 
    }
 
 
    return 0;
}
 

[ 클래스를 통한 표현 ]

#include <iostream>
 
using namespace std;
 
class node
{
 
private:
    int data;
    node *next;
 
public:
    void inputData(int value)
    {
        data = value;
    }
 
    void init()
    {
        next = NULL;
    }
 
    // next라함은 a -> next(b)에서 a의 next를 의미한다.
    void doNext(node *newnode)
    {
        next = newnode;
    }
    
    // 연결 리스트에 연결된 노드들을 삭제하는 과정
    void doDelete(node *delnode, node *delnextnode)
    {
        node *tmp = delnode;
 
        delnextnode = tmp->next;
 
        cout << tmp->data<< "를 삭제합니다." << endl;
 
        delete tmp;
 
        while (delnextnode != NULL)
        {
            tmp = delnextnode; // delnode는 그다음 노드를 가리키게된다.
            delnextnode = tmp->next;
            cout << tmp->data<< "를 삭제합니다." << endl;
            delete tmp;
        }
 
    }
 
    // 그 포인터가 가지는 데이터를 가져온다.
    int getData()
    {
        return data;
    }
 
    // 전체 노드를 보기 위한 함수
    void see(node *head, node *cur) 
    {
        cur = head;
        
        cout << cur->data << " ";
            while (cur->next != NULL) // tail->next는 NULL이다.
            {
                cur = cur->next;
                cout << cur->data << " ";
            }
            cout << endl;
    }
};
 
int main()
{
    node *head = NULL; // 이것은 구조체를 만든 것이 아닌 node 구조체를 가리킬 수 있는 포인터를 만든 것이다.
    node *tail = NULL; // node node1; 과는 다르다.
    node *cur = NULL;
    node *newnode = NULL;
 
    int value;
 
    cout << "예외 : 0 입력시 연결 리스트 모든 값이 출력됩니다." << endl;
    cout << "예외 : -1 입력시 연결 리스트 모든 값이 출력됩니다.\n" << endl;
 
    while (1)
    {
        cout << "자연수를 입력해 주세요 : " ;
        cin >> value;
 
        // 연결 리스트 값 출력 ( value == 0 )
        if (value == 0)
        {
                if (head == NULL)
                {
                    cout << "연결 리스트에 값이 존재하지 않습니다." << endl;
                    continue;
                }
 
                else
                {
                    cur->see(head,cur);
                }
        }
 
 
 
        // 연결 리스트 삭제 과정 ( value == -1 )
        else if (value == -1)
        {
            if (head == NULL)
            {
                printf("삭제할 노드가 없습니다.\n");
                continue;
            }
 
            else
            {
                node *delnode = head;
                node *delnextnode = NULL;
 
                delnode->doDelete(delnode, delnextnode);
                                
                // 모든 노드를 삭제하면서 free(delnode);를 시행했으니 결국 head가 가리키던 node 및 tail이 가리키던 node가 다 메모리 헤제가 되면서
                // head와 tail이 쓰레기 값을 보고 있게된다. 그것을 방지해주기 위해 모두 NULL로 초기화 한다.
                head = NULL;
                tail = NULL;
                cur = NULL;
            }
        }
 
        else if (value < 1) // 예외처리는 모든 코딩에서 아주 중요하다.
        {
            cout << "다시 입력해 주세요."<< endl;
 
            continue;
        }
 
        else
        {
            // 노드의 추가 과정
            newnode = new node; // node의 크기만큼 newnode에 공간을 할당해 준다.
            newnode->inputData(value);  // 새로 생긴 node에 data를 넣는다.
            newnode->init();  // 새로 생긴 node의 next 포인터는 NULL을 가리키도록 한다. 
 
            if (head == NULL)
                head = newnode; // 만약 head가 아무것도 가리키지 않고있다면 newnode를 가리키게 한다.
            else
                tail->doNext(newnode); // 그렇지 않다면 tail의 next 즉, tail은 node를 가리키니 node의 next가 newnode를 가리키게 한다.
        
            tail = newnode;
        }
        
    }
    return 0;
}
 
 

값 출력 과정에서 알고리즘

만약 head가 NULL을 가리킨다면?? 아무것도 없다는 뜻이니 값이 없다는 상태를 출력한다.

그게 아니라면 cur은 head가 가리키는 주소를 가리킨다. 

즉, 연결 리스트의 가장 첫 부분을 가리키게 된다.

그다음 그 값을 cur->data(즉, cur이 가리키는 노드의 data 값)을 출력하고

while문의 조건을 확인한다. while문의 조건은 cur이 가리키는 노드의 next가 가리키는 것이 NULL이 아니라면

cur = cur->next;를 취한다.

이것의 의미는 cur이라는 포인터는 (cur = ) cur이 가리키는 노드의 next가 가리키는 주소를 가리켜라 (cur = cur->next;)라는 뜻이다.

그리고 그다음 값을 또 출력하며 조건이 맞지 않을 때 까지 반복한다.

값 삭제 과정에서의 알고리즘

출력과정과 동일한 알고리즘이고 그림을 보고 한번 어떠한 알고리즘으로 돌아가는지 생각해봤으면 한다.

그리고 [ 구조체를 통한 표현 ]부분에서 노드 삭제 과정의 

head = NULL, tail = NULL, cur = NULL;의 의미를 한번 생각 해보는 시간을 가졌으면 좋겠다.