标签归档:链表

算法学习三、链表

常见的缓存策略有三种:先进先出策略 FIFO,最少使用策略 LFU,最近最少使用策略 LRU。那么如何用链表来实现 LRU 缓存淘汰算法呢?

链表结构

链表是通过“指针”将一组零散的内存块串联起来使用。常见的三种链表结构:单链表、双向链表、循环链表。

单链表

我们把内存块称为链表的“节点”,为了将所有的节点串起来,每个链表的节点除了存储数据之外,还需要记录链上的下一个结点的地址。记录下个节点的地址叫做后继指针 next

两个特殊的节点:头节点尾节点。头节点记录链表的基地址,其 data 为 NULL,尾节点指向一个空地址 NULL

链表的插入与删除,只需要考虑相邻节点的指针变化,对应的时间复杂度为 O(1)。

随机访问某一个节点,需要从头节点一个节点一个节点的进行遍历,直到找到对应的节点,时间复杂度是 O(n)。

循环链表

循环链表是一个特殊的单链表,其尾节点指针指向链表的头节点。

双向链表

双向链表支持两个方向,每个节点不仅有一个后继指针 next 指向后面的节点,还有一个前驱指针 prev 指向前面的节点。

双向链表的缺点是占用更多的内存,其适合解决的问题:

删除操作

实际的软件开发中,删除一个数据有两种情况:

  • 删除结点中“值等于某个给定值”的结点
  • 删除给定指针指向的结点

对于第一种情况,不管是单链表还是双向链表,为了查找到值等于给定值的结点,都需要从头结点开始一个一个依次遍历对比,直到找到值等于给定值的结点,将其删除。尽管单纯的删除操作时间复杂度是 O(1),但遍历查找的时间是主要的耗时点,对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则,删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。对于第二种情况,我们已经找到了要删除的结点,但是删除某个结点 q 需要知道其前驱结点,而单链表并不支持直接获取前驱结点,所以,为了找到前驱结点,我们还是要从头结点开始遍历链表,直到 p->next=q,说明 p 是 q 的前驱结点。但是对于双向链表来说,这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针,不需要像单链表那样遍历。所以,针对第二种情况,单链表删除操作需要 O(n) 的时间复杂度,而双向链表只需要在 O(1) 的时间复杂度内就搞定了!

同理,如果我们希望在链表的某个指定结点前面插入一个结点,双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定,而单向链表需要 O(n) 的时间复杂度。

对于一个有序链表,双向链表的按值查询的效率也要比单链表高一些。因为,我们可以记录上次查找的位置 p,每次查询时,根据要查找的值与 p 的大小关系,决定是往前还是往后查找,所以平均只需要查找一半的数据。

双向循环链表

链表 vs 数组

数组与链表相比简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。

数组的缺点是大小固定,一经声明就要占用整块连续内存空间。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致“内存不足”。如果声明的数组过小,则可能出现不够用的情况。这时只能再申请一个更大的内存空间,把原数组拷贝进去,非常费时。链表本身没有大小的限制,天然地支持动态扩容,我觉得这也是它与数组最大的区别。

用链表实现一个 LRU 缓存淘汰算法

我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。

  1. 如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中,又可以分为两种情况:
    1. 如果此时缓存未满,则将此结点直接插入到链表的头部
    2. 如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部

5 个常见的链表操作

单链表反转

public function reverse()
{
    if ($this->list == null || $this->list->head == null || $this->list->head->next == null) {
        return false;
    }


    $preNode = null;
    $curNode = $this->list->head->next;
    $remainNode = null;


    while ($curNode != null) {
        $remainNode = $curNode->next;
        $curNode->next = $preNode;
        $preNode = $curNode;
        $curNode = $remainNode;
    }


    $this->list->head->next = $preNode;


    return true

链表中环的检测

public function checkCircle()
{
    if ($this->list == null || $this->list->head == null || $this->list->head->next == null) {
        return false;
    }


    $slow = $this->list->head->next;
    $fast = $this->list->head->next;


    while ($fast != null && $fast->next != null) {
        $slow = $slow->next;
        $fast = $fast->next->next;


        if ($slow === $fast) {
            return true;
        }
    }


    return false

两个有序的链表合并

public function mergeSortedList(SingleLinkedList $listA, SingleLinkedList $listB)
{
    if ($listA == null) {
        return $listA;
    }
    if ($listB == null) {
        return $listB;
    }


    $newList = new SingleLinkedList();
    $newRootNode = $newList->head;
    $pListA = $listA->head->next;
    $pListB = $listB->head->next;


    while ($pListA != null && $pListB != null) {
        if ($pListA->data <= $pListB->data) {
            $newRootNode->next = $pListA;
            $pListA = $pListA->next;
        } else {
            $newRootNode->next = $pListB;
            $pListB = $pListB->next;
        }
        $newRootNode = $newRootNode->next;
    }


    if ($pListA != null) {
        $newRootNode->next = $pListA;
    }
    if ($pListB != null) {
        $newRootNode->next = $pListB;
    }
    $newList->length = $listA->length + $listB->length;


    return $newList;

删除链表倒数第 n 个结点

public function deleteLastKth($index)
{
    if ($this->list == null || $this->list->head == null || $this->list->head->next == null) {
        return false;
    }


    $i = 1;
    $fast = $this->list->head;
    while ($fast != null && $i < $index) {
        $fast = $fast->next;
    }


    $prev = null;
    $slow = $this->list->head;
    while ($fast != null && $fast->next != null) {
        $prev = $slow;
        $slow = $slow->next;
        $fast = $fast->next;
    }


    if ($prev == null) {
        $this->list->head->next = $slow->next;
    } else {
        $prev->next = $prev->next->next;
    }


    return true

求链表的中间结点

public function findMiddleNode()
{
    if ($this->list == null || $this->list->head == null || $this->list->head->next == null) {
        return false;
    }


    $slow = $this->list->head;
    $fast = $this->list->head;
    while ($fast != null && $fast->next != null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }


    return $slow;