程序世界的数据组织形式：数组和链表

数组是各种语言的基本数据类型，链表不是语言级类型，是基本类库提供的工具类。

数组Array和链表List是组织数据的两种方式，各种利弊，彼此互补。数组可以随机访问，但是不方便插入和删除数据，链表方便插入和删除，但是不能随机访问。

刚开始学习还在纳闷，难道没有两全其美的方案吗？但后来却不得不接受这个现实，这也许就像计划和市场一样，都不是完美的，市场经济也需要宏观调控，计划经济需要市场调节。

作为最基本的数据组织形式，其他的各种数据结构，比如栈，队列，集合，散列表等都是由其实现的，栈可以用数组实现，也可以用链表实现，队列可以用数组实现，也可以用链表实现，集合和散列表同时使用了数组和链表。

数组大小一经分配，将不可改变，所以需要提示预知数据量的多少。数组中的元素是连续的，所以必须要求元素是同种类型，否则没法定位。链表相对比较随意，只要将前后元素通过指针或引用关联起来即可。

直接使用数组有一些不便之处，鉴于此，很多语言中都提供了数组的封装类，比如C++的Vector，Java中的ArrayList，分别具有添加，删除，插入等功能，如果申请的空间全部占有了，则需要重新申请空间，这时候对性能是很大的考验，因此使用前最好估算出数组的大小。

开发中如何选择使用数组还是链表呢？这个需要看业务场景，是随机访问多呢？还是插入和删除多呢？这时候选择具有优势的一种数据结构。