链表和数组的对比

数组

  • 在内存中，数组是一块连续的区域；
  • 数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间；
  • 插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移；
  • 随机读取效率很高，因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据；
  • 不利于扩展，数组定义的空间不够时要重新定义数组。

链表

  • 在内存中可以存在任何地方，不要求连续；
  • 每一个数据都保存了下一个数据的内存地址，通过这个地址找到下一个数据。第一个人知道第二个人的座位号，第二个人知道第三个人的座位号……；
  • 增加数据和删除数据很容易。再来个人可以随便坐，比如来了个人要做到第三个位置，那他只需要把自己的位置告诉第二个人，然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动；
  • 查找数据时效率低。因为不具有随机访问性，所以访问某个位置的数据都要从第一个数据开始访问，然后根据第一个数据保存的下一个数据的地址找到第二个数据，以此类推。 要找到第三个人，必须从第一个人开始问起；
  • 不指定大小，扩展方便。链表大小不用定义，数据随意增删。