最近总是听说各类说法，例如数组的速度比指针快，或是指针的速度比数组快。事实上，这两种的速度是基本一致的。

关于链表的两种实现方式，经过测试，平均运行时间都在0.17s左右
刚才测得的一些数据：

• 链表 指针版
  0.1932
  0.1551
  0.1618
  0.1598
  0.2269
  平均0.1793
• 链表 数组版
  0.1513
  0.1901
  0.1651
  0.1615
  0.1852
  平均0.1706

实验数据存在误差，可以认定，数组和指针的运行时间基本相同。
至于其内部原理，我想说，数组本质就是指针，不理解的可以看看我之前写过的文章，即：

p[i]=*(p+i)

使用数组的lst[p].next，寻址的时候需要使用一次指针，而p->next也是一次指针，效率相同。

最后附上测试代码：
指针版

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct List{
	int val;
	struct List *next;
	List(){
		val=0;next=NULL;
	}
};
struct List *head;
void insert(){
	struct List *p=head;
	while(p->next!=NULL)p=p->next;
	p->next=new List;
}
int main(){
	head=new List;
	for(int i=1;i<=N;i++)insert();
	return 0;
}

数组版

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct List{
	int val;
	int next;
}lst[2*N];
int idx=1;
int head=1;
void insert(){
	int p=head;
	while(lst[p].next!=0)p=lst[p].next;
	lst[p].next=++idx;
	lst[idx].val=0;lst[idx].next=0;
}
int main(){
	lst[head].val=0;
	lst[head].next=0;
	for(int i=1;i<=N;i++)insert();
	return 0;
}