- 1、本文档共5页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
ArrayList 和 LinkedList 的区别
ArrayList 和 Vector 使用了数组的实现,可以认为 ArrayList 或者 Vector 封装了对内部数组的操作,比如向数组中添加,删除,插入新的元素或者数据的扩展和重定向。
LinkedList 使用了循环双向链表数据结构。与基于数组 ArrayList 相比,这是两种截然不同的实现技术,这也决定了它们将适用于完全不同的工作场景。
LinkedList 链表由一系列表项连接而成。一个表项总是包含3 个部分:元素内容,前驱表和后驱表,如图所示:
在下图展示了一个包含 3 个元素的 LinkedList 的各个表项间的连接关系。在 JDK 的实现中,无论 LikedList 是否为空,链表内部都有一 个 header 表项,它既表示链表的开始, 也表示链表的结尾。表项 header 的后驱表项便是链表中第一个元素,表项 header 的前驱表项便是链表中最 后一个元素。
下面以增加和删除元素为例比较 ArrayList 和 LinkedList 的不同之处:
增加元素到列表尾端:
在 ArrayList 中增加元素到队列尾端的代码如下: public boolean add(E e){
ensureCapacity(size+1);//确保内部数组有足够的空间elementData[size++]=e;//将元素加入到数组的末尾,完成添加return true;
}
ArrayList 中 add()方法的性能决定于 ensureCapacity()方法。ensureCapacity()的实现如下: public vod ensureCapacity(int minCapacity){
modCount++;
int oldCapacity=elementData.length;
if(minCapacityoldCapacity){ //如果数组容量不足,进行扩容Object[] oldData=elementData;
int newCapacity=(oldCapacity*3)/2+1; //扩容到原始容量的 1.5 倍if(newCapacittyminCapacity) //如果新容量小于最小需要的容量,则使用最小
//需要的容量大小newCapacity=minCapacity ; //进行扩容的数组复制elementData=Arrays.copyof(elementData,newCapacity);
}
}
可以看到,只要 ArrayList 的当前容量足够大, add()操作的效率非常高的。只有当ArrayList 对容量的需求超出当前数组大小时,才 需要进行扩容。扩容的过程中,会进行大量的数组复制操作。而数组复制时,最终将调用 System.arraycopy()方法,因此 add()操作的效率 还是相当高的。
LinkedList 的 add()操作实现如下,它也将任意元素增加到队列的尾端: public boolean add(E e){
addBefore(e,header);//将元素增加到 header 的前面return true;
}
其中 addBefore()的方法实现如下:
private EntryE addBefore(E e,EntryE entry){
EntryE newEntry = new EntryE(e,entry,entry.previous); newEntry.provious.next=newEntry; newEntry.next.previous=newEntry;
size++; modCount++; return newEntry;
}
可见,LinkeList 由于使用了链表的结构,因此不需要维护容量的大小。从这点上说, 它比 ArrayList 有一定的性能优势,然而,每次的元素增加都需要新建一个 Entry 对象,并进行更多的赋值操作。在频繁的系统调用中,对性能会产生一定的影响。
增加元素到列表任意位置
除了提供元素到List 的尾端,List 接口还提供了在任意位置插入元素的方法:void add(int index,E element);
由于实现的不同, ArrayList 和 LinkedList 在这个方法上存在一定的性能差异,由于ArrayList 是基于数组实现的,而数组是一块连续的内存空间,如果在数组的任意位置插入元素,必然导致在该位置后的所有元素需要重新排列,因此,其效率相对会比较低。
以下代码是 ArrayList 中的实现: public void add(int index,E element){
if(indexsize||index0)
throw
您可能关注的文档
- 2215200503计算机网络 蔡茂国 教学大纲.docx
- Ⅱ类申请医疗器械注册证申请流程.docx
- Ⅲ 社区开展创建文明家庭活动的情况说明报告 .docx
- a bit of的四种用法分析和总结.docx
- A class of oneindependent learning分析和总结分析和总结.docx
- a job worth doing教案新部编本.docx
- A Puppy for Poppy分析和总结分析和总结.docx
- A1包、班车租赁服务.docx
- a3 分销商销售代表—C店货车销售代表VSR 宝洁营销.docx
- A4试卷模板分析和总结.docx
- 2024年江西省寻乌县九上数学开学复习检测模拟试题【含答案】.doc
- 2024年江西省省宜春市袁州区数学九上开学学业水平测试模拟试题【含答案】.doc
- 《GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语》.pdf
- 中国国家标准 GB/T 44275.2-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第2部分:术语.pdf
- GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- 《GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构》.pdf
- 中国国家标准 GB/T 44285.1-2024卡及身份识别安全设备 通过移动设备进行身份管理的构件 第1部分:移动电子身份系统的通用系统架构.pdf
- GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 中国国家标准 GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南.pdf
- 《GB/T 44275.11-2024工业自动化系统与集成 开放技术字典及其在主数据中的应用 第11部分:术语制定指南》.pdf
文档评论(0)