Dra*_*rgy 12
从理论的角度来看,一个单独链接的列表,包括头部和尾部.从前面卸下,贴在尾巴上.在那里你有理论上的O(1)恒定时间复杂度(即使对于最坏情况),存储量比双向链表更少.
从实际角度来看,基于阵列的可扩展连续结构可以使用循环索引更好地执行.由于空间局部性(例如,适合多个相邻元件的高速缓存行),硬件优于处理连续存储器.那些具有更差的算法复杂度,只有摊销的恒定时间和最坏情况的线性时间复杂度(虽然它很少见,通常无关紧要).
同样从实际的角度来看,展开的列表可以很好地工作(基本上存储在链接在一起的节点中的多个元素的数组,为您提供引用的局部性+保证的恒定时间入队和出队).
"最好"在这里很难说,因为它取决于你的需求.
例如,具有尾部的单链接列表具有每个节点的分配/解除分配开销和丢失的引用局部性的弱点,除非您使用有效的,连续的分配器来帮助缓解这些弱点.它还支付每个元素的列表指针/ ref的内存开销(由于每个节点的单独分配,可能还需要更多).正如评论中指出的那样,链接列表通常远没有它们听起来那么好,因为它们与硬件的实际性质不相符(至少没有来自分配器的大量帮助).
圆形阵列有一个弱点,它需要多余的容量来减少重新分配的数量(或者最坏情况下线性时间复杂度将更频繁地开始)和复制(尽管在某些情况下它们可能很浅).此外,因为它只是一个大的连续内存块,如果你正在处理大量数据集,即使在具有虚拟寻址的机器上也可能会出现内存错误(内存不足并不意味着所有内存都已用完)在这种情况下,这意味着找不到与请求的大小匹配的连续的未使用页面集合.
展开的列表减轻了列表指针和节点分配开销,但是在节点中存储了一些过剩的容量,如果你使用一个展开的列表,每个节点可以存储64个元素而你只是存储3个,这可能会非常浪费队列中的元素.
| 归档时间： |
|
| 查看次数： |
5519 次 |
| 最近记录： |