샷건치며 배우는 자료구조 with C++, 8화

노드를 기반으로 하는 자료구조, 링크드 리스트에 대해 알아봅시다.

읽어주세요

자료구조를 배우기 위해 위대한 항로(?)를 넘어 여기까지 오신 분들 환영합니다. 본 게시글은 자료구조를 공부하면서 복습 겸 정리하기 위해 작성하였습니다. 개인적으로 강좌 형식 및 장난을 섞어가며 작성하는 걸 좋아하기 때문에 진지한 게시글을 원하신다면 뒤로 가기를 눌러주세요.

C++ 언어를 기반으로 하고 있습니다. 다른 프로그래밍 언어를 사용 중이신 경우 개념(이론)을 배우는 데 큰 문제는 없지만, 실제 코드로 구현할 땐 생각보다 차이가 있을 수 있습니다.

업데이트

1. C 언어 구현 내용 제거
   • 게시글의 내용이 너무 복잡해져 제거하였습니다.

게시글 개선을 위해 임시 숨김 처리

링크드 리스트

링크드 리스트^{Linked List}는 데이터를 저장하는 선형 자료구조로, 배열과는 다른 방식으로 요소를 관리합니다. 배열은 연속적인 메모리 공간에 데이터를 저장하는 반면, 링크드 리스트는 노드라는 개별 단위로 데이터를 저장하고, 각 노드가 다음 노드와 연결된(Linked) 형태를 띄고 있습니다.

링크드 리스트는 크게 세 가지로 구분됩니다. 각 노드가 다음 노드만을 가리키는 단일 링크드 리스트, 각 노드가 이전 노드와 다음 노드를 가리키는 이중 링크드 리스트, 마지막 노드가 첫 번째 노드와 연결된 구조를 갖는 원형 링크드 리스트입니다.

노드

노드 연결 구성

노드^Node는 링크드 리스트에서 사용되는 기본 구성 단위입니다.

각 노드는 데이터를 저장하고, 다른 노드와의 연결 정보를 갖습니다. C/C++ 언어에서 노드는 보통 구조체 또는 클래스로 구현합니다.

• 데이터: 노드가 실제로 저장하는 값입니다. 정수, 실수, 문자, 구조체 등 다양한 데이터 타입을 사용할 수 있습니다.
• 포인터: 이전 노드 또는 다음 노드 등을 가리키는 포인터 변수입니다. 이를 통해 노드가 서로 연결됩니다.

각 노드는 다음 또는 이전 노드를 가리키는 포인터를 갖기 때문에 서로 연결된 형태를 보입니다. 마치 기차 칸들이 연결되어 있는 것처럼 말이죠. 각 칸(노드)은 다음 칸(노드)으로 가는 길(포인터)을 알고 있을 수 있습니다.

위 사진은 단일 링크드 리스트의 노드 모습입니다. 1번 다음 2번, 2번 다음 3번 순으로 노드가 연결되어 있는 걸 확인할 수 있습니다.

특징

• 유연

  ---

  크기가 고정된 배열과는 달리, 동적 메모리 할당을 이용하기 때문에 실행 중에 원하는 만큼 데이터를 추가 및 제거할 수 있습니다.

• 비연속적

  ---

  기본적으로 동적 메모리 할당을 이용하기 때문에 메모리 공간이 연속적으로 할당되지 않습니다.

• 빠른 추가 및 제거 속도

  ---

  중간 삽입을 제외하고, 이중 링크드 리스트 기준으로 데이터를 삽입 및 제거하는 속도가 \(O(1)\)으로 빠릅니다.

• 느린 탐색 속도

  ---

  인덱스가 없기 때문에 원하는 데이터를 찾으려면 순차적으로 접근해야 합니다. \(O(n)\)의 시간복잡도가 발생합니다.

단일 링크드 리스트

단일 링크드 리스트^{Singly Linked List}는 링크드 리스트의 가장 기본적인 형태로, 각 노드가 하나의 데이터와 다음 노드를 가리키는 포인터를 갖는 선형 자료구조입니다. 노드는 단방향(하나의 방향)으로 연결되어 있어, 한 노드에서 다음 노드로 갈 수 있지만 그 반대는 불가합니다.

각 노드는 다음 노드만을 가리키기 때문에, 리스트를 순회할 때 항상 헤드^Head(1)에서 시작해야 합니다.

1. 단일 링크드 리스트의 첫 번째 노드를 가리키는 포인터

기본 구성

//! @brief 노드
class Node {
private:
    int data;                       //!< 데이터
    Node* next;                     //!< 다음 노드를 가리키는 포인터
public:
    friend class SinglyLinkedList;  //!< SinglyLinkedList에서 접근하기 위해 필요

    //! @brief 생성자
    //! @param value 값
    Node(int value) noexcept {
        this->data = value;
        this->next = nullptr;
    }
};

//! @brief 단일 링크드 리스트
class SinglyLinkedList {
private:
    Node* m_Head;                   //!< 헤드 노드
    int m_Size;                     //!< 크기 (리스트 요소의 수)

public:
    //! @brief 생성자
    SinglyLinkedList() noexcept {
        m_Head = nullptr;
        m_Size = 0;
    }

    //! @brief 소멸자
    ~SinglyLinkedList() noexcept {
        Clear();
    }
};

단일 링크드 리스트의 기본 구성입니다.

노드는 데이터를 갖는 변수와 다음 노드를 가리키는 포인터 변수를 갖습니다.

단일 링크드 리스트는 첫 번째 노드를 가리키는 포인터 변수 헤드(head)와 요소의 수를 기록하는 size 변수를 갖습니다. head의 값이 NULL이거나 size 변수의 값이 0이라면 리스트가 비어있음을 나타냅니다.

기본 연산

노드 삽입

appendprependinsertAt

append 연산은 리스트의 맨 끝에 새 노드를 추가합니다.

리스트의 끝까지 가기 위해 모든 노드를 순회하기 때문에 시간 복잡도는 \(O(n)\)입니다.

classstd::forward_list

class SinglyLinkedList {
    // ...

    //! @brief 리스트의 맨 끝에 새 노드를 추가하는 메서드
    //! @param value 값
    void Append(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있다면
        if (m_Head == nullptr) {
            m_Head = newNode;
            m_Size += 1;                    // 크기 증가
            return;
        }

        // (3) 리스트가 비어 있지 않다면
        auto* current = m_Head;             // 헤드에서 시작
        while (current->next != nullptr) {  // 마지막 노드까지 이동
            current = current->next;
        }
        current->next = newNode;            // 마지막 노드의 다음 노드를 새 노드로

        // (4) 크기 증가
        m_Size += 1;
    }
};

1. 새 노드 생성

   새 노드를 생성합니다. nullptr인 것을 사전에 검사하여 오류가 발생할 수 있는 상황을 차단합니다.

2. 리스트가 비어 있다면

   m_Head가 nullptr라면 리스트가 비어 있다는 의미입니다. 비어 있는 상태에서 새 노드를 추가하는 건 첫 노드인 것과 마찬가지입니다.

   m_Head에 newNode를 할당한 후 크기를 1 증가시킵니다.

3. 리스트가 비어 있지 않다면

   m_Head에서 시작하여 다음 노드가 nullptr가 아닐 때까지 반복하여 순회합니다. nullptr를 만나면 다음 노드가 없다는 것을 의미하며, 마지막 노드에 도달했음을 나타냅니다.

   마지막 노드의 다음에(current->next) newNode를 할당하여 새 노드를 추가(연결)합니다.

   Tip

   m_Head == nullptr 연산 대신 m_Size == 0 연산으로 대체해도 됩니다. 두 조건식 모두 리스트가 비어 있음을 나타냅니다.

4. 크기 증가

   새 노드가 추가되었으니 크기를 1 증가시킵니다.

#include <forward_list>
#include <iostream>

int main(int argc, char* argv[]) {
    // 단일 링크드 리스트
    std::forward_list<int> sll;

    return 0;
}

C++은 std::forward_list라는 단일 링크드 리스트 컨테이너를 제공합니다.

다만, append 연산을 제공하지 않습니다. 왜냐하면 마지막에 추가하려면 모든 노드를 순회해야 하기 때문에 비효율적입니다.

prepend 연산은 리스트의 처음에 새 노드를 추가합니다.

리스트의 길이, 순회와는 상관없기 때문에 시간 복잡도는 \(O(1)\)입니다.

새 노드가 헤드가 된다

classstd::forward_list

class SinglyLinkedList {
    // ...

    //! @brief 리스트의 처음에 새 노드를 추가하는 함수
    //! @param value 값
    void Prepend(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 새 노드의 다음 노드를 기존의 헤드를 가리키도록
        newNode->next = m_Head;

        // (3) 기존의 헤드를 새 노드로
        m_Head = newNode;

        // (4) 크기 증가
        m_Size += 1;
    }
};

1. 새 노드 생성

   새 노드를 생성합니다. nullptr인 것을 사전에 검사하여 오류가 발생할 수 있는 상황을 차단합니다.

2. 새 노드의 다음 노드를 기존의 헤드를 가리키도록

   기존의 헤드는 새 노드의 다음이 되기 때문에, 새 노드의 다음(newNode->next)을 기존의 헤드를 가리키도록 합니다.

3. 기존의 헤드를 새 노드로

   새 노드가 헤드가 되기 때문에, 현재 헤드를 새 노드로 변경합니다.

4. 크기 증가

   새 노드가 추가되었으니 크기를 1 증가시킵니다.

// ...

int main(int argc, char* argv[]) {
    // 단일 링크드 리스트
    std::forward_list<int> sll;

    // 앞에 데이터 추가
    sll.push_front(3);
    sll.push_front(2);
    sll.push_front(1);
    sll.push_front(0);

    // 출력
    for (auto n : sll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

push_front 메서드를 사용해 리스트의 맨 앞에 새 노드를 추가할 수 있습니다.

insertAt 연산은 리스트의 특정 위치에 새 노드를 추가하며, 사용자로부터 인덱스를 넘겨받습니다.

단일 링크드 리스트는 단방향이기 때문에 삽입하려는 위치의 직전(이전) 노드를 찾아야 합니다. 즉 탐색 과정을 거치기 때문에 인덱스가 0이 아니라면 시간 복잡도는 \(O(n)\)입니다.

insertAt

classstd::forward_list

class SinglyLinkedList {
    // ...

    //! @brief 리스트의 특정 위치에 새 노드를 추가하는 메서드
    //! @param index 인덱스
    //! @param value 값
    void InsertAt(int index, int value) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            Prepend(value);
            return;
        }

        // (3) 삽입 위치의 이전 노드 찾기
        auto* current = m_Head;
        int currentIndex = 0;

        while (current != nullptr && currentIndex < (index - 1)) {
            current = current->next;
            currentIndex += 1;
        }

        // (4) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (5) 새 노드의 다음을 삽입 위치의 이전 노드의 다음을 가리키기
        newNode->next = current->next;

        // (6) 삽입 위치의 이전 노드의 다음을 새 노드를 가리키기
        current->next = newNode;

        // (7) 크기 증가
        m_Size += 1;
    }
};

