链表

链表的每个元素除了存放数据还存储了下一个元素的位置信息，从而使一系列随机存放的数据串在一起，其中的数据呈线性排列。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

链表的操作

插入元素：若要在元素Blue后面插入元素Green，只需要让Green指向Blue的后一个元素（Yellow），再让Blue指向Green即可；

删除元素：若要删除元素Yellow，只需让Yellow的前一个元素（Green）直接指向Yellow的后一个元素（Red）即可；

查询元素：若要在链表中查询数据为x的元素，需要从表头开始遍历查找（操作次数O(n)）。

数组模拟链表

//创建链表
for (int i = 0; i < n; i++) {
	cin >> num[i];
	nxt[i] = i + 1;					//每一位都指向下一位
}
nxt[n - 1] = -1;					//让最后一位指向并不存在的第-1位，代表数组结束
//找到数据为x的元素并删除
int now = 0;
while (nxt[now] != -1) {			//只要当前位(now)不是最后一位
	if (num[nxt[now]] == x) {		//如果当前位(now)的下一位对应的数值是x
		nxt[now] = nxt[nxt[now]];	//则将当前位(now)直接指向下一位的下一位
			break;					//找到并删除则结束遍历
	}
	now = nxt[now];					//让当前位(now)前往下一位
}