[Data Structure] 이중 연결 리스트

이중 연결 리스트 (Doubly Linked List)

기존 연결 리스트는 단순히 한 방향으로만 이동할 수 있었다. 양방향에 대한 포인터를 가지는 노드를 사용하면 양방향으로 이동할 수 있는 이중 연결 리스트를 구현할 수 있다.

https://www.geeksforgeeks.org/doubly-linked-list-tutorial/

양방향 노드

template <typename T>
class BidirectionalNode
{
    public:
        BidirectionalNode(T data)
        {
            this->data = data;
        }

    T data;
    BidirectionalNode<T>* left = nullptr;
    BidirectionalNode<T>* right = nullptr;
};

노드 삽입

양쪽 노드에 대한 포인터 처리만 해주면 된다.

// 삽입
void Insert(BidirectionalNode<T>* newNode, BidirectionalNode<T>* node) // node의 오른쪽에 newNode를 삽입
{
    newNode->left = node;
    newNode->right = node->right;
    if (node->right) // 오른쪽 노드가 있는 경우에만 연결
        node->right->left = newNode;
    node->right = newNode;
}

노드 삭제

삽입과 동일하게 포인터 처리만 잘 해주면 된다.

// 삭제
void Delete(BidirectionalNode<T>* node)
{
    if (node == head)
    {
        std::cout << "Cannot delete head node\n";
        return;
    }

    BidirectionalNode<T>* leftNode = node->left;
    BidirectionalNode<T>* rightNode = node->right;
    leftNode->right = node->right;
    rightNode->left = node->left;
    delete node;
}