数组和链表的区别

JAVA面试中经常会被问到集合,集合必说的就是List,List又会讲到两种实现:ArrayList,LinkedList,然后面试官又会问你区别,接下来告诉你怎么完美的装一波逼。

    最开始的时候,人们想的是分配一连串存储空间,每个空间大小一致,也就是说从第二个开始,每一个离上一个相差空间大小的偏移量,这样就形成了数组。数组需要提前分配好空间,如果需要扩充时原先的空间是不能使用的,需要分配更大的空间然后将数据转移。然后由于整个地址都是连续的,在中间插入或者删除中间元素时,为了空出位置或者是填补空缺,都需要对后面的元素进行移位操作,所以增删效率比较慢。但是查找的话,因为每个偏移量固定,每个地址其实都可以计算出来(首地址+(索引*偏移量)),其实这也是为什么java索引从0开始,get到技能点了么。

    慢慢的发现,一大串的空间是太浪费资源了,一些小块的资源完全利用不到,然后就出现了链表,需要的时候分配一块存储空间,然后将原来的链表尾部后继指向这块存储空间就好了。因为链表只是逻辑上的顺序,在内存中是独立的一小块一小块的内存,所以很多小块的资源可以合理的利用。因为链表是有指针指向下一个数据块,所以增加删除的时候只需要对地址指针的指向修改一下,效率比较快,但是查询的时候,需要从头部开始,一直到想要的数据,效率比较慢。

总结:

    array: 需要提前分配空间,且占用一连串空间,比较耗费资源。扩充比较麻烦,需要分配更大空间,然后复制数据。增删麻烦,需要移动元素,效率低,但是通过索引获取的话查询起来效率搞,时间复杂度为O(1)。

    link:需要数据块的时候才分配空间,每个数据块较小,可以合理利用内存资源。增删简单,但是查询需要从头部开始遍历,效率低下。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 重新回顾了下,总结如下: 1.数组查询快:数组要求是一块连续的内存空间来存储,这就要求在物理上这一片空间是连续的,...
    InitialX阅读 3,518评论 0 8
  • 数组和链表是两种基本的数据结构,他们在内存存储上的表现不一样,所以也有各自的特点。 大致总结一下特点和区别,拿几个...
    喵了个呜s阅读 3,787评论 0 1
  • 数组是将元素在内存中连续存放,从栈中分配空间,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如...
    奔跑的图腾阅读 335评论 0 1
  • 小学的时候,这个世界似乎就开始了勾心斗角,争强好胜。外表对人热情,内心对人谩骂。我不懂到底为什么人性被金钱磨灭了吗?
    释优阅读 194评论 1 0