자료구조) 양방향 연결 리스트

양방향(이중) 연결 리스트(Doubly Linked List)는 각 노드가 앞뒤로 연결된 형태의 자료구조이다.

단방향 연결 리스트(Singly Linked List)와 달리 이전 노드를 가리키는 포인터(left)와 다음 노드를 가리키는 포인터(right)를 모두 포함하므로, 양방향 탐색이 가능하다.

노드(Node) 구조

struct Node
{
    T item = T();      // 데이터 저장
    Node* left = nullptr;  // 이전 노드를 가리키는 포인터
    Node* right = nullptr; // 다음 노드를 가리키는 포인터
};

• item → 실제 저장되는 데이터

• left → 이전 노드를 가리키는 포인터이다. (단방향 리스트에는 없던 속성)

• right → 다음 노드를 가리키는 포인터이다.

• 리스트의 첫 번째 노드의 left는 nullptr이며, 마지막 노드의 right도 nullptr이다.

양방향 연결 리스트 핵심 연산

맨 앞에 삽입 (PushFront)

새로운 노드를 리스트의 맨 앞에 추가하는 연산이다.

예제코드

void PushFront(T item)
{
    Node* temp = new Node;
    temp->item = item;

    temp->right = first_;
    if (first_)
        first_->left = temp;
    
    first_ = temp;
    temp->left = nullptr;
}

동작원리

• 새 노드를 생성한다.

• 새 노드의 right를 기존 first_로 설정한다.

• 기존 first_가 존재하면, first_->left를 새 노드로 연결한다.

• first_를 새 노드로 변경한다.

• 새 노드의 left를 nullptr로 설정하여 처음 노드임을 명확히 한다.

시간 복잡도: O(1) → 항상 맨 앞에 추가하므로 빠르다.

맨 뒤에 삽입 (PushBack)

새로운 노드를 리스트의 맨 끝에 추가하는 연산이다.

예제코드

void PushBack(T item)
{
    if (first_)
    {
        Node* curNode = first_;
        while (curNode->right)
        {
            curNode = curNode->right;
        }

        Node* temp = new Node{ item, curNode, nullptr };
        curNode->right = temp;
    }
    else
    {
        PushFront(item);
    }
}

동작원리

• 리스트가 비어있으면 PushFront로 노드를 추가한다.
• 마지막 노드까지 이동한다.
• 새로운 노드를 생성하고, 이전 노드를 curNode로 설정한다.
• 기존 마지막 노드의 right를 새로운 노드로 연결한다.

시간 복잡도: O(n) → 마지막 노드를 찾기 위해 선형 탐색 필요

맨 앞의 노드 삭제 (PopFront)

리스트의 첫 번째 노드를 삭제하는 연산이다.

예제코드

void PopFront()
{
    if (IsEmpty())
    {
        std::cout << "Nothing to Pop in PopFront()" << std::endl;
        return;
    }

    assert(first_);

    Node* temp = first_;
    first_ = first_->right;

    if (first_)
        first_->left = nullptr;

    delete temp;
}

동작원리

• first_가 nullptr이면 삭제할 것이 없으므로 종료한다.
• 첫 번째 노드를 임시 변수(temp)에 저장한다.
• first_를 기존 first_->right로 변경한다.
• 새로운 first_가 존재하면 left 포인터를 nullptr로 설정한다.
• temp를 delete하여 메모리를 해제한다.

시간 복잡도: O(1) → 항상 첫 번째 노드만 삭제

맨 뒤의 노드 삭제 (PopBack)

리스트의 마지막 노드를 삭제하는 연산이다.

예제코드

void PopBack()
{
    if (IsEmpty())
    {
        std::cout << "Nothing to Pop in PopBack()" << std::endl;
        return;
    }

    assert(first_);

    Node* curNode = first_;
    if (curNode->right)
    {
        while (curNode->right->right)
        {
            curNode = curNode->right;
        }
        Node* temp = curNode->right;
        curNode->right = nullptr;

        delete temp;
    }
    else
    {
        delete first_;
        first_ = nullptr;
    }
}

동작원리

• 리스트가 비어있는지 확인한다.
• 노드가 하나뿐이라면 first_를 삭제하고 nullptr로 설정한다.
• 마지막에서 두 번째 노드를 찾는다.
• 마지막 노드를 삭제하고, 두 번째 마지막 노드의 right를 nullptr로 설정한다.

시간 복잡도: O(n) → 마지막 노드의 이전 노드를 찾기 위해 선형 탐색 필요

리스트 반전 (Reverse)

연결 리스트의 순서를 반대로 뒤집는 연산이다.

예제코드

void Reverse()
{
    if (IsEmpty())
        return;

    Node* curNode = first_;
    Node* beforeNode = nullptr;

    while (curNode)
    {
        beforeNode = curNode;
        curNode = curNode->right;

        std::swap(beforeNode->left, beforeNode->right);
    }

    first_ = beforeNode;
}

동작원리

• curNode를 순회하며 left와 right 포인터를 서로 바꾼다.
• 리스트의 끝까지 이동하면, first_를 beforeNode로 변경한다.

시간 복잡도: O(n) → 모든 노드를 한 번씩 방문하여 방향을 변경

양방향 연결 리스트의 특징

• 양방향 탐색 가능 → left와 right를 통해 앞뒤로 이동할 수 있다.
• 삽입/삭제가 빠름 → 노드 참조만으로 O(1) 시간에 가능하다.
• 추가 메모리 필요 → left 포인터 저장을 위한 추가 공간이 필요하다.