数据结构中二叉树,哈希表,顺序表,链表的比较补充

简介: 二叉搜索树,哈希表,顺序表,链表的特点的比较

阿华代码,不是逆风,就是我疯,希望本文内容能帮到你!你们的点赞收藏是我前进最大的动力!!

目录

一:二叉搜索树

二:哈希表

三:ArrayList

四:LinedList

1:特点

2:三问:

(1):用LinkedList 是否遍历速度更快呢?

(2):ArrayList是要预分配空间的,那么用LinkedList是否更节省内存呢?

(3):用LinkedList ,在中间位置插入删除,为什么是O(N)?



零:引入

查询时间复杂度,我们默认是以最坏的情况来看,其次说平均,基本不会说最优的情况,

平衡二叉树,查询能达到O(logN),快于O(N),近似理解成O(1)

一:二叉搜索树

元素非常多,树的高度就很高,就会增加查询过程中的次数,如果实在数据库中就会比较敏感了,每次比较都可能会涉及到硬盘操作,

二:哈希表

1:速度最快O(1),哈希表会在合适的时机进行扩容,可以保持整体的时间复杂度任然是O(1),在实际开发中,我们用到的最多的就是hash表和数组

2:查询大致步骤——哈希表是把key转换为数组下标(通过一定的哈希函数),再在对应的数组下标中进行查找,这里只能比较相等

3:与数据库异——数据库查询的时候,经常需要指定条件,不是一定按照 相等 来比较的 例如:<>  between and  范围查询


三:ArrayList

错误说法:ArrayList 查找速度比较快,LinkedList新增删除的速度比较快。

1:ArrayList底层使用的是数组,可以进行随机访问,每次随机访问进行读写的时候,速度是比较快的

2:随机访问不是查找,查找使用的是indexOf 这样的方法,按照元素的值进行查找,这个过程是要遍历ArrayList 开销为O(N)

3:ArrayList 尾插入/删除的速度比较快,但是头/中间/尾插入,删除元素比较慢(会对元素进行搬运)

四:LinedList

1:特点

底层是一个链表,不能进行随机访问

进行头/尾插,头/尾删时间复杂度都是O(1)

进行查找/中间位置的插入删除操作,都是O(N)

总结:相比较于ArrayList优势在于能够快速的进行头插、头删,在实现队列的时候很有用,其他方面ArrayList更优

2:三问:

(1):用LinkedList 是否遍历速度更快呢?

答:链表访问下个元素的操作是用next这个引用,相比较顺序表元素下标++的操作,多了一次内存访问的过程

(2):ArrayList是要预分配空间的,那么用LinkedList是否更节省内存呢?

答:链表的每一个节点都要有额外的空间储存指针,具体谁更省,有待考虑

(3):用LinkedList ,在中间位置插入删除,为什么是O(N)?

LinkedList 是通过add(元素,下标)进行插入,这个根据下标找位置的过程,就是链表遍历O(N)的操作。



相关文章
|
13天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
76 29
|
13天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
70 25
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
38 5
|
1月前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算(头歌实践教学平台习题)【合集】
本文档介绍了线性表的基本运算任务,涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法,并提供了测试说明和通关代码。 主要内容包括: - **任务描述**:实现顺序表的基本运算。 - **相关知识**:介绍线性表的基本概念及操作,如初始化、销毁、判定是否为空表等。 - **具体操作**:详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法,并附有代码示例。 - **测试说明**:提供测试输入和预期输出,确保代码正确性。 - **通关代码**:给出完整的C++代码实现,帮助完成任务。 文档
40 5
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
49 2
|
8月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
8月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
8月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
76 2

热门文章

最新文章