[YYBASIC0306/얌얌코딩] 링크드 리스트 클래스 만들기

C++ 이중 연결 리스트 구현: `std::list` 클론 코딩

C++의 `std::list`와 유사한 기능을 하는 이중 연결 리스트를 직접 구현해 보았습니다.

커스텀 리스트를 만들면서 `push_front()`와 `push_back()` 기능을 구현하였습니다.

---

이중 연결 리스트란?

이중 연결 리스트(Doubly Linked List)는 각 노드가 두 개의 포인터(`front`, `back`)를 가지는 구조입니다.

• `front` : 이전 노드를 가리키는 포인터
• `back` : 다음 노드를 가리키는 포인터

이러한 구조를 활용하면 앞쪽과 뒤쪽에서 노드를 자유롭게 추가/삭제할 수 있습니다.

구현 코드

아래 코드는 `ya::list`라는 이름의 커스텀 이중 연결 리스트를 구현한 것입니다.

// YYBASIC03_06
#include <iostream>
#include <list>

// std::list와 유사한 기능을 하는 커스텀 list 구현 (이중 연결 리스트)
namespace ya
{
    template <typename T>
    class list
    {
    public:
        // 노드 구조체 (이중 연결 리스트의 요소)
        struct Node
        {
            T data;      // 데이터 저장
            Node* back;  // 다음 노드를 가리키는 포인터
            Node* front; // 이전 노드를 가리키는 포인터
        };

        // 생성자 : 객체가 생성될 때 (메모리에 할당될 때) 자동으로 호출되는 함수
        list()
        {
            mHead = nullptr;
            mTail = nullptr;
        }

        // 소멸자 : 객체가 사라질 때 (메모리에 해제될 때) 자동으로 호출되는 함수
        // - 동적으로 할당된 메모리를 해제하여 메모리 누수 방지
        ~list()
        {
            Node* cur = mHead;
            while (cur != nullptr)
            {
                Node* tmp = cur;
                cur = cur->back;
                delete tmp;     // 동적으로 생성된 노드 삭제
            }
        }

        // 리스트 처음에 새로운 노드 추가
        void push_front(T data)
        {
            // 리스트가 비어 있는 경우 (첫 번째 노드 추가)
            if (mHead == nullptr)
            {
                mHead = new Node(); // 새로운 데이터를 담을 객체 생성
                mHead->data = data;
                mHead->back = nullptr;
                mHead->front = nullptr;

                mTail = mHead;
            }
            // 기존 노드가 있는 경우
            else
            {
                /*
                mHead->front = new Node();  // 새로운 데이터를 담을 객체 생성
                mHead->front->data = data;
                mHead->front->back = mHead;     // 새로운 노드는 맨 처음 노드가 되므로 기존 헤드가 새로 추가된 노드의 back이 됨
                mHead->front->front = nullptr;  // 새로운 노드 앞에는 아무것도 없으므로 새로 추가된 노드의 front는 nullptr이 됨

                mHead = mHead->front;   // 헤드 변경
                */

                // 가독성과 유지보수성을 고려한 방법
                Node* newNode = new Node();
                newNode->data = data;
                newNode->back = mHead;
                newNode->front = nullptr;   // 리스트의 첫 번째 노드가 되므로 front가 nullptr이 됨

                mHead->front = newNode; // 기존 헤드의 front를 새 노드로 설정
                mHead = newNode;        // 헤드를 새 노드로 변경
            }
        }

        // 리스트 끝에 새로운 노드 추가
        void push_back(T data)
        {
            // 리스트가 비어 있는 경우 (첫 번째 노드 추가)
            if (mHead == nullptr)
            {
                mHead = new Node(); // 새로운 데이터를 담을 객체 생성
                // (*mHead).data = data;
                mHead->data = data;
                mHead->back = nullptr;
                mHead->front = nullptr;

                mTail = mHead;  // 첫 번째 노드는 헤드이자 테일
            }
            // 기존 노드가 있는 경우
            else
            {
                mTail->back = new Node(); // 새로운 데이터를 담을 객체 생성
                mTail->back->data = data;
                mTail->back->back = nullptr;    // 새로운 노드는 마지막 노드가 되므로 back은 nullptr
                mTail->back->front = mTail;     // 새 노드의 front는 기존 마지막 노드

                mTail = mTail->back;    // 테일 변경
            }
        }

        // 리스트를 처음부터 끝까지 출력
        void print()
        {
            Node* cur = mHead;

            while (cur != nullptr)
            {
                std::cout << cur->data << " ";
                cur = cur->back;
            }
            std::cout << "\\n";
        }

    private:
        Node* mHead;
        Node* mTail;
    };
}

int main()
{
    std::list<int> stlList; // 생성자 호출
    stlList.push_back(10);
    stlList.push_back(20);
    stlList.push_front(-10);

    ya::list<int> yaList;
    yaList.push_back(1);
    yaList.push_back(2);
    yaList.push_back(3);

    std::cout << "Custom Linked List : ";
    yaList.print();

    int* p = new int;
    // p 자체 : 지역 변수 - 스택에 저장됨
    // new int : 동적으로 메모리 할당 - 힙에 메모리 공간이 생성됨
    // int* p = new int; : 힙 영역의 '주소'를 저장하는 포인터

    delete p;   // 메모리 누수 방지를 위해 삭제

    return 0; // 소멸자 호출
}

`push_front(T data)` 함수

: 리스트의 맨 앞에 새로운 노드를 추가하는 함수입니다.

