链表

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

链表的操作

插入元素：若要在元素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)前往下一位
}

单选题

1、链表不具备的特点是( )。

A.可随机访问任何一个元素

B.插入、删除操作不需要移动元素

C.无需事先估计存储空间大小

D.所需存储空间与存储元素个数成正比

2、线性表若采用链表存储结构，要求内存中可用存储单元地址( )。

A. 必须连续

B. 部分地址必须连续

C. 一定不连续

D. 连续不连续均可

3、链表不具有的特点是()

A.插入删除不需要移动元素

B.不必事先估计存储空间

C.所需空间与线性表长度成正比

D.可随机访问任一元素

4、链表不具有的特点是( )。

A. 可随机访问任一元素

B. 不必事先估计存储空间

C. 插入删除不需要移动元素

D. 所需空间与线性表长度成正比