DLList: 双方向連結リスト

双方向連結リストの場合は各Nodeが前後のNodeを持つ.
SLListではnextのみであったが、prevというNodeも記録しているわけだ.

protected:
    struct Node
    {
        T m_value;
        std::shared_ptr<Node> m_prev;
        std::shared_ptr<Node> m_next;
    };

今回はListのノード管理はm_dummyに任せる.
sizeに関しては前回と同じため省略.

protected:
    std::shared_ptr<Node> m_dummy;
    int m_size;

Nodeはindexでdummy内から取得可能.
ただし、辿り方としては前と後ろの近い方から探索するようにする.
これはprevが追加されたことによりできるようになったことだね.
nextのみだと前からしか辿れないので、明らかに双方向連結リストの利点といえそう.

// Nodeの取得
std::shared_ptr<Node> GetNode(int i)
{
    std::shared_ptr<Node> p;
    if (i < m_size / 2)
    {
        // 前の方が近いので、前から辿る
        p = m_dummy->m_next;
        for (int j = 0; j < i; j++)
        {
            p = p->m_next;
        }
    }
    else
    {
        // 後ろの方が近いので、後ろから辿る
        p = m_dummy;
        for (int j = m_size; i < j; j--)
        {
            p = p->m_prev;
        }
    }

    return p;
}

Nodeが取れさえすれば、GetとSetの実装は簡単.
GetNodeでNodeを取得して、そこの値に対してGet/Setするだけである.

T Get(int i)
{
    GetNode(i)->m_value;
}

T Set(int i, T x)
{
    auto u = GetNode(i);
    T y = u->m_value;
    u->m_value = x;
    return y;
}

次は追加処理.
追加に関してはAddBeforeという関数内で行う.
これはNodeと値を引数に取る.

// 追加
void Add(int i, T x)
{
    AddBefore(GetNode(i), x);
}

Addの追加は対象のノードwの前に追加を行う.
wはw->prev, w, w->nextのような形式になっている.
そのため、追加後はw->prev, u, w, w->nextのような順になればよい.

そうなると接続関係をちゃんと整理が必要.
まずw->prev,w->prev->prevは変わらないが、nextに関してはuになるので、1:w->prev->next=uと変える.
uは簡単.2:u->prev = w->prevで3:u->next = wとなる.
wに関してはnextは特に変わらないけど、4:w->prev = uとなることも大事.
最後にw->nextは何も変わらないので、変更は不要.
後はこの1~4の変更を反映すればOK.

std::shared_ptr<Node> AddBefore(std::shared_ptr<Node> w, T x)
{
    std::shared_ptr<Node> u = std::make_shared<Node>();
    u->m_value = x;

    // w->prev, u, wのような順で挿入
    u->m_prev = w->m_prev;
    u->m_next = w;

    // wの前なので、prevに登録
    u->m_next->m_prev = u;

    // w->prevの後なので、nextに登録
    u->m_prev->m_next = u;

    // Count Up
    m_size++;

    return u;
}

Removeも見ておこう.
indexを指定して消すが、まずNodeを取得して、ノード自体の削除は別関数に任せる.

// 削除
T Remove(int i)
{
    auto w = GetNode(i);
    T x = w->m_value;
    Remove(w);
    return x;
}

削除するノードをwとすると、w->prev,w,w->nextの構造がw->prev,w->nextの構造になればよい.
つまりprev側はw->prev->next = w->nextと直接連結.
next側も直接w->next->prev= w->prevと直接連結.
これで依存関係が潰れたのでwを削除すれば終わり.

// 削除処理
void Remove(std::shared_ptr<Node> w)
{
    // prev, w, next　-> prev, next にする
    w->m_prev->m_next = w->m_next;
    w->m_next->m_prev = w->m_prev;
    w.reset();

    // Count Down
    m_size--;
}

これで双方向連結リストも終わり！