本文共 2403 字,大约阅读时间需要 8 分钟。
线程安全
:ArrayList和LinkedList都是不同步的,都是线程不安全的底层数据结构
:ArrayList底层是使用数组来实现的,LinkedList底层是使用双向链表来实现的在随机访问时
:ArrayList支持快速随机访问,借助下标进行访问;而LinkedList不行扩容机制
:LinkedList底层是双向链表,没有初始化大小,也没有扩容机制;ArrayList初始化如果不指定大小,初始大小为10;在使用add方法的时候,首先会调用ensureCapacityInternal方法,传入size+1检查是否需要扩容,newCapacity = 扩充数组为原来的1.5倍;ArrayList中copy数组的核心就是System.arraycopy方法。内存空间占用
:ArrayList的空间浪费主要体现在List结尾需要预留一部分空间,而LinkedList的空间浪费则体现在它的每一个元素都要消耗比ArrayList更多的空间(存放数据和下一个节点的引用)顺序表存储位置是连续的、支持随机访问,链表可以是不连续的、不能随机访问,只能从头到尾逐个搜索。
下面这张图总结的很好~时间性能 :查找 O(1) ,插入和删除O(n)。
时间性能 :查找 O(n) ,插入和删除O(1)。
①在内存中,数组是一块连续的区域。
拿上面的看电影来说,这几个人在电影院必须坐在一起。
数组需要预留空间,在使用前要先申请占内存的大小,可能会浪费内存空间。
比如看电影时,为了保证10个人能坐在一起,必须提前订好10个连续的位置。这样的好处就是能保证10个人可以在一起。但是这样的缺点是,如果来的人不够10个,那么剩下的位置就浪费了。如果临时有多来了个人,那么10个就不够用了,这时可能需要将第11个位置上的人挪走,或者是他们11个人重新去找一个11连坐的位置,效率都很低。如果没有找到符合要求的作为,那么就没法坐了。 ③插入数据和删除数据效率低
,插入数据时,这个位置后面的数据在内存中都要向后移。删除数据时,这个数据后面的数据都要往前移动。 比如原来去了5个人,然后后来又去了一个人要坐在第三个位置上,那么第三个到第五个都要往后移动一个位子,将第三个位置留给新来的人。 当这个人走了的时候,因为他们要连在一起的,所以他后面几个人要往前移动一个位置,把这个空位补上。 ④随机读取效率很高
。因为数组是连续的,知道每一个数据的内存地址,可以直接找到给地址的数据。并且不利于扩展,数组定义的空间不够时要重新定义数组。 在内存中可以存在任何地方,不要求连续
。 在电影院几个人可以随便坐。 ②每一个数据都保存了下一个数据的内存地址,通过这个地址找到下一个数据
。 第一个人知道第二个人的座位号,第二个人知道第三个人的座位号…… ③增加数据和删除数据很容易
。 再来个人可以随便坐,比如来了个人要做到第三个位置,那他只需要把自己的位置告诉第二个人,然后问第二个人拿到原来第三个人的位置就行了。其他人都不用动。 ④查找数据时效率低,因为不具有随机访问性
,所以访问某个位置的数据都要从第一个数据开始访问,然后根据第一个数据保存的下一个数据的地址找到第二个数据,以此类推。 要找到第三个人,必须从第一个人开始问起。 ⑤不指定大小,扩展方便
。链表大小不用定义,数据随意增删。转载地址:http://zlanz.baihongyu.com/