链表(上)

今天来学习链表(上)。

引言

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。

缓存大小有限，当缓存被用满时，就涉及到了缓存淘汰策略。

1. 先进先出策略FIFO(First In, First Out)
2. 最少使用策略LFU(Least Frequently Used)
3. 最近最少使用策略LRU(Least Recently Used)

经典的链表应用场景，LRU缓存淘汰算法。

五花八门的链表结构

单链表

首先需要搞清几个概念

• 链表结点：存储数据和后继指针的内存块
• 后继指针：记录下个结点地址的指针
• 头结点：第一个结点
• 尾结点：最后一个结点，指向一个空地址NULL

插入删除操作时间复杂度O(1)，随机访问时间复杂度O(n)

循环链表

循环链表是一种特殊的单链表，它跟单链表唯一的区别就在尾结点。单链表的尾结点指针指向空地址。而循环链表的尾结点指针是指向链表的头结点。

和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环形结构特点时，就特别适合采用循环链表，比如著名的约瑟夫问题。尽管用单链表也可以实现，但使用循环链表实现的话，代码会简洁很多。

双向链表

在实际的软件开发，双向链表更加常用。

单链表只有一个方向，结点只有一个后继指针，next指向后面的结点。而双向链表，它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样带来了双向链表操作的灵活性。

单链表 vs 双向链表

在实际的软件开发中，从链表删除一个数据无外乎这两种情况：

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

对于第一种情况，无论是单链表和双向链表，都需要遍历查找。所以删除操作的时间复杂度是O(1)，遍历查找的时间复杂度是O(n)，根据加法法则，总的时间复杂度O(n)。

对于第二种情况，由于删除某个结点q需要知道其前驱结点，而单链表并不支持直接获取前驱结点，时间复杂度O(n)；而双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历，时间复杂度O(1)

同理在链表的某个结点前面或者后面插入一个结点，双向链表时间复杂度O(1)；单链表时间复杂度O(n)

除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为双向链表可以记录上次查找的位置p，每次查询时，根据要查询值和位置p的值的大小关系，决定往前查找还是往后查找，所以平均只需要查找一半的数据。

Java语言中的LinkedHashMap就用到了双向链表，尽管比较费内存，但是应用比较广泛。

这里面，涉及到一个重要的涉及思想：空间换时间。对于执行比较慢的程序，可以通过消耗更多的内存(空间换时间)，来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间(时间换空间)来降低内存的消耗。

双向循环链表

概念容易理解，但是代码写起来更复杂了....

数组 vs 链表

底层结构上：数组连续的内存空间；链表零散的内存块

时间复杂度：

时间复杂度	数组	链表
插入、删除	O(n)	O(1)
随机访问	O(1)	O(n)

在实际开发中，不能简单的根据时间复杂度来决定使用哪个数据结构来存储数据。

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

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

除此之外，如果对内存的使用非常苛刻，那么数组更适合。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片。

解答开篇

如何基于链表实现LRU缓存淘汰算法？

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

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

时间复杂度O(n)

思考：如何利用数组来实现LRU缓存淘汰策略？

思考

如何判断一个字符串是否是回文字符串的问题？

这个问题考查了两个知识点：

1. 快慢指针
2. 反转相邻结点

花了一个下午写了关于链表的一些基本操作—。—，如下

class Node:
  """
  	单链表-结点
  """
    def __init__(self, data, next_node=None):
        self.data = data
        self.next = next_node
        
