三、数据结构与算法 — 链表

链表与数组的区别

• 链表不是连续的

  
  

单链表与循环链表

注意链表中的头结点和尾结点。

循环链表从尾可以方便的到头，适合环型结构数据，比如约瑟夫问题。

双向链表

优势：

时间复杂度找到前驱结点

删除，插入更高效。考虑以下两种情况：

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

查询更高效：记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

以空间换时间

再次比较数组和链表

从复杂度分析：

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

其它角度：

• 内存连续，利用 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。

• 而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

• 数组的大小固定，即使动态申请，也需要拷贝数据，费时费力。

• 链表支持动态扩容.

链表删除会触发jcc的垃圾回收机制，频繁地触发垃圾回收会影响性能

class SinglyLinkedList:
    def __init__(self) -> None:
        self.head = None  # 头指针

    def insert_tail(self, value):
        if self.head is None:
            self.insert_to_head(value)
            return
        q = self.head
        # 寻找尾结点
        while q.next is not None:
            q = q.next
        new_node = self.Node(value)
        q.next = new_node

    def insert_to_head(self, value):
        new_node = self.Node(value)
        if self.head is None:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def delete_by_value(self, value):
        if self.head is None:
            return False
        q = self.head
        p = None
        while q is not None and q.data != value:
            p = q
            q = q.next
        # 当链表中没有 value 的时候
        if q is None:
            return False
        # head 的值就是 value 的时候
        if p is None:
            self.head = self.head.next
        else:
            p.next = q.next
        return True

    def find_by_value(self, value):
        if self.head is None:
            return
        q = self.head
        while q is not None and q.data != value:
            q = q.next

        if q is None:
            return
        return q

    def insert_after(self, node, value):
        if node is None:
            return
        new_node = self.Node(value)
        new_node.next = node.next
        node.next = new_node

    def insert_before(self, node, value):
        if self.head is None:
            self.insert_to_head(value)
            return
        q = self.head
        while q is not None and q.next != node:
            q = q.next
        # 链表中，没有一个与 node 相等的结点
        if q is None:
            return
        new_node = self.Node(value)
        new_node.next = node
        q.next = new_node
       
    def print_all(self):
        if self.head is None:
            return
        q = self.head
        while q is not None:
            print(q.data)
            q = q.next

    class Node:
        def __init__(self, data) -> None:
            self.data = data
            self.next = None


def test_link():
    link = SinglyLinkedList()
    data = [1, 2, 5, 3, 1]
    for i in data:
        link.insert_tail(i)
    link.insert_to_head(99)
    # 打印内容为 99 1 2 5 3 1
    link.print_all()
    link.delete_by_value(2)
    assert not link.delete_by_value(999)
    assert link.delete_by_value(99)
    # 打印内容为 1 5 3 1
    link.print_all()
    assert link.find_by_value(2) is None
    new_node = link.find_by_value(3)
    link.insert_after(new_node, 10)
    assert link.find_by_value(3).next.data == 10
    link.insert_before(new_node, 30)
    assert link.find_by_value(5).next.data == 30

if __name__ == '__main__':
    test_link()