JAVA面试中经常会被问到集合，集合必说的就是List，List又会讲到两种实现：ArrayList，LinkedList，然后面试官又会问你区别，接下来告诉你怎么完美的装一波逼。
最开始的时候，人们想的是分配一连串存储空间，每个空间大小一致，也就是说从第二个开始，每一个离上一个相差空间大小的偏移量，这样就形成了数组。数组需要提前分配好空间，如果需要扩充时原先的空间是不能使用的，需要分配更大的空间然后将数据转移。然后由于整个地址都是连续的，在中间插入或者删除中间元素时，为了空出位置或者是填补空缺，都需要对后面的元素进行移位操作，所以增删效率比较慢。但是查找的话，因为每个偏移量固定，每个地址其实都可以计算出来（首地址+（索引*偏移量）），其实这也是为什么java索引从0开始，get到技能点了么。
慢慢的发现，一大串的空间是太浪费资源了，一些小块的资源完全利用不到，然后就出现了链表，需要的时候分配一块存储空间，然后将原来的链表尾部后继指向这块存储空间就好了。因为链表只是逻辑上的顺序，在内存中是独立的一小块一小块的内存，所以很多小块的资源可以合理的利用。因为链表是有指针指向下一个数据块，所以增加删除的时候只需要对地址指针的指向修改一下，效率比较快，但是查询的时候，需要从头部开始，一直到想要的数据，效率比较慢。
总结：
array: 需要提前分配空间，且占用一连串空间，比较耗费资源。扩充比较麻烦，需要分配更大空间，然后复制数据。增删麻烦，需要移动元素，效率低，但是通过索引获取的话查询起来效率搞，时间复杂度为O（1）。
link：需要数据块的时候才分配空间，每个数据块较小，可以合理利用内存资源。增删简单，但是查询需要从头部开始遍历，效率低下。
网友评论