1. 인덱스 범위 검사

   인덱스가 음수이거나 리스트의 수를 초과하면 삽입 연산을 수행하지 않도록 합니다.

   index >= size로 수행하지 않는 이유는 직전 노드(index -1)를 찾아야하기 때문에 그렇습니다.

2. 인덱스가 0이라면

   인덱스가 0이라면 리스트의 처음에 새 노드를 추가하겠다는 뜻입니다. prepend 연산을 수행하여 노드를 추가합니다.

3. 삽입 위치의 이전 노드 찾기

   이전 노드에서 새 노드를 가리키고, 새 노드에서 이전 노드의 다음을 가리키기 위해 삽입 위치의 이전 노드를 찾습니다.

4. 새 노드 생성

   새 노드를 생성합니다. nullptr인 것을 사전에 검사하여 오류가 발생할 수 있는 상황을 차단합니다.

5. 새 노드의 다음을 삽입 위치의 이전 노드의 다음을 가리키기

   이전 노드와 이전 노드 다음 그 사이에 새 노드가 삽입되기 때문에 새 노드의 다음을 이전 노드의 다음을 가리키도록 합니다.

6. 삽입 위치의 이전 노드의 다음을 새 노드를 가리키기

   이전 노드와 이전 노드 다음 그 사이에 새 노드가 삽입되기 때문에 이전 노드의 다음을 새 노드를 가리키도록 합니다.

7. 크기 증가

   새 노드가 추가되었으니 크기를 1 증가시킵니다.

forward_list_insert_at.cpp

// ...

