자료구조: 연결 리스트(Linked Lisk)

연결 리스트란

데이터를 저장하고 표현하는 리스트형 자료구조 중 하나이다.
그 중에서 연결 리스트는 여러개의 노드가 있고 노드는 데이터를 담고 있으며 각 노드는 데이터를 담는 부분과, 다음 노드의 위치를 가리키는 참조 데이터 정보로 이루어져 있다.

노드의 구현

// C++ 구현
typdef struct node{
    DataType data;
    node * next_node;
}node;

노드 자체의 구현은 어렵지 않다. 단순하게 데이터를 담을 변수와 다음 노드를 가리킬 포인터 혹은 참조자만 선언해주면 어떤 것이든 노드가 될 수 있다.

DataType은 어떤 형태여도 상관 없고 하나의 노드가 여러개의 데이터 변수를 담아도 상관 없다. 마음대로 만들어 보자

리스트의 ADT

내가 만든 연결 리스트의 ADT는 다음과 같다

class LinkedList{
private:
    node * head;
    node * make_new_node(int data);
public:
    LinkedList();
    ~LinkedList();
    void insert_node(int data);
    void insert_node(int data, int target_nodes_data);
    void print_list();
    void search_node(int target_nodes_data);
    void delete_node(int target_nodes_data);
    bool is_empty();
}

각 함수의 역할 및 구현은 다음과 같다

node * make_new_node(int data){
   node * new_node = new node();
   new_node->data = data;
   new_node->next_node = nullptr;
   return new_node;
}

이 함수는 새로운 노드를 만들어서 그 주소를 리턴하는 역할을 한다. 각 삽입 함수마다 몇 줄씩 되는 새로운 노드 생성 코드를 집어넣어놓으면 보기에도 불편하고 지저분해 보이니 별도의 함수로 분리시켜주었다.

LinkedList() { head = nullptr; }

생성자는 클래스가 갖고있는 헤드포인터를 널포인터로 초기화하는 역할을 한다. 만일 헤드포인터가 널포인터일 경우 리스트가 비어있다는 의미이기도 해서 널포인터로 초기화시켜주었다.

~LinkedList(){
    node * delete_target;
    while(cur){
        delete_target = head;
        head = head->next_node;
        std::cout << delete_target->data << " 삭제됨" << std::endl;
        delete delete_target;
    }
    head = nullptr;
}

소멸자는 남아있는 노드들을 차례대로 돌면서 모두 delete 시켜준다. 리스트의 노드들은 동적으로 할당해서 쓰기 때문에 만일 소멸시켜 주지 않는다면 메모리 누수로 이어질 수 있기 때문.
만일 커서에 널포인터가 들어올 경우 마지막 노드라는 의미이므로 순회를 멈추고 함수를 종료한다.

void insert_node(int data){
   node * cur = head;
   while(cur->next_node)
       cur = cur->next_node;
   cur->next_node = make_new_node(data);
}

새로운 노드를 생성해서 삽입하는 함수는 2개의 함수를 오버로딩 했는데 하나는 맨 끝에다 새로운 노드를 삽입하는 함수이고, 나머지 하나는 타겟 노드를 지정하고 해당 노드의 바로 뒤에 새로운 노드를 삽입하는 함수이다.

위의 함수는 그냥 맨 뒤에다 새로운 노드를 삽입하는 함수로 커서의 next_node가 nullptr이 될 때 까지 계속해서 다음 노드를 탐색한다. 만일 커서의 next_node가 nullptr일 경우 해당 노드가 마지막 노드라는 의미이므로 해당 노드의 next_node가 새로 생긴 노드를 가리키도록 해준다.

