数组和链表的顺序遍历的时间比较

结论：数组顺序遍历快于链表

原因：CPU每次取数据时都不是只取一个数据，而是将那连续的一块一起取，而因为数组的地址空间是连续的，所以下几次要访问的元素也一起被放入缓存中了，减少了对内存的访问（访问速度：缓存 快于 内存）。

由于链表的元素是离散的放在内存中的，所以遍历每个元素的都需要对内存进行访问，导致顺序访问效率不如数组。

//采用vector<>和list<>来分别代表数组和链表
#include
typedef long long ll;
using namespace std;
const int maxn=1e5+5;

time_t timeForArray(int& cnt){
	vector<int> array(cnt,0);
	
	time_t start=clock();//计算时间，end-start=遍历时间 ，单位毫秒(ms) 
	for(int i=0;i<cnt;i++)	array[i]=1;
	time_t end=clock();
	
	return end-start;
}

time_t timeForList(int& cnt){
	list<int> List(cnt,0);
	
	auto iter=List.begin();
	time_t start=clock();
	while(iter!=List.end())	*iter=1,iter++;
	time_t end=clock();
	
	return end-start;
}

int main(){
	ios::sync_with_stdio(0);
	
	int cnt;
	cin>>cnt;//10000000
	cout<<"Array:"<<timeForArray(cnt)<<endl;//Array:78、31、47 
	cout<<"List:"<<timeForList(cnt)<<endl;//List:164、151、152 
	
	return 0;
}