Java 集合面试题之链表

2024-01-07 21:15:39

Java 集合面试题之链表

链表

单向链表
  • 链表中的每一个元素称之为结点(Node)

  • 物理存储单元上,非连续、非顺序的存储结构

  • 单向链表:每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。记录下个结点地址的指针叫作后继指针 next

在这里插入图片描述

代码实现参考:

在这里插入图片描述

链表中的某个节点为B,B的下一个节点为C 表示: B.next==C

单向链表时间复杂度分析

(1)查询操作

在这里插入图片描述

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

  • 查询其他结点需要遍历链表,时间复杂度是O(n)

(2)插入和删除操作

在这里插入图片描述

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

而双向链表,顾名思义,它支持两个方向

  • 每个结点不止有一个后继指针 next 指向后面的结点

  • 有一个前驱指针 prev 指向前面的结点

参考代码

在这里插入图片描述
在这里插入图片描述

对比单链表:

  • 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址

  • 支持双向遍历,这样也带来了双向链表操作的灵活性

双向链表时间复杂度分析

在这里插入图片描述

(1)查询操作

  • 查询头尾结点的时间复杂度是O(1)

  • 平均的查询时间复杂度是O(n)

  • 给定节点找前驱节点的时间复杂度为O(1)

(2)增删操作

  • 头尾结点增删的时间复杂度为O(1)

  • 其他部分结点增删的时间复杂度是 O(n)

  • 给定节点增删的时间复杂度为O(1)

面试题-ArrayList和LinkedList的区别是什么?
  • 底层数据结构

    • ArrayList 是动态数组的数据结构实现

    • LinkedList 是双向链表的数据结构实现

  • 操作数据效率

    • ArrayList按照下标查询的时间复杂度O(1)【内存是连续的,根据寻址公式】, LinkedList不支持下标查询
    • 查找(未知索引): ArrayList需要遍历,链表也需要遍历,时间复杂度都是O(n)
    • 新增和删除
      • ArrayList尾部插入和删除,时间复杂度是O(1);其他部分增删需要挪动数组,时间复杂度是O(n)
      • LinkedList头尾节点增删时间复杂度是O(1),其他都需要遍历链表,时间复杂度是O(n)
  • 内存空间占用

    • ArrayList底层是数组,内存连续,节省内存

    • LinkedList 是双向链表需要存储数据,和两个指针,更占用内存

  • 线程安全

    • ArrayList和LinkedList都不是线程安全的
    • 如果需要保证线程安全,有两种方案:
      • 在方法内使用,局部变量则是线程安全的
      • 使用线程安全的ArrayList和LinkedList

大家好,我是xwhking,一名技术爱好者,目前正在全力学习 Java,前端也会一点,如果你有任何疑问请你评论,或者可以加我QQ(2837468248)说明来意!希望能够与你共同进步

文章来源:https://blog.csdn.net/Go_ahead_forever/article/details/135405679
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。