void insert_node(int data, int target_nodes_data){
    node * cur = head;
    while(cur->next_node){
        if(cur->data == target_nodes_data){
            node * new_node = make_new_node(data);
            new_node->next_node = cur->next_node;
            cur->next_node = new_node;
            return;
        }
        cur = cur->next_node;
    }
   
    cur->next_node = make_new_node(data);

이 함수는 타겟 노드를 지정해서 그 노드의 뒤에다 새로운 노드를 생성해서 삽입하는 오버로딩 함수이다. 타겟 노드는 해당 데이터를 가진 노드를 찾아서 탐색하다가 발견을 하면 그 노드의 뒤에다 삽입하고, 없으면 그냥 맨 뒤에다 삽입한다.

새로운 노드를 삽입할 때 new_node->next_node = cur->next_node;
를 먼저 해준 이유는 아래의 그림과 같다

위 그림과 같이 새로 삽입될 노드의 다음 노드의 주소에 대한 정보를 가진 것은 커서가 가리키고 있는 타겟 노드 뿐이다. 헌데 이 상태애서 먼저 타겟 노드가 새로 생성된 노드를 가리키게 만들어버리면?

위의 그림과 같이 해당 커서가 가리키고 있던 다음 노드들을 찾아갈 수 있는 방법을 잃어버리게 된다. 왜냐하면 잃어버린 노드의 주소 정보는 오로지 커서가 가리키고 있는 타겟 노드만이 갖고 있었기 때문.

그렇기 때문에 이런 일을 방지하기 위해선

먼저 새로 생성한 노드가 다음 노드로 커서가 가리키는 타겟 노드의 다음 노드를 가리키도록 해놓고

그런 다음 커서가 가리키는 타겟 노드가 새로 생성한 노드를 가리키도록 해주어야 참조를 잃어버리는 문제를 방지할 수 있다.

void print_list(){
    node * cur = head;
    while(cur){
        std::cout << cur->data << ' ';
        cur = cur->next_node;
    }
    std::cout << std::endl;
}

리스트를 출력하는 간단한 함수이다. 커서가 nullptr을 가리키기 전까지 계속 다음 노드를 탐색하며 해당 노드의 데이터를 출력한다.

void search_node(int target_nodes_data){
    node * cur = head;
    while(cur){
        if(cur->data == target_nodes_data){
            std::cout << cur->data << "를 발견함" << std::endl;
            return;
        }
        cur = cur->next_node;
    }
    // 찾으려는 노드가 존재하지 않을 경우
    std::cout << "해당 노드가 존재하지 않습니다" << std::endl;
}

해당 데이터를 가진 노드가 있는 지 탐색하는 함수로, 노드들을 순차적으로 순회하며 해당 노드가 존재할 경우 해당 노드를 발견했다고 출력하고 발견하지 못했을 경우 해당 노드가 존재하지 않는다는 메시지를 띄운 후 종료한다.

void delete_node(int target){
    node * cur = head;
    node * prev = nullptr;

    // 만일 삭제 대상 노드가 맨 앞의 노드일 경우
    if(cur->data == target_nodes_data){
        head = head->next_node;
        std::cout << cur->data << " 삭제" << std::endl;
        delete cur;
        return;
    }

    // 삭제 대상 노드가 헤드 노드가 아닐 경우
    while(cur){
        // 노드를 찾았을 경우
        if(cur->data == target_nodes_data){
            prev->next_node = cur->next_node;
            std::cout << cur->data << " 삭제" << std::endl;
            delete cur;
            return;
        }
        // 찾는 노드가 아니면
        prev = cur;
        cur = cur->next_node;
    }

    std::cout << "대상 노드가 없습니다" << std::endl;

해당 함수는 노드를 삭제하는 함수로 삭제대상인 노드를 찾아 삭제하는 노드이다. 만약 삭제 대상인 노드를 찾지 못했을 경우 노드를 찾지 못했다는 메시지를 띄우고 종료한다.

이 함수 또한 위의 중간에 노드를 삽입하는 함수와 비슷하게 먼저 대상 노드를 삭제해버리면 리스트가 끊기는 문제가 생기기 때문에, 대상 노드를 삭제하기 전에 앞의 노드인 prev 노드가 삭제 대상의 다음 노드를 가리키도록 만들어 놓고 삭제 대상인 노드를 삭제하였다.

이해하기 어렵다면 위의 그림을 역순으로 보면 이해가 쉽다?

리스트의 동작 결과

자 이제 이렇게 만든 리스트의 동작 결과를 보도록 하자

int main(int argc, char * argv[]){
    LinkedList list;
    
    for (int i = 0; i < 5; i++)
        list.insert_node((i + 1) * 10);
    list.insert_node(100, 30);
    list.insert_node(200, 90);
    // 10 20 30 100 40 50 200
    list.print_list();
    
    list.search_node(10); // 10을 찾음
    list.search_node(100); // 100을 찾음
    list.search_node(1000); // 해당 노드를 찾지 못함
    
    list.delete_node(50); // 50삭제
    list.print_list();
    list.delete_node(300); // 해당 노드를 찾지 못함
    
    return 0;
}

잘 동작한다