什么时候使用双向链表 - (sunznx) 振翅飞翔
08 August 2019

相信要让大家自己写一个 “单向链表” 和 “双向链表” 很容易,但是考虑过 “什么时候使用双向链表” 吗?
既然都是 O(n) ,那么为什么还要使用双向链表。下面会介绍一个场景,该场景来自 leetcode 的 146 LRU Cache

长话短说:
单链表的情况,我们要删除一个节点,需要遍历到该节点的时候,同时保留该节点的 “前一个节点”,时间复杂度 O(N)
双向链表的情况,我们可以借助一个 map 来直接索引到该节点,并利用 node->prev 来直接获取 “前一个节点”,时间复杂度 是 O(1)

假设我们的链表长这样:

现在要删除 n3 节点

然后

这个过程是 O(n) ,代码如下

class MyList
{
    ...

    public function remove($data)
    {
        ...

        $prev = $this->head;
        $cur = $prev->next;
        while (!empty($prev) && !empty($cur)) {
            if ($cur->data == $data) {
                $this->removeHelper($prev, $cur);
                break;
            }

            $prev = $prev->next;
            $cur = $cur->next;
        }
    }

    private function removeHelper($prev, $cur)
    {
        if ($cur == $this->tail) {
            $this->tail = $prev;
        }
        $prev->next = $cur->next;
    }

    public function append($data)
    {
        $n = new Node($data);
        ...
    }
}

那么能不能优化呢,如果链表是 unique 的,那么我们可以用一个 map 来存储指针的地址,然后直接 O(1) 定位到对应的链表节点。
但是,在单向链表的情况下,我们拿不到链表节点的 prev 节点,这时候就需要双向链表了

class MyList
{
    ...

    public function remove($data)
    {
        ...

        $cur = $this->map[$data];
        $prev = $cur->prev;            // 如果是单向链表的时候,我们拿不到 prev 节点
        $this->removeHelper($prev, $cur);
    }

    private function removeHelper($prev, $cur)
    {
        if ($cur == $this->tail) {
            $this->tail = $prev;
        }
        $prev->next = $cur->next;
    }

    public function append($data)
    {
        $n = new Node($data);
        $this->map[$data] = $n;
        ...
    }
}