无任何技巧下直接暴力遍历数组链表_数据库

当前位置：网站建设 > 技术支持

资料来源：网络整理时间：2023/3/6 14:51:41 共计：3610 浏览

无任何技巧下直接暴力遍历数组链表？

首先搞清楚数组和链表的差异。

数组是在一整块连续的内存中存储数据，每一项数组成员大小相同。保存数组需要记录数组的起始地址、数组成员占用内存大小、数组长度；数组成员中记录了数据、类型。

下面用一个便于理解的方式举个关于数组的例子：

某数组起始位置在内存地址0上，每个数组成员占10byte，那么[0]在内存地址0，[2]在内存地址20，遍历数组的方式是根据数组起始位置+索引*数组成员大小。

链表是存储不需要一整块连续的内存，保存链表只要记录链表表头地址即可；每一项链表成员中保存了数据、数据类型、下一个成员的地址，另双向链表还会保存上一个成员的地址。

下面用一个便于理解的方式举个关于链表的例子：

某链表的表头在内存地址1000，访问它可获得数据和下一项数据地址是1234，遍历链表的方式是依次访问每一链的数据和下一链的地址，下一链的地址是直接获取，不需要计算。

再来说说题主的问题，为什么通常只是遍历那么链表性能略好一些，因为遍历链表时少做了一个加法和一个乘法运算。

那么实际上为啥链表总得很少数组用得很多呢？

原因主要有2条：

一、按索引随机访问成员时数组的效率比链表高很多。即顺序访问链表性能略高于数组，随机访问数组性能远高于链表。整体性能数组胜出。

二、使用数组时数组是连续存储，产生的内存碎片的几率和数量比链表少很多。

最后：所有的编程语言都支持数组，有相当多的编程语言不直接支持链表。因为链表的功能和数组的功能重叠，综合性能略差，而且使用链表要直接接触内存地址，容易产生内存地址越界、数据不安全的情况。

版权说明：
本网站凡注明“广州京杭原创”的皆为本站原创文章，如需转载请注明出处！
本网转载皆注明出处，遵循行业规范，如发现作品内容版权或其它问题的，请与我们联系处理！
欢迎扫描右侧微信二维码与我们联系。