数据结构与算法-链表LinkedList

链表: 通过指针将一组零散的内存块串联在一起

单链表

        头结点(data | next) -> data | next -> 尾节点(data | next) -> null

双向链表

    头结点(prev | data | next) < - > prev | data | next < - > 尾节点(prev | data | next) 

    比单链表消耗更多内存空间

循环链表:一种特殊的单链表

    头结点(data | next) -> data | next -> 尾节点(data | next) -> null   

    适用于处理的数据具有环型结构

双向循环链表

    头结点(data | next) -> data | next -> 尾节点(data | next) -> 头节点

链表对比

    随机访问

        时间复杂度为O(n)        

        场景:有序链表按值查询

            双向链表效率比单链表效率平均快1倍            

    插入

        时间复杂度为O(1)

        场景: 指定结点前面插入一个结点

            单链表的时间复杂度为:O(n)  (从头结点开始遍历链表找到前驱结点)

            双向链表的时间复杂度为:O(1)  (结点已经保存了前驱结点的指针)

    删除    

        时间复杂度为O(1)

        场景1: 删除结点中“值等于某个给定值”的结点

            单纯删除操作时间复杂度是O(1), 遍历查找的时间对应时间复杂度为O(n)

            加法法则 -> 时间复杂度是O(1)

        场景2: 删除给定指针指向的结点

            单链表的时间复杂度为:O(n)  (从头结点开始遍历链表找到前驱结点)

            双向链表的时间复杂度为:O(1)  (结点已经保存了前驱结点的指针)        

链表 VS 数组

                                        数组                                    链表    

        插入/删除                O(n)                                    O(1)

        随机访问                 O(1)                                    O(n)

        CPU缓存               有效预读,CPU缓存            不是连续内存空间,无法预读,CPU不友好

        存储空间                固定大小限制                    无限制,动态扩容

        内存消耗                指定大小                           额外存储前驱后继结点指针,消耗翻倍  

        内存使用                 正常                                 频繁插入/删除,内存申请/释放->内存碎片