int main(int argc, char* argv[]) {
    // 단일 링크드 리시트
    std::forward_list<int> sll;

    // 앞에 데이터 추가
    sll.push_front(40);
    sll.push_front(20);
    sll.push_front(10);
    sll.push_front(0);

    // 중간 데이터 추가
    auto it = std::next(sll.begin(), 2);
    sll.insert_after(it, 30);

    // 출력
    for (auto n : sll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

std::next(sll.begin(), index)로 index번째에 있는 이터레이터를 반환 받습니다.

insert_after(it, value) 형식으로 사용해 index번째에 있는 노드 다음에 새 노드를 추가합니다. 'after'라는 단어를 보시면 알 수 있듯이 해당 위치 뒤에 삽입함을 의미합니다.

노드 삭제

deleteBegindeleteEnddeleteAtclear

deleteBegin 연산은 리스트의 첫 노드를 제거합니다.

리스트의 길이, 순회와는 상관없기 때문에 시간 복잡도는 \(O(1)\)입니다.

제거 과정

classstd::forward_list

class SinglyLinkedList {
    // ...

    //! @brief 리스트의 첫 노드를 제거하는 메서드
    void DeleteBegin() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 제거할 헤드 노드 임시 보관
        auto* temp = m_Head;

        // (3) 헤드 노드를 헤드 노드의 다음을 가리킨다
        m_Head = m_Head->next;

        // (4) 헤드 노드 제거
        delete temp;

        // (5) 크기 감소
        m_Size -= 1;
    }
};

1. 리스트가 비어 있다면

   리스트가 비어 있다면 제거할 노드가 없음을 나타냅니다. 아무 처리도 하지 않고 return하도록 합니다.

2. 제거할 헤드 노드 임시 보관

   제거 대상인 헤드 노드를 temp에 임시로 보관합니다. 제거하기 전 헤드 노드를 변경해야 하기 때문입니다.

3. 헤드 노드를 헤드 노드의 다음을 가리킨다

   m_Head에 m_Head->next를 할당합니다. 즉 제거 대상인 헤드 노드의 다음 노드를 헤드로 만듭니다.

4. 헤드 노드 제거

   노드는 동적 할당되었으니 delete로 동적 할당을 해제합니다.

5. 크기 감소

   노드가 제거되었으니 크기를 1 감소시킵니다.

// ...

int main(int argc, char* argv[]) {
    // 단일 링크드 리스트
    std::forward_list<int> sll;

    // 맨 앞 데이터 추가
    sll.push_front(40);
    sll.push_front(30);
    sll.push_front(20);
    sll.push_front(10);
    sll.push_front(0);

    // 맨 앞 데이터 제거
    sll.pop_front();
    sll.pop_front();
    sll.pop_front();

    // 출력
    for (auto n : sll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

pop_front() 메서드를 호출하여 맨 앞의 노드를 제거할 수 있습니다.

deleteEnd 연산은 리스트의 마지막 노드를 제거합니다.

리스트의 끝까지 가기 위해 모든 노드를 순회하기 때문에 시간 복잡도는 \(O(n)\)입니다.

이전 노드 찾는 과정

classstd::forward_list

class SinglyLinkedList {
    // ...

    //! @brief 리스트의 마지막 노드를 제거하는 메서드
    void DeleteEnd() noexcept {
        // (1) 리스트가 비어 있는 지 확인
        if (m_Head == nullptr) { return; }

        // (2) 리스트에 노드가 하나 뿐인 지 확인
        if (m_Head->next == nullptr) {      // 다음 노드가 없는 지 확인
            delete m_Head;                  // 제거
            m_Head = nullptr;               // 댕글링 포인터 방지 및 리스트 비어있음 명시
            m_Size = 0;                     // 리스트 비어있음 명시
            return;
        }

        // (3) 마지막 노드의 이전 노드까지 이동
        auto* current = m_Head;
        while (current->next->next != nullptr) {
            current = current->next;
        }

        // (4) 제거
        auto* temp = current->next;         // 삭제할 마지막 노드 임시 보관
        current->next = nullptr;            // 이전 노드의 next 노드 없음
        delete temp;                        // 제거
        m_Size -= 1;                        // 크기 감소
    }
};

1. 리스트가 비어 있는 지 확인

   리스트가 비어 있는 지 확인합니다. 비어 있는 상태라면 제거할 노드가 없으니 생략하도록 합니다.

2. 리스트에 노드가 하나 뿐인 지 확인

   리스트에 노드가 하나 뿐인 지 확인합니다.

   리스트에 노드가 하나 뿐이라면 해당 노드가 헤드 노드이자 마지막 노드입니다. 굳이 이전 노드를 찾는 순회 과정을 거칠 필요가 없기 때문에 바로 제거하도록 합니다.

3. 마지막 노드의 이전 노드까지 이동

   현재 노드의 다다음 노드를 확인하여 nullptr이 아니라면 다음 노드로 이동하도록 합니다. 이 과정을 반복하여 마지막 노드의 이전 노드까지 이동할 수 있습니다.

4. 제거

   삭제할 마지막 노드를(current->next)를 temp에 임시로 보관합니다.

   이전 노드(current->next)의 다음 노드는 제거될 예정이기 때문에 다음을 가리킬 노드가 없습니다. nullptr을 할당합니다.

   delete를 호출하여 마지막 노드를 제거합니다. 그리고 m_Size 변수의 값을 1 감소시킵니다.

append 연산과 마찬가지로 맨 끝까지 순회하는 건 비효율적이기 때문에 별도로 맨 끝 노드를 제거하는 메서드가 존재하지 않습니다. 직접 구현해야 합니다.

deleteAt 연산은 리스트의 특정 위치에 있는 노드를 제거하며, 사용자로부터 인덱스를 넘겨 받습니다.

단일 링크드 리스트는 단방향이기 때문에 제거 대상의 노드 위치를 순회하여 찾아야합니다. 시간 복잡도는 \(O(n)\)입니다.

classstd::forward_list

class SinglyLinkedList {
    // ...

    //! @brief 리스트의 특정 위치에 있는 노드를 제거하는 메서드
    //! @param index 인덱스
    void DeleteAt(int index) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index >= m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            DeleteBegin();
            return;
        }

        // (3) 제거 대상 노드의 이전 노드를 찾는다
        auto* current = m_Head;
        int currentIndex = 0;

        while (current != nullptr && currentIndex < (index - 1)) {
            current = current->next;
            currentIndex += 1;
        }

        // (4) 제거
        auto* temp = current->next;     // 제거 대상 노드 임시 보관
        current->next = temp->next;     // 이전 노드의 다음 노드를 제거 대상 노드의 다음 노드를 가리킨다
        delete temp;                    // 제거
        m_Size -= 1;                    // 크기 감소
    }
};

1. 인덱스 범위 검사

   인덱스가 음수이거나 리스트의 수를 초과하면 제거 연산을 수행하지 않도록 합니다.

   insertAt과는 다르게 새 노드 추가가 아닌 기존의 노드를 제거하는 것이기 때문에 리스트의 크기와 같거나 큰 인덱스는 존재하지 않습니다. 그래서 index >= m_Size를 조건식으로 합니다.

2. 인덱스가 0이라면

   인덱스가 0이라면 첫 노드 제거를 의미합니다. DeleteBegin을 호출하여 리스트의 첫 노드를 제거하도록 합니다.

3. 제거 대상 노드의 이전 노드를 찾는다

   제거 대상의 이전 노드를 찾습니다.

4. 제거

   제거 대상의 노드를 temp에 임시로 보관합니다. 그리고 이전 노드의 다음 노드를 제거 대상 노드의 다음을 가리키도록 합니다.

   delete를 호출하여 노드를 제거한 후, 크기를 1 감소시킵니다.

// ...

int main(int argc, char* argv[]) {
    // 단일 링크드 리스트
    std::forward_list<int> sll;

    // 맨 앞 데이터 추가
    sll.push_front(40);
    sll.push_front(30);
    sll.push_front(50);
    sll.push_front(20);
    sll.push_front(10);

    // 중간 데이터 제거
    auto it = std::next(sll.begin(), 1);
    sll.erase_after(it);

    // 출력
    for (auto n : sll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

erase_after() 메서드를 사용해 지우고 싶은 노드의 앞 노드를 제거할 수 있습니다.

만약 이 메서드로 가장 첫 노드를 제거하고 싶다면 그건 불가능합니다. pop_front() 메서드를 사용해야 합니다.

clear 연산은 모든 노드를 순회하며 제거합니다. 모든 노드를 순회하기 때문에 시간 복잡도는 \(O(n)\)입니다.

classstd::forward_list

class SinglyLinkedList {
    // ...

    //! @brief 모든 노드를 제거하는 메서드
    void Clear() noexcept {
        // (1) 리스트가 비어 있는 지 확인
        if (m_Head == nullptr) { return; }

        // (2) 순회 및 제거
        auto* current = m_Head;
        while (current != nullptr) {
            auto* next = current->next;
            delete current;
            current = next;
        }
        m_Head = nullptr;
        m_Size = 0;
    }
};

// ...

int main(int argc, char* argv[]) {
    // 단일 링크드 리스트
    std::forward_list<int> sll;

    // 맨 앞 데이터 추가
    sll.push_front(40);
    sll.push_front(30);
    sll.push_front(20);
    sll.push_front(10);
    sll.push_front(0);

    // 모든 노드 제거
    sll.clear();

    return 0;
}

전체 코드

classstd::forward_list

#include <iostream>

//! @brief 노드
class Node {
private:
    int data;       //!< 데이터
    Node* next;     //!< 다음 노드를 가리키는 포인터

public:
    friend class SinglyLinkedList;      // SinglyLinkedList에서 접근하기 위해 필요

    //! @brief 생성자
    //! @param value 값
    Node(int value) noexcept {
        this->data = value;
        this->next = nullptr;
    }
};

//! @brief 단일 링크드 리스트
class SinglyLinkedList {
private:
    Node* m_Head;       //!< 헤드 노드
    int m_Size;         //!< 크기 (리스트의 요소 수)

public:
    //! @brief 생성자
    SinglyLinkedList() noexcept {
        m_Head = nullptr;
        m_Size = 0;
    }

    //! @brief 소멸자
    ~SinglyLinkedList() noexcept {
        Clear();
    }

    //! @brief 리스트의 맨 끝에 새 노드를 추가하는 메서드
    //! @param value 값
    void Append(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있다면
        if (m_Head == nullptr) {
            m_Head = newNode;
            m_Size += 1;                    // 크기 증가
            return;
        }

        // (3) 리스트가 비어 있지 않다면
        auto current = m_Head;              // 헤드에서 시작
        while (current->next != nullptr) {  // 마지막 노드까지 이동
            current = current->next;
        }
        current->next = newNode;            // 마지막 노드의 다음 노드를 새 노드로

        // (4) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트의 처음에 새 노드를 추가하는 함수
    //! @param value 값
    void Prepend(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 새 노드의 다음 노드를 기존의 헤드를 가리키도록
        newNode->next = m_Head;

        // (3) 기존의 헤드를 새 노드로
        m_Head = newNode;

        // (4) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트의 특정 위치에 새 노드를 추가하는 메서드
    //! @param index 인덱스
    //! @param value 값
    void InsertAt(int index, int value) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            Prepend(value);
            return;
        }

        // (3) 삽입 위치의 이전 노드 찾기
        Node* current = m_Head;
        int currentIndex = 0;

        while (current != nullptr && currentIndex < (index - 1)) {
            current = current->next;
            currentIndex += 1;
        }

        // (4) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (5) 새 노드의 다음을 삽입 위치의 이전 노드의 다음을 가리키기
        newNode->next = current->next;

        // (6) 삽입 위치의 이전 노드의 다음을 새 노드를 가리키기
        current->next = newNode;

        // (7) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트의 첫 노드를 제거하는 메서드
    void DeleteBegin() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 제거할 헤드 노드 임시 보관
        auto* temp = m_Head;

        // (3) 헤드 노드를 헤드 노드의 다음을 가리킨다
        m_Head = m_Head->next;

        // (4) 헤드 노드 제거
        delete temp;

        // (5) 크기 감소
        m_Size -= 1;
    }

    //! @brief 리스트의 마지막 노드를 제거하는 메서드
    void DeleteEnd() noexcept {
        // (1) 리스트가 비어 있는 지 확인
        if (m_Head == nullptr) { return; }

        // (2) 리스트에 노드가 하나 뿐인 지 확인
        if (m_Head->next == nullptr) {      // 다음 노드가 없는 지 확인
            delete m_Head;                  // 제거
            m_Head = nullptr;               // 댕글링 포인터 방지 및 리스트 비어있음 명시
            m_Size = 0;                     // 리스트 비어있음 명시
            return;
        }

        // (3) 마지막 노드의 이전 노드까지 이동
        auto* current = m_Head;
        while (current->next->next != nullptr) {
            current = current->next;
        }

        // (4) 제거
        auto* temp = current->next;         // 삭제할 마지막 노드 임시 보관
        current->next = nullptr;            // 이전 노드의 next 노드 없음
        delete temp;                        // 제거
        m_Size -= 1;                        // 크기 감소
    }

    //! @brief 리스트의 특정 위치에 있는 노드를 제거하는 메서드
    //! @param index 인덱스
    void DeleteAt(int index) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index >= m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            DeleteBegin();
            return;
        }

        // (3) 제거 대상 노드의 이전 노드를 찾는다
        auto* current = m_Head;
        int currentIndex = 0;

        while (current != nullptr && currentIndex < (index - 1)) {
            current = current->next;
            currentIndex += 1;
        }

        // (4) 제거
        auto* temp = current->next;     // 제거 대상 노드 임시 보관
        current->next = temp->next;     // 이전 노드의 다음 노드를 제거 대상 노드의 다음 노드를 가리킨다
        delete temp;                    // 제거
        m_Size -= 1;                    // 크기 감소
    }

    //! @brief 모든 노드를 제거하는 메서드
    void Clear() noexcept {
        // (1) 리스트가 비어 있는 지 확인
        if (m_Head == nullptr) { return; }

        // (2) 순회 및 제거
        auto* current = m_Head;
        while (current != nullptr) {
            auto* next = current->next;
            delete current;
            current = next;
        }
        m_Head = nullptr;
        m_Size = 0;

        std::cout << "\nSinglyLinkedSize: " << m_Size << "\n";
    }

    //! @brief 모든 노드를 순회하여 출력하는 메서드
    void Print() noexcept {
        // (1) 리스트가 비어 있다면 생략
        if (m_Head == nullptr) { return; }

        // (2) 순회 및 출력
        auto* current = m_Head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
    }
};

int main(int argc, char* argv[]) {
    // 단일 링크드 리스트
    SinglyLinkedList sll;

    // 리스트의 끝에 새 노드 추가
    sll.Append(10);
    sll.Append(30);

    // 리스트의 중간에 새 노드 추가
    sll.InsertAt(1, 20);

    // 모든 노드 요소의 값 출력
    sll.Print();

    // 모든 노드 제거
    sll.Clear();

    return 0;
}

#include <forward_list>
#include <iostream>

int main(int argc, char* argv[]) {
    // 단일 링크드 리스트
    std::forward_list<int> sll;

    // 리스트의 처음에 새 노드 추가
    sll.push_front(30);
    sll.push_front(10);

    // 리스트의 중간에 새 노드 추가
    sll.insert_after(std::next(sll.begin(), 0), 20);

    // 출력
    for (auto n : sll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    // 모든 노드 제거
    sll.clear();

    return 0;
}

10 20 30
SinglyLinkedList Size: 0

이중 링크드 리스트

이중 링크드 리스트^{Doubly Linked List}는 각 노드가 데이터와 함께 이전 노드와 다음 노드를 갖는 자료구조입니다.

단일 링크드 리스트는 단방향 탐색만 가능했다면, 이중 링크드 리스트는 헤드와 테일이라는 두 개의 특별한 포인터를 갖아 양방향 탐색이 가능합니다. 헤드^Head는 리스트의 가장 첫 번째 노드를 가리키고, 테일^Tail은 리스트의 가장 마지막 노드를 가리킵니다.

현실 세계의 지하철 열차를 생각하시면 됩니다. 지하철 열차의 칸을 떠올려보세요. 헤드와 테일을 제외한 각 칸은 앞 칸과 뒷 칸이랑 연결되어 있습니다.

기본 구성

//! @brief 노드
class Node {
private:
    int data;               //!< 데이터
    Node* prev;             //!< 이전 노드를 가리키는 포인터
    Node* next;             //!< 다음 노드를 가리키는 포인터

public:
    friend class DoublyLinkedList;  // DoublyLinkedList에서 접근하기 위해 필요

    //! @brief 생성자
    //! @param value 값
    Node(int value) noexcept {
        this->data = value;
        this->prev = this->next = nullptr;
    }
};

//! @brief 이중 링크드 리스트
class DoublyLinkedList {
private:
    Node* m_Head;           //!< 헤드 노드
    Node* m_Tail;           //!< 테일 노드
    int m_Size;             //!< 크기 (리스트의 요소 수)

public:
    //! @brief 생성자
    DoublyLinkedList() noexcept {
        m_Head = m_Tail = nullptr;
        m_Size = 0;
    }

    //! @brief 소멸자
    ~DoublyLinkedList() noexcept {
        Clear();
    }
};

이중 링크드 리스트의 기본 구성입니다.

노드는 데이터를 갖는 변수와 이전 노드를 가리키는 포인터, 다음 노드를 가리키는 포인터 변수를 갖습니다.

아중 링크드 리스트는 리스트의 첫 노드를 가리키는 head와 마지막 노드를 가리키는 tail 그리고 현재 리스트의 요소 수를 기록하는 size 변수를 갖습니다.

단일 링크드 리스트의 기본 구성에서 tail과 prev가 추가된 것 뿐입니다.

기본 연산

노드 삽입

appendprependinsertAt

append 연산은 리스트의 끝에 새 노드를 추가합니다.

이중 링크드 리스트는 단일 링크드 리스트와 다르게 테일 포인터를 사용하기 때문에 순회 연산이 사용되지 않습니다. 그래서 시간 복잡도는 \(O(1)\)입니다.

append 과정

초반 head와 tail이 NULL일 때 append 연산 수행 시 head와 tail이 유일하게 같은 노드를 가리키는 순간입니다.

classstd::list

class DoublyLinkedList {
    // ...

    //! @brief 리스트의 끝에 새 노드를 추가하는 메서드
    //! @param value 값
    void Append(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있는 경우
        if (m_Head == nullptr) {
            m_Head = newNode;           // 헤드 노드가 새 노드를 가리킨다
            m_Tail = newNode;           // 테일 노드가 새 노드를 가리킨다
            m_Size += 1;                // 크기 증가
            return;
        }

        // (3) 리스트에 노드가 있는 경우
        newNode->prev = m_Tail;         // 새 노드의 이전 노드를 테일 노드를 가리킨다
        m_Tail->next = newNode;         // 테일 노드의 다음 노드를 새 노드를 가리킨다
        m_Tail = newNode;               // 테일 노드를 새 노드로
        m_Size += 1;                    // 크기 증가
    }
};

1. 새 노드 생성

   새 노드를 생성합니다.

2. 리스트가 비어 있는 경우

   리스트가 비어 있는 경우 새 노드가 첫 노드이자 마지막 노드입니다. 그렇기 때문에 head와 tail에 새 노드를 할당합니다.

3. 리스트에 노드가 있는 경우

   리스트에 노드가 있는 경우, 새 노드의 이전 노드를 기존의 테일 노드를 가리키도록 합니다. 기존의 테일 노드는 더 이상 테일 노드가 안 되기 때문이죠.

   기존의 테일 노드의 다음 노드는 새 노드를 가리키고, 테일 노드를 새 노드를 가리키도록 합니다. 그리고 크기를 1 증가시킵니다.

#include <iostream>
#include <list>

int main(int argc, char* argv[]) {
    // 이중 링크드 리스트
    std::list<int> dll;

    // 리스트 끝에 데이터 추가
    dll.push_back(10);
    dll.push_back(20);
    dll.push_back(30);

    // 출력
    for (auto n : dll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

C++은 std::list라는 이중 링크드 리스트 컨테이너를 제공하고 있습니다.

push_back() 메서드를 통해 리스트 끝에 새 노드를 추가할 수 있습니다.

prepend 연산은 리스트의 처음에 새 노드를 추가합니다.

리스트의 길이, 순회 연산과는 상관없기 때문에 시간 복잡도는 \(O(1)\)입니다.

prepend 과정

classstd::list

class DoublyLinkedList {
    // ...

    //! @brief 리스트의 처음에 새 노드를 추가하는 메서드
    //! @param value 값
    void Prepend(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있는 경우
        if (m_Head == nullptr) {
            m_Head = newNode;           // 헤드 노드가 새 노드를 가리킨다
            m_Tail = newNode;           // 테일 노드가 새 노드를 가리킨다
            m_Size += 1;                // 크기 증가
            return;
        }

        // (3) 리스트에 노드가 있는 경우
        newNode->next = m_Head;         // 새 노드의 다음 노드를 헤드 노드로
        m_Head->prev = newNode;         // 헤드 노드의 이전 노드를 새 노드로
        m_Head = newNode;               // 헤드 노드를 새 노드로
        m_Size += 1;                    // 크기 증가
    }
};

1. 새 노드 생성

   새 노드를 생성합니다.

2. 리스트가 비어 있는 경우

   리스트가 비어 있는 경우 새 노드가 첫 노드이자 마지막 노드입니다. 그렇기 때문에 head와 tail에 새 노드를 할당합니다.

3. 리스트에 노드가 있는 경우

   리스트에 노드가 있는 경우, 새 노드의 다음 노드를 기존의 헤드 노드를 가리키도록 합니다. 기존의 헤드 노드는 더 이상 헤드 노드가 안 되기 때문이죠.

   기존의 헤드 노드의 이전 노드는 새 노드를 가리키고, 헤드 노드를 새 노드를 가리키도록 합니다. 그리고 크기를 1 증가시킵니다.

// ...

int main(int argc, char* argv[]) {
    // 이중 링크드 리스트
    std::list<int> dll;

    // 리스트 처음에에 데이터 추가
    dll.push_front(30);
    dll.push_front(20);
    dll.push_front(10);

    // 출력
    for (auto n : dll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

push_front() 메서드를 통해 리스트의 처음에 새 노드를 추가할 수 있습니다.

insertAt 연산은 리스트의 특정 위치에 새 노드를 추가하며, 사용자로부터 인덱스를 넘겨 받습니다.

이중 링크드 리스트는 양방향 탐색이 가능합니다. 단일 링크드 리스트 방식으로 수행할 경우 조금 비효율적입니다. 그래서 헤드 또는 테일에서 시작하여 끝까지 순회하는 것보다, index의 값을 절반으로 나누어 순회할 방향을 정하는 것이 그나마 성능 향상에 도움이 됩니다. 시간 복잡도는 \(O(n)\)입니다.

classstd::list

class DoublyLinkedList {
    // ...

    //! @brief 리스트의 특정 위치에 새 노드를 추가하는 메서드
    //! @param index 인덱스
    //! @param value 값
    void InsertAt(int index, int value) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            Prepend(value);
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == m_Size) {
            Append(value);
            return;
        }

        // (4) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (5) 반으로 나누어 진행 방향 결정, 삽입될 위치의 노드 취득
        Node* current = nullptr;
        if ((m_Size / 2) < index) { // 헤드에서 시작
            current = m_Head;
            for (auto i = 0; i < index; ++i) {
                current = current->next;
            }
        } else {                    // 테일에서 시작
            current = m_Tail;
            for (auto i = m_Size - 1; i >= index; --i) {
                current = current->next;
            }
        }

        // (6) 새 노드의 next를 현재 노드로 설정
        newNode->next = current;

        // (7) 새 노드의 prev를 현재 노드의 prev로 설정
        newNode->prev = current->prev;

        // (8) 현재 노드의 prev의 next를 새 노드로 설정
        current->prev->next = newNode;

        // (9) 현재 노드의 prev를 새 노드로 설정
        current->prev = newNode;

        // (10) 크기 증가
        m_Size += 1;
    }
};

1. 인덱스 범위 검사

   인덱스가 음수이거나 리스트의 수를 초과하면 삽입 연산을 수행하지 않도록 합니다.

   index >= size로 수행하지 않는 이유는 직전 노드(index -1)를 찾아야하기 때문에 그렇습니다.

2. 인덱스가 0이라면

   인덱스가 0이라면 리스트의 처음에 새 노드를 추가하겠다는 뜻입니다. prepend 연산을 수행하여 노드를 추가합니다.

3. 인덱스가 마지막이라면

   인덱스가 리스트의 크기와 같다면 마지막에 새 노드를 추가하겠다는 뜻입니다. append 연산을 수행하여 노드를 추가합니다.

4. 새 노드 생성

   새 노드를 생성합니다.

5. 반으로 나누어 진행 방향 결정, 삽입될 위치의 노드 취득

   인덱스가 리스트 크기의 절반보다 크면 테일에서, 작으면 헤드에서 시작하도록 합니다. 헤드나 테일에서 시작하여 순회하는 것보다 조금이나마 나은 성능을 보입니다.

   6번부터는 중간 삽입 처리를 수행합니다. 왜냐하면 위에서 리스트의 처음과 끝 처리를 하기 때문에, 6번까지 왔다는 건 중간에 새 노드가 삽입된다는 걸 의미합니다.

6. 새 노드의 next를 현재 노드로 설정

   새 노드의 next를 현재 노드로 설정합니다.

   새 노드가 삽입되기 전, 현재 노드와 현재 노드의 prev 그 사이에 추가되는 것이기 때문에 새 노드의 next를 현재 노드를 가리키도록 합니다.

7. 새 노드의 prev를 현재 노드의 prev로 설정

   새 노드의 prev를 현재 노드의 prev로 설정합니다.

   새 노드가 삽입되기 전, 현재 노드와 현재 노드의 prev 그 사이에 추가되는 것이기 때문에 새 노드의 prev를 현재 노드의 prev를 가리키도록 합니다.

8. 현재 노드의 prev의 next를 새 노드로 설정

   현재 노드의 prev의 next를 새 노드로 설정합니다.

   새 노드가 삽입되기 전, 현재 노드와 현재 노드의 prev 그 사이에 추가되는 것이기 때문에 이전 노드의 next를 새 노드를 가리키도록 합니다.

9. 현재 노드의 prev를 새 노드로 설정

   현재 노드의 prev를 새 노드로 설정합니다.

   새 노드가 삽입되기 전, 현재 노드와 현재 노드의 prev 그 사이에 추가되는 것이기 때문에 현재 노드의 prev를 새 노드를 가리키도록 합니다.

10. 크기 증가

    새 노드가 추가되었으니 크기를 1 증가시킵니다.

// ...

int main(int argc, char* argv[]) {
    // 이중 링크드 리스트
    std::list<int> dll;

    // 맨 끝 데이터 추가
    dll.push_back(10);
    dll.push_back(20);
    dll.push_back(40);

    // 중간 데이터 추가
    auto it = std::next(dll.begin(), 2);
    dll.insert(it, 30);

    // 출력
    for (auto n : dll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

std::list 컨테이너에선 insert() 메서드를 통해 중간에 새 노드를 추가할 수 있습니다. 첫 번째 매개변수로 추가될 위치를 받고, 두 번째 매개변수로 추가될 데이터를 넘겨 받습니다.

노드 제거

deleteBegindeleteEnddeleteAtclear

deleteBegin 연산은 리스트의 첫 노드를 제거합니다.

리스트의 길이, 순회와는 상관없기 때문에 시간 복잡도는 \(O(1)\)입니다.

classstd::list

class DoublyLinkedList {
    // ...

    //! @brief 리스트의 첫 노드를 제거하는 메서드
    void DeleteBegin() noexcept {
        // (1) 리스트가 비어 있다면 생략
        if (m_Head == nullptr) { return; }

        // (2) 제거할 헤드 노드 임시 보관
        auto* temp = m_Head;

        // (3) 리스트의 노드가 하나 뿐인 경우
        if (m_Head == m_Tail) {
            m_Head = nullptr;
            m_Tail = nullptr;
        } else {        // (4) 그외 경우
            m_Head = m_Head->next;
            m_Head->prev = nullptr;
        }

        // (5) 삭제
        delete temp;

        // (6) 크기 감소
        m_Size -= 1;
    }
};

1. 리스트가 비어 있다면 생략

   리스트가 비어 있다면 제거할 노드가 존재하지 않습니다.

2. 제거할 헤드 노드 임시 보관

   제거 대상인 헤드 노드를 임시 보관합니다.

3. 리스트의 노드가 하나뿐인 경우

   리스트의 노드가 하나 뿐인 경우 m_Head와 m_Tail을 nullptr로 변경합니다.

4. 그외 경우

   리스트의 노드가 두 개 이상인 경우 m_Head를 m_Head의 next 노드를 가리키도록 합니다. 그리고 prev는 nullptr을 할당합니다. m_Head의 prev는 없으니까요.

5. 삭제

   delete를 사용하여 노드를 제거합니다.

6. 크기 감소

   노드를 제거하였으니 크기를 1 감소시킵니다.

// ...

int main(int argc, char* argv[]) {
    // 이중 링크드 리스트
    std::list<int> dll;

    // 맨 끝 데이터 추가
    dll.push_back(10);
    dll.push_back(20);
    dll.push_back(30);

    // 맨 앞 데이터 제거
    dll.pop_front();

    // 출력
    for (auto n : dll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

std::list 컨테이너는 pop_front() 메서드를 호출하여 리스트의 맨 앞 노드를 제거할 수 있습니다.

deleteEnd 연산은 리스트의 마지막 노드를 제거합니다.

이중 링크드 리스트는 테일 포인터를 갖기 때문에 순회와 상관없이 바로 접근이 가능합니다. 시간 복잡도는 \(O(1)\)입니다.

classstd::list

class DoublyLinkedList {
    // ...

    //! @brief 리스트의 마지막 노드를 제거하는 메서드
    void DeleteEnd() noexcept {
        // (1) 리스트가 비어 있다면 생략
        if (m_Head == nullptr) { return; }

        // (2) 제거할 테일 노드 임시 보관
        auto* temp = m_Tail;

        // (3) 리스트의 노드가 하나 뿐인 경우
        if (m_Head == m_Tail) {
            m_Head = nullptr;
            m_Tail = nullptr;
        } else {        // (4) 그외 경우
            m_Tail = m_Tail->prev;
            m_Tail->next = nullptr;
        }

        // (5) 삭제
        delete temp;

        // (6) 크기 감소
        m_Size -= 1;
    }
};

1. 리스트가 비어 있다면 생략

   리스트가 비어 있다면 제거할 노드가 존재하지 않습니다.

2. 제거할 테일 노드 임시 보관

   제거 대상인 테일 노드를 임시 보관합니다.

3. 리스트의 노드가 하나뿐인 경우

   리스트의 노드가 하나 뿐인 경우 m_Head와 m_Tail을 nullptr로 변경합니다.

4. 그외 경우

   리스트의 노드가 두 개 이상인 경우 m_Tail을 m_Tail의 prev 노드를 가리키도록 합니다. 그리고 next는 nullptr을 할당합니다. m_Tail의 prev는 없으니까요.

5. 삭제

   delete를 사용하여 노드를 제거합니다.

6. 크기 감소

   노드를 제거하였으니 크기를 1 감소시킵니다.

// ...

int main(int argc, char* argv[]) {
    // 이중 링크드 리스트
    std::list<int> dll;

    // 맨 끝 데이터 추가
    dll.push_back(10);
    dll.push_back(20);
    dll.push_back(30);

    // 맨 뒤 데이터 제거
    dll.pop_back();

    // 출력
    for (auto n : dll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

std::list 컨테이너는 pop_back() 메서드를 호출하여 리스트의 맨 뒤 노드를 제거할 수 있습니다.

deleteAt 연산은 리스트의 특정 위치에 있는 노드를 제거하며, 사용자로부터 인덱스를 넘겨 받습니다.

이중 링크드 리스트는 양방향 탐색이 가능합니다. 단일 링크드 리스트 방식으로 수행할 경우 조금 비효율적입니다. 그래서 헤드 또는 테일에서 시작하여 끝까지 순회하는 것보다, index의 값을 절반으로 나누어 순회할 방향을 정하는 것이 그나마 성능 향상에 도움이 됩니다. 시간 복잡도는 \(O(n)\)입니다.

classstd::list

class DoublyLinkedList {
    // ...

    //! @brief 리스트의 특정 위치에 있는 노드를 제거하는 메서드
    //! @param index 인덱스
    void DeleteAt(int index) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            DeleteBegin();
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == (m_Size - 1)) {
            DeleteEnd();
            return;
        }

        // (4) 반으로 나누어 진행 방향 결정, 제거할 노드 취득
        Node* current = nullptr;
        if ((m_Size / 2) < index) {      // 헤드에서 시작
            current = m_Head;
            for (auto i = 0; i < index; ++i) {
                current = current->next;
            }
        } else {                            // 테일에서 시작
            current = m_Tail;
            for (auto i = m_Size - 1; i > index; --i) {
                current = current->prev;
            }
        }

        // (5) 연결 끊기
        current->prev->next = current->next; 
        current->next->prev = current->prev;

        // (6) 해제
        delete current;

        // (7) 크기 감소
        m_Size -= 1;
    }
};

1. 인덱스 범위 검사

   인덱스가 음수이거나 리스트의 길이를 초과하는 경우 생략합니다.

2. 인덱스가 0이라면

   인덱스의 값이 0이라면 첫 번째 노드를 제거함을 의미합니다. DeleteBegin() 함수를 호출합니다.

3. 인덱스가 마지막이라면

   인덱스의 값이 리스트 크기의 1을 뺀 값과 같다면 마지막 노드를 제거함을 의미합니다. DeleteEnd() 함수를 호출합니다.

4. 반으로 나누어 진행 방향 결정, 제거할 노드 취득

   리스트의 크기를 반으로 나누어 인덱스 값보다 작다면 헤드에서, 크다면 테일에서 시작하도록 진행 방향을 설정합니다.

   제거할 노드를 취득합니다.

5. 연결 끊기

   사이에 끼어있는 중간 노드를 제거하는 것이기 때문에 제거 대상의 노드를 가리키지 않도록 합니다.

6. 해제

   delete를 사용하여 제거 대상의 노드를 제거합니다.

7. 크기 감소

   노드가 제거되었으니 크기를 1 감소시킵니다.

// ...

int main(int argc, char* argv[]) {
    // 이중 링크드 리스트
    std::list<int> dll;

    // 맨 끝 데이터 추가
    dll.push_back(10);
    dll.push_back(20);
    dll.push_back(40);
    dll.push_back(30);

    // 중간 데이터 제거
    auto it = std::next(dll.begin(), 2);
    dll.erase(it);

    // 출력
    for (auto n : dll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

std::list 컨테이너는 erase() 메서드를 사용하여 특정 위치에 있는 노드를 제거할 수 있습니다.

clear 연산은 모든 노드를 순회하여 제거합니다.

모든 노드를 순회하기 때문에 시간 복잡도는 \(O(n)\)입니다.

classstd::list

class DoublyLinkedList {
    // ...

    //! @brief 모든 노드를 제거하는 함수
    void Clear() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 순회하며 제거
        auto* current = m_Head;
        while (current != nullptr) {
            auto* next = current->next;
            delete current;
            current = next;
        }
        m_Head = nullptr;
        m_Tail = nullptr;
        m_Size = 0;
    }
};

// ...

int main(int argc, char* argv[]) {
    // 이중 링크드 리스트
    std::list<int> dll;

    // 맨 끝 데이터 추가
    dll.push_back(10);
    dll.push_back(20);
    dll.push_back(30);

    // 모든 노드 제거
    dll.clear();

    return 0;
}

전체 코드

classstd::list

#include <iostream>

//! @brief 노드
class Node {
private:
    int data;               //!< 데이터
    Node* prev;             //!< 이전 노드를 가리키는 포인터
    Node* next;             //!< 다음 노드를 가리키는 포인터

public:
    friend class DoublyLinkedList;  // DoubluLinkedList에서 접근하기 위해 필요

    //! @brief 생성자
    //! @param value 값
    Node(int value) noexcept {
        this->data = value;
        this->prev = this->next = nullptr;
    }
};

//! @brief 이중 링크드 리스트
class DoublyLinkedList {
private:
    Node* m_Head;           //!< 헤드 노드
    Node* m_Tail;           //!< 테일 노드
    int m_Size;             //!< 크기 (리스트의 요소 수)

public:
    //! @brief 생성자
    DoublyLinkedList() noexcept {
        m_Head = m_Tail = nullptr;
        m_Size = 0;
    }

    //! @brief 소멸자
    ~DoublyLinkedList() noexcept {
        Clear();
    }

    //! @brief 리스트의 끝에 새 노드를 추가하는 메서드
    //! @param value 값
    void Append(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있는 경우
        if (m_Head == nullptr) {
            m_Head = newNode;           // 헤드 노드가 새 노드를 가리킨다
            m_Tail = newNode;           // 테일 노드가 새 노드를 가리킨다
            m_Size += 1;                // 크기 증가
            return;
        }

        // (3) 리스트에 노드가 있는 경우
        newNode->prev = m_Tail;         // 새 노드의 이전 노드를 테일 노드를 가리킨다
        m_Tail->next = newNode;         // 테일 노드의 다음 노드를 새 노드를 가리킨다
        m_Tail = newNode;               // 테일 노드를 새 노드로
        m_Size += 1;                    // 크기 증가
    }

    //! @brief 리스트의 처음에 새 노드를 추가하는 메서드
    //! @param value 값
    void Prepend(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있는 경우
        if (m_Head == nullptr) {
            m_Head = newNode;           // 헤드 노드가 새 노드를 가리킨다
            m_Tail = newNode;           // 테일 노드가 새 노드를 가리킨다
            m_Size += 1;                // 크기 증가
            return;
        }

        // (3) 리스트에 노드가 있는 경우
        newNode->next = m_Head;         // 새 노드의 다음 노드를 헤드 노드로
        m_Head->prev = newNode;         // 헤드 노드의 이전 노드를 새 노드로
        m_Head = newNode;               // 헤드 노드를 새 노드로
        m_Size += 1;                    // 크기 증가
    }

    //! @brief 리스트의 특정 위치에 새 노드를 추가하는 메서드
    //! @param index 인덱스
    //! @param value 값
    void InsertAt(int index, int value) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            Prepend(value);
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == m_Size) {
            Append(value);
            return;
        }

        // (4) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (5) 반으로 나누어 진행 방향 결정, 삽입될 위치의 노드 취득
        Node* current = nullptr;
        if ((m_Size / 2) < index) { // 헤드에서 시작
            current = m_Head;
            for (auto i = 0; i < index; ++i) {
                current = current->next;
            }
        } else {                    // 테일에서 시작
            current = m_Tail;
            for (auto i = m_Size - 1; i >= index; --i) {
                current = current->next;
            }
        }

        // (6) 새 노드의 next를 현재 노드로 설정
        newNode->next = current;

        // (7) 새 노드의 prev를 현재 노드의 prev로 설정
        newNode->prev = current->prev;

        // (8) 현재 노드의 prev의 next를 새 노드로 설정
        current->prev->next = newNode;

        // (9) 현재 노드의 prev를 새 노드로 설정
        current->prev = newNode;

        // (10) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트의 첫 노드를 제거하는 메서드
    void DeleteBegin() noexcept {
        // (1) 리스트가 비어 있다면 생략
        if (m_Head == nullptr) { return; }

        // (2) 제거할 헤드 노드 임시 보관
        auto* temp = m_Head;

        // (3) 리스트의 노드가 하나 뿐인 경우
        if (m_Head == m_Tail) {
            m_Head = nullptr;
            m_Tail = nullptr;
        } else {        // (4) 그외 경우
            m_Head = m_Head->next;
            m_Head->prev = nullptr;
        }

        // (5) 삭제
        delete temp;

        // (6) 크기 감소
        m_Size -= 1;
    }

    //! @brief 리스트의 마지막 노드를 제거하는 메서드
    void DeleteEnd() noexcept {
        // (1) 리스트가 비어 있다면 생략
        if (m_Head == nullptr) { return; }

        // (2) 제거할 테일 노드 임시 보관
        auto* temp = m_Tail;

        // (3) 리스트의 노드가 하나 뿐인 경우
        if (m_Head == m_Tail) {
            m_Head = nullptr;
            m_Tail = nullptr;
        } else {        // (4) 그외 경우
            m_Tail = m_Tail->prev;
            m_Tail->next = nullptr;
        }

        // (5) 삭제
        delete temp;

        // (6) 크기 감소
        m_Size -= 1;
    }

    //! @brief 리스트의 특정 위치에 있는 노드를 제거하는 메서드
    //! @param index 인덱스
    void DeleteAt(int index) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            DeleteBegin();
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == (m_Size - 1)) {
            DeleteEnd();
            return;
        }

        // (4) 반으로 나누어 진행 방향 결정, 제거할 노드 취득
        Node* current = nullptr;
        if ((m_Size / 2) < index) {      // 헤드에서 시작
            current = m_Head;
            for (auto i = 0; i < index; ++i) {
                current = current->next;
            }
        } else {                            // 테일에서 시작
            current = m_Tail;
            for (auto i = m_Size - 1; i > index; --i) {
                current = current->prev;
            }
        }

        // (5) 연결 끊기
        current->prev->next = current->next; 
        current->next->prev = current->prev;

        // (6) 해제
        delete current;

        // (7) 크기 감소
        m_Size -= 1;
    }

    //! @brief 모든 노드를 제거하는 함수
    void Clear() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 순회하며 제거
        auto* current = m_Head;
        while (current != nullptr) {
            auto* next = current->next;
            delete current;
            current = next;
        }
        m_Head = nullptr;
        m_Tail = nullptr;
        m_Size = 0;
    }

    void Print() noexcept {
        auto* current = m_Head;
        while (current != nullptr) {
            std::cout << current->data << " ";
        }
        std::cout << "\n";
    }
};

int main(int argc, char* argv[]) {
    // DoublyLinkedList
    DoublyLinkedList dll;

    // Append
    dll.Append(10);
    dll.Append(20);
    dll.Append(40);

    // Insert At
    dll.InsertAt(2, 30);

    // Print
    dll.Print();

    return 0;
}

#include <iostream>
#include <list>

int main(int argc, char* argv[]) {
    // DoublyLinkedList
    std::list<int> dll;

    // Append
    dll.push_back(10);
    dll.push_back(20);
    dll.push_back(40);

    // Insert At
    auto it = std::next(dll.begin(), 2);
    dll.insert(it, 30);

    // Print
    for (auto n : dll) {
        std::cout << n << " ";
    }
    std::cout << "\n";

    return 0;
}

10 20 30 40

원형 링크드 리스트

원형 링크드 리스트^{Circular Linked List}는 일반적인 링크드 리스트의 변형으로, 마지막 노드가 첫 번째 노드와 연결되거나 첫 번째 노드가 마지막 노드와 연결되어 순환 구조를 갖는 자료구조입니다. 끝에서 시작으로, 시작에서 끝으로 가기 때문에 '끝'이라는 개념이 없다고 보시면 됩니다.

원형 링크드 리스트는 크게 단일과 이중으로 구분할 수 있습니다.

단일 원형 링크드 리스트는 마지막 노드의 next가 head를 가리키고, 이중 원형 링크드 리스트는 tail->next가 head를 가리키고 head->prev가 tail을 가리킵니다.

기본 구성

단일이중

//! @brief 노드
class Node {
private:
    int data;               //!< 데이터
    Node* next;             //!< 다음 노드를 가리키는 포인터

public:
    friend class SinglyCircularLinkedList;      // SinglyCircularLinkedList에서 접근하기 위해 필요

    //! @brief 생성자
    Node(int value) noexcept {
        this->data = value;
        this->next = nullptr;
    }
};

//! @brief 단일 원형 링크드 리스트
class SinglyCircularLinkedList {
private:
    Node* m_Head;           //!< 헤드 노드
    int m_Size;             //!< 리스트의 크기

public:
    //! @brief 생성자
    SinglyCircularLinkedList() noexcept {
        m_Head = nullptr;
        m_Size = 0;
    }

    //! @brief 소멸자
    ~SinglyCircularLinkedList() noexcept {
        Clear();
    }
};

단일 원형 링크드 리스트의 기본 구성입니다. 기본 구성은 단일 링크드 리스트와 같습니다.

//! @brief 노드
class Node {
private:
    int data;               //!< 데이터
    Node* prev;             //!< 이전 노드를 가리키는 포인터
    Node* next;             //!< 다음 노드를 가리키는 포인터

public:
    friend class DoublyCircularLinkedList;  // DoublyCircularLinkedList 접근하기 위해 필요

    //! @brief 생성자
    //! @param value 값
    Node(int value) noexcept {
        this->data = value;
        this->prev = this->next = nullptr;
    }
};

//! @brief 이중 원형 링크드 리스트
class DoublyCircularLinkedList {
private:
    Node* m_Head;           //!< 헤드 노드
    int m_Size;             //!< 크기 (리스트의 요소 수)

public:
    //! @brief 생성자
    DoublyCircularLinkedList() noexcept {
        m_Head = nullptr;
        m_Size = 0;
    }

    //! @brief 소멸자
    ~DoublyCircularLinkedList() noexcept {
        Clear();
    }
};

이중 원형 링크드 리스트의 기본 구성입니다. 이중 링크드 리스트의 구성과 같지만, tail 노드를 사용하지 않습니다. 왜냐하면 head->prev가 곧 tail이고, tail->next가 곧 head이기 때문에 그렇습니다.

기본 연산

노드 삽입

단일이중

appendprependinsertAt

append 연산은 리스트의 맨 끝에 새 노드를 추가합니다.

단일 링크드 리스트 기반은 리스트의 끝까지 가기 위해 순회 과정을 거치기 때문에 시간 복잡도는 \(O(n)\)입니다.

class SinglyCircularLinkedList {
    // ...

    //! @brief 리스트 끝에 새 노드를 추가하는 메서드
    //! @param value 값
    void Append(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있다면
        if (m_Head == nullptr) {
            m_Head = newNode;
            m_Head->next = m_Head;              // 자기 자신을 가리킨다
            m_Size += 1;
            return;
        }

        // (3) 리스트에 노드가 있다면
        auto* current = m_Head;
        while (current->next != m_Head) {       // 마지막 노드로 이동
            current = current->next;
        }
        current->next = newNode;                // 새 노드 가리키기

        // (4) 원형 연결
        newNode->next = m_Head; 

        // (5) 크기 증가
        m_Size += 1;
    }
};

prepend 연산은 리스트의 처음에 새 노드를 추가합니다.

리스트의 길이, 순회와는 상관없기 때문에 시간 복잡도는 \(O(1)\)입니다.

class SinglyCircularLinkedList {
    // ...

    //! @brief 리스트 처음에 새 노드를 추가하는 함수
    //! @param value 값
    void Prepend(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있다면
        if (m_Head == nullptr) {
            m_Head = newNode;
            m_Head->next = m_Head;          // 자기 자신을 가리킨다
            m_Size += 1;
            return;
        }

        // (3) 리스트에 노드가 있다면
        auto* current = m_Head;
        while (current->next != m_Head) {   // 마지막 노드로 이동
            current = current->next;
        }

        // (4) 새 노드의 next가 기존 헤드를 가리킨다
        newNode->next = m_Head;

        // (5) 마지막 노드가 새 노드를 가리킨다
        current->next = newNode;

        // (6) 헤드 갱신
        m_Head = newNode;

        // (7) 크기 증가
        m_Size += 1;
    }
};

insertAt 연산은 리스트의 특정 위치에 새 노드를 추가합니다. 사용자로부터 인덱스를 넘겨 받습니다.

단일 링크드 리스트를 기반으로 하기 때문에 삽입하려는 위치의 직전 노드를 찾아야 합니다. 순회 과정을 거치기 때문에 인덱스가 0이 아니라면 시간 복잡도는 \(O(n)\)입니다.

class SinglyCircularLinkedList {
    // ...

    //! @brief 리스트의 특정 위치에 새 노드를 삽입하는 메서드
    //! @param index 인덱스
    //! @param value 값
    void InsertAt(int index, int value) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            Prepend(value);
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == m_Size) {
            Append(value);
            return;
        }

        // (4) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (5) 직전 노드 취득
        auto* current = m_Head;
        for (auto i = 0; i < index - 1; ++i) {
            current = current->next;
        }

        // (6) 새 노드가 다음 노드 가리키기
        newNode->next = current->next;

        // (7) 이전 노드가 새 노드 가리키기
        current->next = newNode;

        // (8) 크기 증가
        m_Size += 1;
    }
};

appendprependinsertAt

append 연산은 리스트의 맨 끝에 새 노드를 추가합니다.

이중 링크드 리스트 기반은 리스트의 끝을 prev로 바로 접근할 수 있습니다. 시간 복잡도는 \(O(1)\)입니다.

class DoublyCircularLinkedList {
    // ...

    //! @brief 리스트의 끝에 새 노드를 추가하는 메서드
    //! @param value 값
    void Append(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있다면
        if (m_Head == nullptr) {
            m_Head = newNode;

            // 자기 자신을 가리킨다
            newNode->prev = newNode;
            newNode->next = newNode;

            m_Size += 1;
            return;
        }

        // (3) 리스트에 노드가 있다면
        Node* last = m_Head->prev;      // 마지막 노드
        last->next = newNode;           // 새 노드를 가리킨다
        newNode->prev = last;           // 새 노드의 이전 노드는 마지막 노드를 가리킨다
        newNode->next = m_Head;         // 새 노드의 다음 노드는 헤드 노드를 가리킨다
        m_Head->prev = newNode;         // 헤드 노드의 이전 노드는 새 노드를 가리킨다

        // (4) 크기 증가
        m_Size += 1;
    }
};

prepend 연산은 리스트의 처음에 새 노드를 추가합니다.

리스트의 길이, 순회와는 상관없기 때문에 시간 복잡도는 \(O(1)\)입니다.

```cpp title="dcll_prepend.cpp" linenums="1" class DoublyCircularLinkedList { // ...

//! @brief 리스트의 처음에 새 노드를 추가하는 메서드
//! @param value 값
void Prepend(int value) noexcept {
    // (1) 새 노드 생성
    auto* newNode = new Node(value);
    if (!newNode) { return; }

    // (2) 리스트가 비어 있다면
    if (m_Head == nullptr) {
        m_Head = newNode;

        // 자기 자신을 가리킨다
        newNode->prev = newNode;
        newNode->next = newNode;

        m_Size +=- 1;
        return;
    }

    // (3) 리스트에 노드가 있다면
    auto* last = m_Head->prev;      // 마지막 노드
    newNode->next = m_Head;         // 새 노드의 다음 노드가 헤드 노드를 가리킨다
    newNode->prev = last;           // 새 노드의 이전 노드가 마지막 노드를 가리킨다
    m_Head->prev = newNode;         // 헤드 노드의 이전 노드가 새 노드를 가리킨다
    last->next = newNode;           // 마지막 노드의 다음 노드가 새 노드를 가리킨다
    m_Head = newNode;               // 헤드 갱신

    // (4) 크기 증가
    m_Size += 1;
}

}; ```

insertAt 연산은 리스트의 특정 위치에 새 노드를 추가합니다. 사용자로부터 인덱스를 넘겨 받습니다.

이중 링크드 리스트는 양방향 탐색이 가능합니다. 단일 링크드 리스트 방식으로 수행할 경우 조금 비효율적입니다. 그래서 헤드 또는 테일에서 시작하여 끝까지 순회하는 것보다, index의 값을 절반으로 나누어 순회할 방향을 정하는 것이 그나마 성능 향상에 도움이 됩니다. 시간 복잡도는 \(O(n)\)입니다.

class DoublyCircularLinkedList {
    // ...

    //! @brief 리스트의 특정 위치에 새 노드를 추가하는 메서드
    //! @param index 인덱스
    //! @param value 값
    void InsertAt(int index, int value) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            Prepend(value);
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == m_Size) { 
            Append(value);
            return;
        }

        // (4) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (5) 반으로 나누어 진행 방향 결정, 삽입 위치의 노드로 이동
        Node* current = nullptr;
        if ((m_Size / 2) < index) {
            current = m_Head;                               // 헤드에서 시작
            for (auto i = 0; i < index; ++i) {
                current = current->next;
            }
        } else {
            current = m_Head->prev;                         // 테일에서 시작
            for (auto i = m_Size - 1; i > index; --i) {
                current = current->next;
            }
        }

        // (6) 노드 추가
        auto* prev = current->prev;
        prev->next = newNode;
        newNode->prev = prev;
        newNode->next = current;
        current->prev = newNode;

        // (7) 크기 증가
        m_Size += 1;
    }
};

노드 제거

단일이중

deleteBegindeleteEnddeleteAtclear

deleteBegin 연산은 리스트의 첫 노드를 제거합니다.

테일 노드를 찾는 순회 과정이 있기 때문에 시간 복잡도는 \(O(n)\)입니다.

class SinglyCircularLinkedList {
    // ...

    //! @brief 리스트의 첫 노드를 제거하는 메서드
    void DeleteBegin() noexcept {
        // (1) 리스트가 비어 있는 지 확인
        if (m_Head == nullptr) { return; }

        // (2) 제거할 노드 임시 보관
        auto* temp = m_Head;

        // (3) 노드가 하나라면
        if (m_Size == 1) {
            delete temp;
            m_Head = nullptr;
            m_Size = 0;
            return;
        }

        // (4) 테일 노드 찾기
        auto* tail = m_Head;
        while (tail->next != m_Head) {
            tail = tail->next;
        }

        // (5) 헤드 노드를 헤드 노드의 다음 노드를 가리킨다
        m_Head = m_Head->next;

        // (6) 테일 노드의 다음 노드를 헤드 노드를 가리킨다
        tail->next = m_Head;

        // (7) 제거
        delete temp;

        // (8) 크기 감소
        m_Size -= 1;
    }
};

deleteEnd 연산은 리스트의 마지막 노드를 제거합니다.

리스트의 마지막 노드를 찾기 위해 순회 연산을 거치기 때문에 시간 복잡도는 \(O(n)\)입니다.

class SinglyCircularLinkedList {
    // ...

    //! @brief 리스트의 마지막 노드를 제거하는 메서드
    void DeleteEnd() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 리스트에 노드가 하나 뿐인 지 확인
        if (m_Head->next == nullptr) {
            delete m_Head;
            m_Head = nullptr;
            m_Size = 0;
            return;
        }

        // (3) 마지막 노드의 이전 노드까지 이동
        auto* prev = m_Head;
        while (prev->next->next != m_Head) {
            prev = prev->next;
        }

        // (4) 제거 대상
        auto* target = prev->next;

        // (5) 제거 대상의 다음 노드는 헤드 노드를 가리킨다
        prev->next = m_Head;

        // (6) 제거
        delete target;

        // (7) 크기 감소
        m_Size -= 1;
    }
};

