map底层由数组和链表怎么理解链表分为双向和单向又怎么理解_百度知 ...

发布网友发布时间：2022-04-29 04:22

共2个回答

热心网友时间：2022-04-23 05:30

题主，准确来说map是一种高层映射，其底层实现是通过红黑树这种数据结构实现的，而再往下溯源会发现红黑树的数据结构是由链表构成的。因此题目所说底层由数组和链表构成其实跳过了中间红黑树的部分。
在C/C++中的链表是通过指针连接的。有些链表结构中只有指向下一个节点的指针，这个就叫单向链表，这种链表只能从前往后顺序访问而不能反向回溯。但一种特殊的链表，每个节点存储了两个指针，一个指向下一个节点，另一个指向上一个节点，这样就可以在访问过程中随意控制访问的顺序：可以顺序向后访问，也可以逆序向前访问。
形象理解：
单向链表：A->B->C
双向链表：A<=>B<=>C

热心网友时间：2022-04-23 06:48

这个是什么语言的什么类库中的map，通常来说map的实现有两种，一种是基于hasn算法，这个需要被存储的类型有一个hash函数（一般内置类型已经定义），另一种是基于排序的平衡二叉树（C++标准库的map使用该数据结构），而如果用二叉树的话就会涉及链式节点

map底层由数组和链表 怎么理解 链表分为双向和单向 又怎么理解_百度知 ...

map底层由数组和链表怎么理解链表分为双向和单向又怎么理解_百度知 ...