关于数组下标访问和链表指针访问的原理和效率,该怎么处理

关于数组下标访问和链表指针访问的原理和效率
对于一个数组a[] 我们想要访问某个元素并且知道这个元素的下标
对于一个双向链表 我们知道一个节点的地址(指针p)

如果想要访问 a[x]和*p那个效率更高？

再比如我要遍历一个数组a[]和一个链表 在每次访问下一个元素的时候 数组是从a这个地址开始 每次都计算a+i*size(element)来找到每个地址吗？
这样说来和链表通过后继的指针找到下一个节点相比 哪一个更快呢？

我脑子笨 真心希望大神指点！
------解决方案--------------------
顺序遍历且只遍历一次整个容器的话，数组和链表效率相同
随机遍历的话，要获取数组任何一个位置都只需要做一次乘法和对指针取值操作就可以，而链表——你要获取第几个位置就必须做几次对指针取值，效率哪个更高还用说？
------解决方案--------------------
顺序访问地址的速度快。所以遍历数组的速度要快于链表
------解决方案--------------------

引用:

顺序遍历且只遍历一次整个容器的话，数组和链表效率相同
随机遍历的话，要获取数组任何一个位置都只需要做一次乘法和对指针取值操作就可以，而链表——你要获取第几个位置就必须做几次对指针取值，效率哪个更高还用说？

++
这个顺序遍历且只遍历一次整个容器的话，数组和链表效率相同
是从时间复杂度考虑的。

引用:

顺序访问地址的速度快。所以遍历数组的速度要快于链表

++
数组略快一点，主要是顺序访问，只需要指针加一就行了（地址移动一个元素位置），寄存器加法
链表需要查表操作，需要两次访问内存
这是从具体执行效率考虑的。

 


------解决方案--------------------

引用:

Quote: 引用:

顺序遍历且只遍历一次整个容器的话，数组和链表效率相同
随机遍历的话，要获取数组任何一个位置都只需要做一次乘法和对指针取值操作就可以，而链表——你要获取第几个位置就必须做几次对指针取值，效率哪个更高还用说？

++
这个顺序遍历且只遍历一次整个容器的话，数组和链表效率相同
是从时间复杂度考虑的。

引用:

顺序访问地址的速度快。所以遍历数组的速度要快于链表

++
数组略快一点，主要是顺序访问，只需要指针加一就行了（地址移动一个元素位置），寄存器加法
链表需要查表操作，需要两次访问内存
这是从具体执行效率考虑的。

按照时间复杂度确实是一样的
但实际上速度可能差异很大，涉及到高速缓存命中率。
------解决方案--------------------
因为楼主使用数组用的是a[i]这种方式，所以数组的指针递增这个寄存器加法没有用武之地，所以说二者基本是同效率的
至于编译器优化和缓存命中率等等，这些都不是编程语言范围内的事情吧
------解决方案--------------------

引用:

因为楼主使用数组用的是a[i]这种方式，所以数组的指针递增这个寄存器加法没有用武之地，所以说二者基本是同效率的

至于编译器优化和缓存命中率等等，这些都不是编程语言范围内的事情吧

这些都不是，或者可以不是，但是也可以是！

如果，没有编译优化，尤其是C++STL，那是很低效的。

有了Java，C#,各种动态语言，为何还要用 C,C++
因为需要高效率，其中编译优化，就是高效率的一个来源。
C,C++ 为此还专门定义了一个关键字 volatile，用于防止过度优化。 

------解决方案--------------------
一般而言 指针访问比数组下标访问效率要高