연결 리스트(Linked List) 개념 (3)

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

지금부터 node node1; node node2;

이런 식으로 node를 생성하는 것이 아닌 메모리 할당으로 node를 생성하고 각 node끼리 연결하는법의 코드를 본다.

[ 구조체를 통한 표현 ]

#include <stdio.h>
#include <malloc.h>
 
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;
 
    int value;
 
    while (1)
    {
        printf("자연수를 입력해 주세요 : ");
        scanf("%d", &value);
 
        if (value < 1) // 예외처리는 모든 코딩에서 아주 중요하다.
        {
            printf("다시 입력해 주세요.\n");
            continue;
        }
        // 노드의 추가 과정
        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;
    }
 
    void doNext(node *newnode)
    {
        next = newnode;
    }
 
    void see(node *head) 
    {
        node *pos = head;
        int val = pos->data;
 
        while (1)
        {
            cout << val << " ";
 
            if (pos->next == NULL)
            {
                pos = NULL; // 이 과정이 없다면 delete pos시 연결 리스트 마지막 값 메모리가 해제 되어버린다.
                delete pos;
                break;
            }
            pos = pos->next;
            val = pos->data;
        }
        cout << endl;
    }
};
 
int main()
{
    node *head = NULL; // 이것은 구조체를 만든 것이 아닌 node 구조체를 가리킬 수 있는 포인터를 만든 것이다.
    node *tail = NULL; // node node1; 과는 다르다.
    node *cur = NULL;
    node *newnode = NULL;
 
    int value;
    
    while (1)
    {
        cout << "자연수를 입력해 주세요 : " ;
        cin >> value;
 
        if (value < 1) // 예외처리는 모든 코딩에서 아주 중요하다.
        {
            cout << "다시 입력해 주세요."<< endl;
 
            head->see(head); // 연결 리스트가 잘 연결되고 있는지 한번 확인해 본다. (이때는 첫부분인 head를 기점으로 본다.)
                        
            continue;
        }
 
        // 노드의 추가 과정
        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는 가장 처음을 가리키는 포인터이다.

cur은 순차 접근을 하기위해 head에서 tail까지 순차적 접근을 하는 포인터이다.

tail은 가장 마지막을 가리키는 포인터이다.

 if(head == NULL)
    head = newNode; // 만약 head가 아무것도 가리키지 않고있다면 newNode를 가리키게 한다.
 
 else
    tail->next = newNode; // 그렇지 않다면 tail

이 코드가 없다면?

첫 노드와 두번째 이상의 노드부터의 경계가 모호해지면서 

head가 첫 노드를 가리키게 하는것이 힘들어지고 노드를 순차적으로 연결하기 애매해진다.

물론 다른 방법으로도 할 수 있지만, 이 방법을 추천하는 바 이다.

이 코드를 계속 반복한다면 결국 아래와 같은 그림이 된다.