deleteAt 연산은 리스트의 특정 위치에 있는 노드를 제거하며, 사용자로부터 인덱스를 넘겨 받습니다.

단일 원형 링크드 리스트는 단방향이기 때문에 제거 대상의 노드 위치를 순회하여 찾아야합니다. 시간 복잡도는 \(O(n)\)입니다.

class SinglyCircularLinkedList {
    // ...

    //! @brief 리스트의 특정 위치에 있는 노드를 제거하는 메서드
    //! @param index 인덱스
    void DeleteAt(int index) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index >= m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            DeleteBegin();
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == m_Size - 1) {
            DeleteEnd();
            return;
        }

        // (4) 제거 대상의 직전 노드 찾기
        auto* prev = m_Head;
        for (auto i = 0; i < index - 1; ++i) {
            prev = prev->next;
        }

        // (6) 제거 대상
        auto* target = prev->next;

        // (7) 직전 노드의 다음 노드를 제거 대상의 다음 노드 가리키기
        prev->next = target->next;

        // (8) 제거
        delete target;

        // (9) 크기 감소
        m_Size -= 1;
    }
};

clear 연산은 모든 노드를 제거합니다.

모든 노드를 순회하며 제거하기 때문에 시간 복잡도는 \(O(n)\)입니다.

class SinglyCircularLinkedList {
    // ...

