[Data Structure] 연결 리스트(LinkedList)

- 연결 리스트

 연결 리스트(Linked List)는 배열과 같이 스택, 큐 등 자료 구조들의 기반이 될 수 있는 자료 구조입니다. 연결 리스트는 정보를 담고 있는 노드와 각 노드들의 논리적인 연결로 구성됩니다. 노드는 정보를 구성하는 데이터와 다음 노드와의 논리적인 연결을 지원하는 변수로 구성됩니다. 변수는 C 언어의 포인터와 같은 개념으로 정의 되고 변수에는 다음 노드의 주소값이 할당됩니다.

 head는 첫 node의 주소값을 갖고 있는 변수입니다. head는 연결 리스트의 각 노드를 방문하기 위한 첫 시작이라고 할 수 있습니다. head의 값을 잃어버린다면 그 리스트에 다시 접근하는 것은 불가능합니다. 그리고 이 연결 리스트는 메모리 어딘가에 표류하게 됩니다. 각 node는 자료 구조(연결 리스트)를 이용해서 프로그래머가 실질적으로 사용하고자하는 Data를 갖고 있습니다. Data는 객체, 원시 타입의 변수(int, float 등)가 될 수 있습니다. 또한, node는 다음 node의 주소값을 갖고 있는 Next(C 언어의 포인터)변수를 갖고 있습니다. Next는 다음 노드와 논리적인 연결을 가능하게하는 변수 입니다. 만약 중간에 어떤 node에서 Next 값을 잃어버린다면 그 연결 리스트는 그 부분부터 단절됩니다. 그리고 head의 값을 잃어버리는 것과 마찬가지로 연결이 끊긴 리스트는 메모리 어딘가에 표류하게 됩니다.

- 연결 리스트의  노드 탐색

 연결 리스트는 기본적으로 소시지와 같이 일자로 이어진 모양으로 구성됩니다. 그렇기 때문에 마지막 노드까지 도달하기 위해서 모든 노드를 거쳐서 이동해야 합니다. 이동은 기본적으로 노드의 주소값을 할당할 수 있는 변수(포인터)를 이용해서 이동합니다.

void BasicLinkedList::printBasicNode(){
    Node* nowNode = head;
    
    if(head == NULL){
        cout << "List is Empty\n";
        return;
    }
    
    do{
        cout << nowNode->data << "->";
        nowNode = nowNode->next;
    }while(nowNode != NULL);
    cout << endl;
}

 모든 노드를 방문하며 어떤 데이터가 있는지 출력해주는 코드입니다. 가장 주목해야 하는 부분은 11번 라인입니다. 현재 노드의 다음 노드를 nowNode라는 포인터 변수에 할당하고 있습니다. 이를 통해서 다음 노드를 탐색할 수 있습니다. while문은 현재 노드가 NULL이 아닌 동안에 동작합니다.

- 연결 리스트의 노드 삽입

 연결 리스트에 새로운 노드를 삽입할 때, 삽입할 위치를 확인하고 해당 위치에서 앞 노드와 뒤 노드의 연결을 수정하면서 진행됩니다. 그림을 보면서 설명하겠습니다.

< 출처 : https://en.wikipedia.org/wiki/Linked_list >

 newNode는 12 node와 99 node 사이에 삽입되려고 합니다. 이 경우에 12 node의 next 변수(포인터)의 연결은 newNode로 변경해주는 단순한 연산으로 newNode를 삽입할 수 있습니다. 이 경우에 논리적인 순서가 매우 중요합니다. 먼저 newNode의 next 변수(포인터)에 99 node의 주소값을 할당합니다. 99 node의 주소값은 12 node의 next변수에 할당된 값 입니다. 그리고 12 node의 next 변수의 값을 newNode의 주소값으로 변경해주면 newNode의 삽입 연산은 완료됩니다. 코드를 보겠습니다.

void BasicLinkedList::addBasicNode(int inputData){
    Node* newNode = (Node *)malloc(sizeof(Node));
    Node* nowNode = head;
    
    newNode->data = inputData;
    newNode->next = NULL;
    
    if(head == NULL){
        head = newNode;
    }else{
        while(nowNode->next != NULL){
            nowNode = nowNode->next;
        }
        nowNode->next = newNode;
    }
    size++;
}

 해당 코드는 2가지의 경우로 경우의 수를 나누었습니다. 먼저 연결 리스트가 비어있을 경우(8번 라인)와 연결 리스트가 비어있지 않을 경우(10번 라인)로 나누었습니다. 첫번째 경우에는 head에 새로운 노드의 주소값을 할당해주고 마무리했습니다. 그리고 두번째의 경우에는 제일 마지막 노드를 탐색(11번 라인 ~ 13번 라인)하고 마지막 노드(nowNode)의 next 변수에 newNode의 주소값을 할당해주며 마무리했습니다. 중간에 삽입하는 방법은 노드가 삽입될 위치를 찾고, newNode의 next 변수에 nowNode->next 값을 할당한 후에 nowNode->next 변수에 newNode의 주소값을 할당해주면 마무리됩니다. 중간에 삽입하는 방법은 해당 코드에는 존재하지 않습니다.

