原文地址http://blog.csdn.net/QQ _ 25806863/article/details/70607204
数组链表是两种基本的数据结构，在内存存储中的表现形式不同，因此也有各自的特点。
大致总结一下特征和区别，以几个人去看电影时坐在座位上为例。
数组的特征在内存中，数组是连续的区域。 就上面的电影而言，这几个人必须在电影院坐在一起。 数组必须有空间，在使用之前必须申请内存大小，这可能会浪费内存空间。 例如看电影的时候，为了让10个人坐在一起，必须提前预约10个连续的位置。 这样的好处是可以保证10个人在一起。 但是，这样的缺点是，来的人少了10个人，剩下的位置就浪费了。 如果临时来了很多人，10个人就不够了。 这种情况下，需要移动位于第11人位置的人，或者11人重新寻找11连座的位置，效率可能会很低。 如果找不到符合要求的工作，就不能坐下。 插入和删除数据效率低下，插入数据时，此位置后面的数据将在内存中向后移动。 删除数据时，此数据后面的所有数据都必须向前移动。 例如，如果走了五个人，再走一个人坐第三个座位，就把座位从第三个移到第五个，把第三个座位留给新的人。 这个人走的时候，他们是相连的，所以他后面的几个人必须向前移动位置，填补这个空缺。 随机读取效率高。 因为数组是连续的，所以可以知道每个数据的内存地址，并且可以直接找到给定地址的数据。 而且不利于扩展，数组定义空间不够时必须重新定义数组。 链表的特点可以位于内存中的任何位置，不要求连续性。 在电影院任何人都可以自由坐。 每个数据都包含以下数据的内存地址，从该地址中找到以下数据： 第一个知道第二个座位号，第二个知道第三个座位号……增加和删除数据很容易。 另外，人来了可以随便坐。 例如，为了别人来了就成为第三个位置，他只要告诉第二个人自己的位置，让第二个人得到原来的第三个位置就可以了。 其他人不需要工作。 查找数据的时候效率很低。 因为没有随机性，所以访问某个位置的所有数据都是从第一个数据开始访问的，从第一个数据存储的下一个数据的地址中找到第二个数据。 要找到第三个人，必须从第一个开始问。 因为不指定大小，所以容易扩展。 即使不定义链表的大小，数据也会被随意添加和删除。 的优缺点每个数组的优点随机存取性高，检索速度快的数组的缺点插入和删除效率低，就需要无用的内存空间，可能需要足够的连续内存空间。 数组大小固定，不能动态扩展链表的优点是插入删除速度快，内存利用率高，内存大小不固定，扩展灵活。 链表的缺点不能随机查找，必须从头遍历，检索效率低——数组链表的读取o(1) o(1 )插入o(1 ) o(1)删除o(1 ) o )1)删除o(1) o )1)。