    //! @brief 모든 노드를 제거하는 메서드
    void Clear() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 순회 및 제거
        auto* current = m_Head;
        for (auto i = 0; i < m_Size; ++i) {
            auto* target = current;
            current = current->next;
            delete target;
        }
        m_Head = nullptr;
        m_Size = 0;
    }
};

deleteBegindeleteEnddeleteAtclear

deleteBegin 연산은 리스트의 첫 노드를 제거합니다.

리스트의 길이, 순회와는 상관없기 때문에 시간 복잡도는 \(O(1)\)입니다.

class DoublyCircularLinkedList {
    // ...

    //! @brief 리스트의 첫 노드를 제거하는 메서드
    void DeleteBegin() noexcept {
        // (1) 리스트가 비어 있는 지 확인
        if (m_Head == nullptr) { return; }

        // (2) 제거 대상 노드 임시 보관
        auto* target = m_Head;

        // (3) 리스트의 노드가 하나만 있다면
        if (m_Size == 1) {
            delete target;
            m_Head = nullptr;
            m_Size -= 1;
            return;
        }

        // (4) 리스트의 노드가 여러 개 있다면
        auto* tail = m_Head->prev;          // 테일 노드
        m_Head = m_Head->next;              // 헤드 노드를 헤드 노드의 다음 노드를 가리킨다
        m_Head->prev = tail;                // 헤드 노드의 이전 노드가 테일 노드를 가리킨다
        tail->next = m_Head;                // 테일 노드의 다음 노드가 헤드 노드를 가리킨다

        // (5) 제거
        delete target;

        // (6) 크기 감소
        m_Size -= 1;
    }
};

