【Java面试】十四、LinkedList相关

文章目录

• 1、单向链表
• • 1.1 结构
  • 1.2 查询的时间复杂度
  • 1.3 插入删除的时间复杂度
  • 2、双向链表
  • • 2.1 时间复杂度
    • 3、ArrayList和LinkedList的区别是什么

      1、单向链表

      1.1 结构

      • 存储空间上，非连续
      • 链表的每个元素称结点Node
      • 每个结点包括两块：存储数据的数据域data、存储下一个节点地址的指针域next（后继指针）

        

        代码实现如下，假设链表中有个B结点，其下一个结点为C，则B.next == C

        

        1.2 查询的时间复杂度

        

        • 只有在查询头节点的时候不需要遍历链表，时间复杂度是O(1)
        • 查询其他结点需要遍历链表，时间复杂度是 O(n)

          1.3 插入删除的时间复杂度

          

          • 只有在添加和删除头节点的时候不需要遍历链表，时间复杂度是 O(1)
          • 添加或删除其他结点时，首先需要遍历链表找到对应节点后，才能完成新增或删除节点，因此时间复杂度是 O(n)

            2、双向链表

            每个结点有三部分：

            • 前驱指针prev
            • 数据域data
            • 后继指针next

              因此，可以支持双向遍历

              

              代码实现：

              

              2.1 时间复杂度

              查询时：

              • 查询头尾结点的时间复杂度是 O(1)
              • 平均的查询时间复杂度是 O(n)
              • 给定节点找前驱后继结点的时间复杂度为 O(1)

                增删时：

                • 头尾结点增删的时间复杂度为 O(1)
                • 其他部分结点增删的时间复杂度是 O(n)
                • 给定节点增删前驱后继结点的时间复杂度为 O(1)

                  3、ArrayList和LinkedList的区别是什么

                  1）底层数据结构上来说：

                  • ArrayList底层是一个数组
                  • LinkedList底层是一个双向链表

                    

                    2）操作数据的效率上来说：

                    • ArrayList 按照下标査询的时间复杂度 O(1)，因为内存是连续的，可根据寻址公式取。而LinkedList 不支持下标查询
                    • 查找数据时(ArrayList未知索引)： ArrayList需要遍历，链表也需要链表，时间复杂度都是 O(n)
                    • 新增和删除：ArrayList 尾部插入和删除，时间复杂度是 O(1)，其他部分增删需要挪动数组，时间复杂度是 O(n)。LinkedList 头尾节点增删时间复杂度是 O(1)，其他都需要先遍历链表找数据，时间复杂度是 O(n)

                      3）空间上来说：

                      • ArrayList底层是数组，内存连续，只存数据，节省内存空间
                      • LinkedList底层是双向链表，内存不连续，除了存数据，还要存两个指针，不节省内存

                        4）线程安全上来说：

                        • ArrayList 和 LinkedList 都不是线程安全的

                          PS：如果要保证线程安全，可考虑：

                          • 在方法内部的局部变量中用，局部变量，每个线程一份，无安全问题
                          • 使用Collections工具类，包装一下ArrayList 和 LinkedList（底层加了synchronized锁），就是线程安全的