class SingleLinkedList(object):
  """
  	单链表
  """
    def __init__(self):
        self.__head = None
        
    def find_by_value(self, value):
        """
            根据value在链表中查找
            时间复杂度O(n)
        :return: node
        """
        node = self.__head
        while (node is not None) and (node.data != value):
            node = node.next
        return node

    def find_by_index(self, index):
        """
            根据index在链表中查找
            时间复杂度O(n)
        :return: node
        """
        node = self.__head
        pos = 0
        while (node is not None) and (pos != index):
            node = node.next
            pos += 1
        return node

    def insert_to_head(self, value):
        """
            头结点插入
            时间复杂度O(1)
        :return: None
        """
        node = Node(value)
        node.next = self.__head
        self.__head = node

    def insert_after(self, node, value):
        """
            在链表的某个指定Node节点之后插入一个存储value数据的Node节点
            时间复杂度O(1)
        :return: None
        """
        # 如果在空结点之后插入数据结点 则什么都不做
        if not node:
            return
        new_node = Node(value)

        new_node.next = node.next
        node.next = new_node

    def insert_before(self, node, value):
        """
            在链表的某个指定Node节点之前插入一个存储value数据的Node节点
            时间复杂度O(n)
        :return: None
        """
        # 如果在空结点之前或者空链表之前插入结点 则什么都不做
        if (node is None) or (self.__head is None):
            return

        # 头结点插入
        if node == self.__head:
            self.insert_to_head(value)
            return

        new_node = Node(value)
        pos = self.__head
        # 注意：判断node是否存在链表中
        not_found = False
        while pos.next != node:
            if pos.next is None:
                not_found = True
                break
            pos = pos.next

        if not_found:
            pos.next = new_node
            new_node.next = node

    def delete_by_node(self, node):
        """
            在链表中删除指定Node的节点
            时间复杂度O(n)
        :return: None
        """
        # 空链表 什么都不做
        if self.__head is None:
            return

        # 删除头结点 头结点后移
        if node == self.__head:
            self.__head = self.__head.next
            return

        pos = self.__head
        not_found = False
        while pos.next != node:
            if pos.next is None:
                not_found = True
                break
            pos = pos.next

        if not_found:
            pos.next = node.next

    def delete_by_value(self, value):
        """
            在链表中删除指定存储数据的Node节点
            时间复杂度O(n)
        :return: None
        """
        if self.__head is None:
            return

        if self.__head.data == value:
            self.__head = self.__head.next
            return

        # 这里用到了pre结点 因为删除指定value结点时候需要用到前一个结点
        pre = self.__head
        node = self.__head.next
        not_found = False
        while node.data != value:
            if node.next is None:
                not_found = True
                break

            pre = node
            node = node.next

        if not_found:
            pre.next = node.next

    def delete_last_n_node(self, n):
        """
            删除链表中倒数第N个节点
            主要思路：
                设置快、慢两个指针，快指针先行，慢指针不动；当快指针走了N步时，快慢指针同时向链表尾部移动，
                当快指针到达链表尾部时，慢指针指向的就是链表倒数第N个结点(脑子绕不过弯来时，画画图就明白了)
            时间复杂度O(n)

            ** 单链表删除结点的时候，一定要注意保存被删除结点的前驱结点
        :return: None
        """
        fast = self.__head
        slow = self.__head
        step = 0
        while step <= n:
            fast = fast.next
            step += 1

        tmp = None
        while fast.next is not None:
            tmp = slow
            slow = slow.next
            fast = fast.next

        tmp.next = slow.next

    def find_mid_node(self):
        """
            查找链表中的中间节点
            主要思想：
                设置快慢指针，快指针每次跨两步，满指针每次跨一步，则当快指针到达链表尾部的时候，慢指针指向链表的中间结点
                同理 脑子绕不过弯时，画画图就明白了
            时间复杂度O(n)
        :return: node
        """
        fast = self.__head
        slow = self.__head

        # 单链表个数局限为奇数
        # while (fast.next is not None):

        # 单链表个数为奇数或者偶数可以
        while (fast is not None) and (fast.next is not None):
            fast = fast.next.next
            slow = slow.next
        return slow

    def create_node(self, value):
        """
            创建一个存储value值的Node节点
        :return: node
        """
        return Node(value)

    def print_all(self):
        """
            打印当前链表所有节点数据
            时间复杂度O(n)
        :return: None
        """
        if self.__head is None:
            return

        node = self.__head
        while node.next is not None:
            print(node.data, end='')
            node = node.next
        # 打印最后一个结点
        print(node.data)

    def reversed_self(self):
        """
            翻转链表
            时间复杂度O(n)
        :return: None
        """
        pre = self.__head
        node = self.__head.next

        # 结束条件 pre为链表最后一个结点 node为None
        while node is not None:
            pre, node = self.__reversed_with_two_node(pre, node)

        # 修改尾结点和头结点
        self.__head.next = None
        self.__head = pre

    def __reversed_with_two_node(self, pre, node):
        """
            翻转相邻两个结点
            思路：利用一个中间结点tmp
        :return: node, node
        """
        # 保存node的下一个结点
        tmp = node.next
        # 修改node指针
        node.next = pre

        # 这两行的意思应该是后移结点
        pre = node
        node = tmp
        return pre, node

    def has_ring(self):
        """
            检测是否有环
            主要思想：
                设置快、慢两个指针，快指针每次跨两步、慢指针每次跨一步，
                如果快指针没有与慢指针相遇而是顺利到达链表尾部，说明没有环，反之存在环
                自己画画图看看 就明白了
            时间复杂度O(n)
        :return: True or False
        """
        fast = self.__head
        slow = self.__head

        # 当链表为空或者只有一个结点时，直接返回False
        while (fast.next is not None) and (fast is not None):
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True

        return False

    def reverse_head(self, head):
        """
            根据给的结点，翻转之后的结点
        :return: node
        """
        reverse_head = None
        while head:
            next_node = head.next
            head.next = reverse_head
            reverse_head = head
            head = next_node
        return reverse_head

    def is_palindrome(self):
        """
            判断是否是回文串
            主要思路：快、慢两个指针，快指针每次前进两步、慢指针每次前进一步。当快指针到达链表尾部时，慢指针到达链表中间节点，翻转慢指针到链表尾部的这部分结										点，然后依次对比链表头部和翻转后的部分链表数据是否相同
        :return: True or False
        """
        slow = self.__head
        fast = self.__head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        head_a = self.__head
        head_b = self.reverse_head(slow)

        is_palin = True
        while head_a and head_b:
            if head_a.data == head_b.data:
                head_a = head_a.next
                head_b = head_b.next
            else:
                is_palin = False
                break
        return is_palin

总结

写链表代码时有几点感受：

1. 在删除链表结点的时候一定要注意利用中间变量保存前驱结点
2. 快慢指针法在链表中有着广泛的应用，比如说查找中间结点、检测链表是否包含环、判断是否为回文串、删除链表倒数第N个结点等等。
3. 多写多练

参考链接：

1. 数据结构与算法之美相关代码