deleteEnd 연산은 리스트의 마지막 노드를 제거합니다.

이중 링크드 리스트는 양방향 접근이 가능하기 때문에 바로 마지막 노드의 접근이 가능합니다. 시간 복잡도는 \(O(1)\)입니다.

class DoublyCircularLinkedList {
    // ...

    void DeleteEnd() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (3) 리스트에 노드가 하나 뿐이라면
        if (m_Size == 1) {
            delete m_Head;
            m_Head = nullptr;
            m_Size = 0;
            return;
        }

        // (3) 제거 대상 노드
        auto* target = m_Head->prev;        // 제거 대상
        auto* newTail = target->prev;       // 새 테일이 되는 대상

        // (5) 새 테일의 다음 노드를 헤드 노드로 가리킨다
        newTail->next = m_Head;

        // (6) 헤드 노드의 이전 노드를 새 테일로 가리킨다
        m_Head->prev = newTail;

        // (7) 제거
        delete target;

        // (8) 크기 감소
        m_Size -= 1;
    }
};

deleteAt 연산은 리스트의 특정 위치에 있는 노드를 제거하며, 사용자로부터 인덱스를 넘겨 받습니다.

이중 링크드 리스트는 양방향 탐색이 가능합니다. 단일 링크드 리스트 방식으로 수행할 경우 조금 비효율적입니다. 그래서 헤드 또는 테일에서 시작하여 끝까지 순회하는 것보다, index의 값을 절반으로 나누어 순회할 방향을 정하는 것이 그나마 성능 향상에 도움이 됩니다. 시간 복잡도는 \(O(n)\) 입니다.