- 연결 리스트의 노드 삭제

 연결 리스트의 노드를 삭제하는 방법도 다른 연산들과 마찬가지로 먼저 삭제할 데이터를 갖고 있는 노드를 찾는것 부터 시작합니다. 그리고 연결된 노드들의 연결을 적절히 끊어주어서 연산은 마무리합니다. 그림을 보며 알아보겠습니다.

< 출처 : https://en.wikipedia.org/wiki/Linked_list >

 먼저 프로그래머가 삭제를 원하는 노드인 99 node를 탐색 합니다. 그리고 앞 노드인 12 node의 next 변수에 99 node의 next 변수값을 할당합니다. 이렇게 되면 12 node는 99 node와 연결된 상태가 아닌 37 node와 연결된 상태가 됩니다. 그리고 99 node의 메모리를 해제하고 연산을 마무리합니다. 코드를 보겠습니다.

void BasicLinkedList::deleteBasicNode(int garbageData){
    Node* nowNode = head;
    Node* priorNode = head;
    bool isGarbageData = false;
    
    if(head == NULL){
        cout << "List is Empty\n";
        return;
    }
    
    do{
        if(nowNode->data == garbageData){
            isGarbageData = true;
            break;
        }
        priorNode = nowNode;
        nowNode = nowNode->next;
    }while(nowNode != NULL);
    
    if(isGarbageData == false){
        cout << "The GarbageData isn't in The List\n";
        return;
    }
    
    if(nowNode->data == head->data){
        head = nowNode->next;
    }else {
        priorNode->next = nowNode->next;
    }
    free(nowNode);
}

 다른 연산에비해서 복잡해 보이지만 코드를 나눠서 보면 단순합니다. 먼저 do~while문에서 삭제할 데이터를 갖고 있는 노드가 있는지 탐색합니다. 이 경우에 현재 탐색된 노드(nowNode)와 선행 노드(priorNode)의 값을 변경하며 탐색했습니다. priorNode와 nowNode를 따로 선언한 이유는 마지막에 노드를 삭제할 때, 삭제되는 노드가 어떤 것인지 명확하게 보여주기 위해서 입니다. 삭제할 데이터를 갖고 있는 노드를 찾았다면 해당 노드가 맨 앞에 위치한 노드인지(head와 연결된 노드)를 확인합니다. 맨 앞에 위치한 노드라면 head의 값을 nowNode 다음 노드의 주소값으로 변경합니다. 맨 앞에 위치한 경우가 아니라면, 삭제될 데이터를 갖고 있는 노드의 앞 노드(priorNode)의 next 변수에 삭제될 노드(nowNode)의 next 값(삭제될 노드의 다음 노드)을 할당합니다. 그리고 마지막에 삭제될 노드(nowNode)를 메모리에서 해제하고 마무리합니다.

- hpp 소스 코드

#ifndef BasicLinkedList_hpp
#define BasicLinkedList_hpp

#include 
#include 
using namespace std;

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

class BasicLinkedList{
private:
    Node* head;
    int size;
    
public:
    BasicLinkedList();
    void addBasicNode(int inputData);
    void deleteBasicNode(int garbageData);
    void printBasicNode();
};

#endif /* BasicLinkedList_hpp */

- cpp 코드

#include "BasicLinkedList.hpp"

BasicLinkedList::BasicLinkedList(){
    size = 0;
    head = NULL;
}

void BasicLinkedList::addBasicNode(int inputData){
    Node* newNode = (Node *)malloc(sizeof(Node));
    Node* nowNode = head;
    
    newNode->data = inputData;
    newNode->next = NULL;
    
    if(head == NULL){
        head = newNode;
    }else{
        while(nowNode->next != NULL){
            nowNode = nowNode->next;
        }
        nowNode->next = newNode;
    }
    size++;
}

void BasicLinkedList::deleteBasicNode(int garbageData){
    Node* nowNode = head;
    Node* priorNode = head;
    bool isGarbageData = false;
    
    if(head == NULL){
        cout << "List is Empty\n";
        return;
    }
    
    do{
        if(nowNode->data == garbageData){
            isGarbageData = true;
            break;
        }
        priorNode = nowNode;
        nowNode = nowNode->next;
    }while(nowNode != NULL);
    
    if(isGarbageData == false){
        cout << "The GarbageData isn't in The List\n";
        return;
    }
    
    if(nowNode->data == head->data){
        head = nowNode->next;
    }else {
        priorNode->next = nowNode->next;
    }
    free(nowNode);
}

void BasicLinkedList::printBasicNode(){
    Node* nowNode = head;
    
    if(head == NULL){
        cout << "List is Empty\n";
        return;
    }
    
    do{
        cout << nowNode->data << "->";
        nowNode = nowNode->next;
    }while(nowNode != NULL);
    cout << endl;
}