NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 5 题

线性表若采用链表存储结构，要求内存中可用存储单元地址（ ）。

这题就是考链表和数组最本质的区别——存不存得挨着。拿到题直接想：链表靠指针指下一个，那内存地址必须连续吗？当然不用，只要逻辑连上就行。

最容易把‘逻辑顺序’和‘物理地址’搞混，觉得链表也得挨着存。其实数组才死磕连续性，链表结点散落在哪儿都行，只要指针能串起来。还有人选‘一定不连续’，这也是错的，内存里完全可以有一块连续区域放链表，只是不强制而已。

考点概念：链表与数组的存储方式

数组和链表都是线性表，但底层实现天差地别。数组必须连续存储，因为它是靠下标直接算地址的，中间缺个地儿整个结构就崩了。链表呢？每个结点里除了存数据，还留着指针域，专门指下一个结头的地址。既然靠指针串起来，那内存地址连续不连续根本不重要，逻辑上连成一条线就行。

命题视角：为什么爱考这个点

命题人特别喜欢拿‘连续’这个词挖坑，尤其是把数组和链表放一起比。学生一看到‘线性表’就下意识想‘数组’，顺手选‘必须连续’，或者反过来觉得链表肯定不连续，直接选‘一定不连续’。其实这两者都太绝对了。链表地址连续不连续均可，连续时效率可能高点，不连续也没毛病，只要指针能指对就行。