• 리스트가 비어 있는 경우: 첫 번째 노드를 추가하는 것이므로 새 노드를 생성하고 `mHead`와 `mTail`을 같은 노드로 설정합니다.
• 기존 노드가 있는 경우: 새 노드를 `mHead->front`에 추가한 뒤, `mHead`를 새 노드로 변경합니다.

이중 연결 리스트에서 `push_front()` 함수를 구현할 때, 새로운 노드를 추가하는 방식에 따라 두 가지 방법이 있습니다.

각 방식의 차이점을 살펴보고, 어떤 방식이 더 유지보수성과 가독성이 좋은지 알아보겠습니다.

 

// 직접 할당 방식 (mHead->front = new Node();) 을 이용한 구현

void push_front(T data)
{
    if (mHead == nullptr) // 리스트가 비어 있는 경우 (첫 번째 노드 추가)
    {
        mHead = new Node();
        mHead->data = data;
        mHead->back = nullptr;
        mHead->front = nullptr;
        mTail = mHead;
    }
    else // 기존 노드가 있는 경우
    {
        mHead->front = new Node(); // 새 노드 동적 할당
        mHead->front->data = data;
        mHead->front->back = mHead; // 기존 헤드를 back으로 설정
        mHead->front->front = nullptr; // 리스트의 첫 번째 노드이므로 front는 nullptr

        mHead = mHead->front; // 헤드를 새 노드로 변경
    }
}

장점

• 코드가 조금 더 짧아지고 간결해집니다.
• 추가적인 변수를 선언하지 않아 메모리 사용량이 조금 절약됩니다.

단점

• `mHead->front`에 바로 `new Node();`를 할당하면 가독성이 떨어질 수 있습니다.
• `mHead->front`가 새로운 노드를 가리킨다는 점이 명확하지 않아 디버깅이 어려울 가능성이 있습니다.
• 가독성이 떨어지면 유지보수할 때 예기치 못한 버그를 만들 가능성이 증가합니다.

`mHead->front`가 새로운 노드를 가리킨다는 점이 명확하지 않다는 것은 코드의 흐름이 직관적이지 않다는 것을 의미합니다.

mHead->front = new Node();  // (1) 새로운 노드 생성
mHead->front->data = data;
mHead->front->back = mHead;  // (2) 기존 헤드를 back으로 설정
mHead->front->front = nullptr;  // (3) 첫 번째 노드이므로 front는 nullptr
mHead = mHead->front;  // (4) 새로운 노드를 헤드로 변경

• (1)에서 새로운 노드를 `mHead->front`에 할당하고 있지만, 어떤 객체가 생성되고 있는지 직접적으로 명시되지 않습니다.
• 즉, 새로운 노드를 생성해서 기존 헤드 앞에 배치하는 과정이 한 줄에서 이루어지기 때문에 논리적으로 직관적이지 않습니다.
• 특히, `mHead = mHead->front;` 라인은 기존 `mHead`의 상태가 이미 변경된 후에야 새로운 헤드를 가리키게 돼 코드의 흐름이 직관적이지 않습니다.

 

// newNode 변수를 활용하는 방식

void push_front(T data)
{
    if (mHead == nullptr)
    {
        mHead = new Node();
        mHead->data = data;
        mHead->back = nullptr;
        mHead->front = nullptr;
        mTail = mHead;
    }
    else
    {
        Node* newNode = new Node(); // 새 노드 생성
        newNode->data = data;
        newNode->back = mHead;
        newNode->front = nullptr; // 리스트의 첫 번째 노드이므로 front는 nullptr

        mHead->front = newNode; // 기존 헤드의 front를 새 노드로 설정
        mHead = newNode; // 헤드를 새 노드로 변경
    }
}

장점

• 코드의 가독성이 좋아집니다 : `newNode` 변수를 활용하면 새로운 노드를 생성하는 과정이 명확해집니다.
• 디버깅할 때 특정 노드가 어떤 상태인지 쉽게 확인 가능해집니다.
• 향후 기능 추가 및 유지보수 시 수정이 용이합니다.

단점

• 코드 길이가 약간 길어집니다

Node* newNode = new Node();  // (1) 새로운 노드 생성
newNode->data = data;
newNode->back = mHead;  // (2) 기존 헤드를 back으로 설정
newNode->front = nullptr;  // (3) 첫 번째 노드이므로 front는 nullptr
mHead->front = newNode;  // (4) 기존 헤드의 front를 새로운 노드로 설정
mHead = newNode;  // (5) 새로운 노드를 헤드로 변경

`newNode` 를 사용한 방식의 경우

• (1)~(3)에서 새로운 노드를 먼저 생성하고, 데이터를 설정하는 과정이 분리되어 있습니다.
• (4)~(5)에서야 기존 `mHead`와 연결하는 과정이 진행되어 어떤 객체를 생성하고 있는지가 직관적으로 보여 이 노드가 무엇을 하는지 명확해집니다.

 

push_back(T data) 함수

: 리스트의 맨 뒤에 새로운 노드를 추가하는 함수입니다.

• 리스트가 비어 있는 경우: 첫 번째 노드를 추가하는 것이므로 새 노드를 생성하고 `mHead`와 `mTail`을 같은 노드로 설정합니다.
• 기존 노드가 있는 경우: 새 노드를 `mTail->back`에 추가한 뒤, `mTail`을 새 노드로 변경합니다.

print() 함수

: `mHead`부터 `nullptr`을 만날 때까지 데이터를 출력하는 함수입니다.

 

// stlList 디버깅

 

// 실행 결과

 

LV11 링크드리스트 (linked list) 만들어보기