class DoublyCircularLinkedList {
    // ...

    //! @brief 리스트의 특정 위치에 있는 노드를 제거하는 메서드
    //! @param index 인덱스
    void DeleteAt(int index) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index >= m_Size) { return; }

        // (3) 인덱스가 0이라면
        if (index == 0) {
            DeleteBegin();
            return;
        }

        // (4) 인덱스가 끝이라면
        if (index == m_Size - 1) {
            DeleteEnd();
            return;
        }

        // (5) 반으로 나누어 진행 방향 결정, 제거할 노드 취득
        Node* current = nullptr;
        if ((m_Size / 2) < index) {         // 헤드에서 시작
            current = m_Head;
            for (auto i = 0; i < index; ++i) {
                current = current->next;
            }
        } else {                                // 테일에서 시작
            current = m_Head->prev;
            for (auto i = m_Size - 1; i > index; --i) {
                current = current->prev;
            }
        }

        // (6) 연결 끊기
        current->prev->next = current->next;
        current->next->prev = current->prev;

        // (7) 제거
        delete current;

        // (8) 크기 감소
        m_Size -= 1;
    }
};

clear 연산은 모든 노드를 제거합니다.

모든 노드를 순회하며 제거하기 때문에 시간 복잡도는 \(O(n)\)입니다.

class DoublyCircularLinkedList {
    // ...

    //! @brief 모든 노드를 제거하는 메서드
    void Clear() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 순회 및 제거
        auto* current = m_Head;
        for (auto i = 0; i < m_Size; ++i) {
            auto* target = current;
            delete target;
            current = current->next;
        }
    }
};

전체 코드

단일이중

#include <iostream>

//! @brief 노드
class Node {
private:
    int data;               //!< 데이터
    Node* next;             //!< 다음 노드를 가리키는 포인터

public:
    friend class SinglyCircularLinkedList;      // SinglyCircularLinkedList에서 접근하기 위해 필요

    //! @brief 생성자
    Node(int value) noexcept {
        this->data = value;
        this->next = nullptr;
    }
};

//! @brief 단일 원형 링크드 리스트
class SinglyCircularLinkedList {
private:
    Node* m_Head;           //!< 헤드 노드
    int m_Size;             //!< 리스트의 크기

public:
    //! @brief 생성자
    SinglyCircularLinkedList() noexcept {
        m_Head = nullptr;
        m_Size = 0;
    }

    //! @brief 소멸자
    ~SinglyCircularLinkedList() noexcept {
        Clear();
    }

    //! @brief 리스트 끝에 새 노드를 추가하는 메서드
    //! @param value 값
    void Append(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있다면
        if (m_Head == nullptr) {
            m_Head = newNode;
            m_Head->next = m_Head;              // 자기 자신을 가리킨다
            m_Size += 1;
            return;
        }

        // (3) 리스트에 노드가 있다면
        auto* current = m_Head;
        while (current->next != m_Head) {       // 마지막 노드로 이동
            current = current->next;
        }
        current->next = newNode;                // 새 노드 가리키기

        // (4) 원형 연결
        newNode->next = m_Head; 

        // (5) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트 처음에 새 노드를 추가하는 함수
    //! @param value 값
    void Prepend(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있다면
        if (m_Head == nullptr) {
            m_Head = newNode;
            m_Head->next = m_Head;          // 자기 자신을 가리킨다
            m_Size += 1;
            return;
        }

        // (3) 리스트에 노드가 있다면
        auto* current = m_Head;
        while (current->next != m_Head) {   // 마지막 노드로 이동
            current = current->next;
        }

        // (4) 새 노드의 next가 기존 헤드를 가리킨다
        newNode->next = m_Head;

        // (5) 마지막 노드가 새 노드를 가리킨다
        current->next = newNode;

        // (6) 헤드 갱신
        m_Head = newNode;

        // (7) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트의 특정 위치에 새 노드를 삽입하는 메서드
    //! @param index 인덱스
    //! @param value 값
    void InsertAt(int index, int value) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            Prepend(value);
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == m_Size) {
            Append(value);
            return;
        }

        // (4) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (5) 직전 노드 취득
        auto* current = m_Head;
        for (auto i = 0; i < index - 1; ++i) {
            current = current->next;
        }

        // (6) 새 노드가 다음 노드 가리키기
        newNode->next = current->next;

        // (7) 이전 노드가 새 노드 가리키기
        current->next = newNode;

        // (8) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트의 첫 노드를 제거하는 메서드
    void DeleteBegin() noexcept {
        // (1) 리스트가 비어 있는 지 확인
        if (m_Head == nullptr) { return; }

        // (2) 제거할 노드 임시 보관
        auto* temp = m_Head;

        // (3) 노드가 하나라면
        if (m_Size == 1) {
            delete temp;
            m_Head = nullptr;
            m_Size = 0;
            return;
        }

        // (4) 테일 노드 찾기
        auto* tail = m_Head;
        while (tail->next != m_Head) {
            tail = tail->next;
        }

        // (5) 헤드 노드를 헤드 노드의 다음 노드를 가리킨다
        m_Head = m_Head->next;

        // (6) 테일 노드의 다음 노드를 헤드 노드를 가리킨다
        tail->next = m_Head;

        // (7) 제거
        delete temp;

        // (8) 크기 감소
        m_Size -= 1;
    }

    //! @brief 리스트의 마지막 노드를 제거하는 메서드
    void DeleteEnd() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 리스트에 노드가 하나 뿐인 지 확인
        if (m_Head->next == nullptr) {
            delete m_Head;
            m_Head = nullptr;
            m_Size = 0;
            return;
        }

        // (3) 마지막 노드의 이전 노드까지 이동
        auto* prev = m_Head;
        while (prev->next->next != m_Head) {
            prev = prev->next;
        }

        // (4) 제거 대상
        auto* target = prev->next;

        // (5) 제거 대상의 다음 노드는 헤드 노드를 가리킨다
        prev->next = m_Head;

        // (6) 제거
        delete target;

        // (7) 크기 감소
        m_Size -= 1;
    }

    //! @brief 리스트의 특정 위치에 있는 노드를 제거하는 메서드
    //! @param index 인덱스
    void DeleteAt(int index) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index >= m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            DeleteBegin();
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == m_Size - 1) {
            DeleteEnd();
            return;
        }

        // (4) 제거 대상의 직전 노드 찾기
        auto* prev = m_Head;
        for (auto i = 0; i < index - 1; ++i) {
            prev = prev->next;
        }

        // (6) 제거 대상
        auto* target = prev->next;

        // (7) 직전 노드의 다음 노드를 제거 대상의 다음 노드 가리키기
        prev->next = target->next;

        // (8) 제거
        delete target;

        // (9) 크기 감소
        m_Size -= 1;
    }

    //! @brief 모든 노드를 제거하는 메서드
    void Clear() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 순회 및 제거
        auto* current = m_Head;
        for (auto i = 0; i < m_Size; ++i) {
            auto* target = current;
            current = current->next;
            delete target;
        }
        m_Head = nullptr;
        m_Size = 0;
    }

    void Print() noexcept {
        if (m_Head == nullptr) { return; }

        auto* current = m_Head;
        for (auto i = 0; i < m_Size; ++i) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << "\n";
    }
};

int main(int argc, char* argv[]) {
    // 단일 원형 링크드 리스트
    SinglyCircularLinkedList scll;

    // 맨 뒤 데이터 추가
    scll.Append(10);
    scll.Append(20);
    scll.Append(40);

    // 중간 데이터 추가
    scll.InsertAt(2, 30);

    // 출력
    scll.Print();

    return 0;
}

#include <iostream>

//! @brief 노드
class Node {
private:
    int data;               //!< 데이터
    Node* prev;             //!< 이전 노드를 가리키는 포인터
    Node* next;             //!< 다음 노드를 가리키는 포인터

public:
    friend class DoublyCircularLinkedList;  // DoublyCircularLinkedList 접근하기 위해 필요

    //! @brief 생성자
    //! @param value 값
    Node(int value) noexcept {
        this->data = value;
        this->prev = this->next = nullptr;
    }
};

//! @brief 이중 원형 링크드 리스트
class DoublyCircularLinkedList {
private:
    Node* m_Head;           //!< 헤드 노드
    int m_Size;             //!< 크기 (리스트의 요소 수)

public:
    //! @brief 생성자
    DoublyCircularLinkedList() noexcept {
        m_Head = nullptr;
        m_Size = 0;
    }

    //! @brief 소멸자
    ~DoublyCircularLinkedList() noexcept {
        Clear();
    }

    //! @brief 리스트의 끝에 새 노드를 추가하는 메서드
    //! @param value 값
    void Append(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있다면
        if (m_Head == nullptr) {
            m_Head = newNode;

            // 자기 자신을 가리킨다
            newNode->prev = newNode;
            newNode->next = newNode;

            m_Size += 1;
            return;
        }

        // (3) 리스트에 노드가 있다면
        Node* last = m_Head->prev;      // 마지막 노드
        last->next = newNode;           // 새 노드를 가리킨다
        newNode->prev = last;           // 새 노드의 이전 노드는 마지막 노드를 가리킨다
        newNode->next = m_Head;         // 새 노드의 다음 노드는 헤드 노드를 가리킨다
        m_Head->prev = newNode;         // 헤드 노드의 이전 노드는 새 노드를 가리킨다

        // (4) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트의 처음에 새 노드를 추가하는 메서드
    //! @param value 값
    void Prepend(int value) noexcept {
        // (1) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (2) 리스트가 비어 있다면
        if (m_Head == nullptr) {
            m_Head = newNode;

            // 자기 자신을 가리킨다
            newNode->prev = newNode;
            newNode->next = newNode;

            m_Size +=- 1;
            return;
        }

        // (3) 리스트에 노드가 있다면
        auto* last = m_Head->prev;      // 마지막 노드
        newNode->next = m_Head;         // 새 노드의 다음 노드가 헤드 노드를 가리킨다
        newNode->prev = last;           // 새 노드의 이전 노드가 마지막 노드를 가리킨다
        m_Head->prev = newNode;         // 헤드 노드의 이전 노드가 새 노드를 가리킨다
        last->next = newNode;           // 마지막 노드의 다음 노드가 새 노드를 가리킨다
        m_Head = newNode;               // 헤드 갱신

        // (4) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트의 특정 위치에 새 노드를 추가하는 메서드
    //! @param index 인덱스
    //! @param value 값
    void InsertAt(int index, int value) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index > m_Size) { return; }

        // (2) 인덱스가 0이라면
        if (index == 0) {
            Prepend(value);
            return;
        }

        // (3) 인덱스가 마지막이라면
        if (index == m_Size) { 
            Append(value);
            return;
        }

        // (4) 새 노드 생성
        auto* newNode = new Node(value);
        if (!newNode) { return; }

        // (5) 반으로 나누어 진행 방향 결정, 삽입 위치의 노드로 이동
        Node* current = nullptr;
        if ((m_Size / 2) < index) {
            current = m_Head;                               // 헤드에서 시작
            for (auto i = 0; i < index; ++i) {
                current = current->next;
            }
        } else {
            current = m_Head->prev;                         // 테일에서 시작
            for (auto i = m_Size - 1; i > index; --i) {
                current = current->next;
            }
        }

        // (6) 노드 추가
        auto* prev = current->prev;
        prev->next = newNode;
        newNode->prev = prev;
        newNode->next = current;
        current->prev = newNode;

        // (7) 크기 증가
        m_Size += 1;
    }

    //! @brief 리스트의 첫 노드를 제거하는 메서드
    void DeleteBegin() noexcept {
        // (1) 리스트가 비어 있는 지 확인
        if (m_Head == nullptr) { return; }

        // (2) 제거 대상 노드 임시 보관
        auto* target = m_Head;

        // (3) 리스트의 노드가 하나만 있다면
        if (m_Size == 1) {
            delete target;
            m_Head = nullptr;
            m_Size -= 1;
            return;
        }

        // (4) 리스트의 노드가 여러 개 있다면
        auto* tail = m_Head->prev;          // 테일 노드
        m_Head = m_Head->next;              // 헤드 노드를 헤드 노드의 다음 노드를 가리킨다
        m_Head->prev = tail;                // 헤드 노드의 이전 노드가 테일 노드를 가리킨다
        tail->next = m_Head;                // 테일 노드의 다음 노드가 헤드 노드를 가리킨다

        // (5) 제거
        delete target;

        // (6) 크기 감소
        m_Size -= 1;
    }

    //! @brief 리스트의 마지막 노드를 제거하는 메서드
    void DeleteEnd() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (3) 리스트에 노드가 하나 뿐이라면
        if (m_Size == 1) {
            delete m_Head;
            m_Head = nullptr;
            m_Size = 0;
            return;
        }

        // (3) 제거 대상 노드
        auto* target = m_Head->prev;        // 제거 대상
        auto* newTail = target->prev;       // 새 테일이 되는 대상

        // (5) 새 테일의 다음 노드를 헤드 노드로 가리킨다
        newTail->next = m_Head;

        // (6) 헤드 노드의 이전 노드를 새 테일로 가리킨다
        m_Head->prev = newTail;

        // (7) 제거
        delete target;

        // (8) 크기 감소
        m_Size -= 1;
    }

    //! @brief 리스트의 특정 위치에 있는 노드를 제거하는 메서드
    //! @param index 인덱스
    void DeleteAt(int index) noexcept {
        // (1) 인덱스 범위 검사
        if (index < 0 || index >= m_Size) { return; }

        // (3) 인덱스가 0이라면
        if (index == 0) {
            DeleteBegin();
            return;
        }

        // (4) 인덱스가 끝이라면
        if (index == m_Size - 1) {
            DeleteEnd();
            return;
        }

        // (5) 반으로 나누어 진행 방향 결정, 제거할 노드 취득
        Node* current = nullptr;
        if ((m_Size / 2) < index) {         // 헤드에서 시작
            current = m_Head;
            for (auto i = 0; i < index; ++i) {
                current = current->next;
            }
        } else {                                // 테일에서 시작
            current = m_Head->prev;
            for (auto i = m_Size - 1; i > index; --i) {
                current = current->prev;
            }
        }

        // (6) 연결 끊기
        current->prev->next = current->next;
        current->next->prev = current->prev;

        // (7) 제거
        delete current;

        // (8) 크기 감소
        m_Size -= 1;
    }

    //! @brief 모든 노드를 제거하는 메서드
    void Clear() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 순회 및 제거
        auto* current = m_Head;
        for (auto i = 0; i < m_Size; ++i) {
            auto* target = current;
            delete target;
            current = current->next;
        }
    }

    //! @brief 순회 및 출력
    void Print() noexcept {
        // (1) 리스트가 비어 있다면
        if (m_Head == nullptr) { return; }

        // (2) 순회 및 출력
        auto* current = m_Head;
        for (auto i = 0; i < m_Size; ++i) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << "\n";
    }
};

int main(int argc, char* argv[]) {
    // 이중 원형 링크드 리스트
    DoublyCircularLinkedList dcll;

    // 맨 뒤 데이터 추가
    dcll.Append(10);
    dcll.Append(30);
    dcll.Append(20);

    // 중간 데이터 삭제
    dcll.DeleteAt(1);

    // 출력
    dcll.Print();

    return 0;
}

정리

단일 링크드 리스트

단일 링크드 리스트는 노드가 한 방향으로만 연결되고, 첫 노드(head)에서 순차적으로 접근이 가능합니다.

헤드 부분의 노드 삽입과 삭제는 매우 빠르나, 중간과 마지막 노드의 삽입과 삭제는 느립니다.

구조가 단순하여 구현이 쉽지만, 역방향 순회가 불가능합니다.

이중 링크드 리스트

이중 링크드 리스트는 노드가 양방향으로 연결되고, 헤드(head)와 테일(tail)이라는 두 개의 포인터 변수를 가집니다.

양쪽에서 노드의 삽입과 삭제가 가능하기 때문에 속도가 빠릅니다.

단일 링크드 리스트에 비해 구현이 다소 복잡하지만, 역방향 순회가 가능하다는 장점이 있습니다.

원형 링크드 리스트

원형 링크드 리스트는 단일과 이중으로 구현이 가능하고, 마지막 노드의 포인터가 헤드 포인터와 연결됩니다. 그래서 끝이 없고 완전한 순환이 가능합니다.

순환 구조를 갖기 때문에 잘못된 구현 시 무한 루프에 빠질 수 있다는 단점이 있지만, 계속되는 순환이 필요할 때 굉장히 유용하게 사용됩니다. (예: 뮤직 플레이어 등)