A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© lucy198921 中级黑马   /  2013-4-4 15:48  /  1657 人查看  /  6 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 lucy198921 于 2013-4-4 18:08 编辑

LinkedList和ArrayList相比优势是增删慢,查询慢,因为他的数据结构是每个元素和相邻的两个元素相连接的。

我不理解为什么它的增删会比ArrayList快
比如说;LinkedList中增加了一个元素,两边的元素记住它了,那Linkedlist 中的其他元素角标不还是得重新移位吗??
那效率也不高呀?

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

6 个回复

倒序浏览
arraylist中的数据在内存中是连续的,成 块的,查找的时候直接顺序遍历内存就可 以了。插入删除的时候,就要把修改的那 个节点之后的所有数据都向后移动,或者 向前移动。所以就慢了。
而linkedlist曾删的时候只是增加或者减少其链接,它不是数组集合

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
元素存储方式
ArrayList:采用数组方式
private transient Object[] elementData;

LinedList:采用链表
private transient Entry<E> header = new Entry<E>(null, null, null);
private static class Entry<E> {
        E element;
        Entry<E> next;
        Entry<E> previous;
        Entry(E element, Entry<E> next, Entry<E> previous) {
            this.element = element;
            this.next = next;
            this.previous = previous;
        }
}
ArrayList内部实现是数组,在每次增删的时候代价都很大,适合查找。
而LinkList内部实现是链表,对LinkList的增删都只需要改变对应的指针就可以了。

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
LinkedList中增加了一个元素,两边的元素记住它了,那Linkedlist 中的其他元素角标不还是得重新移位吗??   

其他两个元素的角标不会移动  本来数据时这样排列的 a b c       当你把b删除后,这时只是将a与后面了连接指向了c,而c与前面的连接指向了a  只是这两个数指向角标的值变化了。其他任何元素都不需要进行变换!

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
如图所示:
ArrayList底层数据结构是数组,每个元素都有自己的索引,所以通过索引进行查找就比较快,但是增删的话就会引起大部分的数据移位,所以比较慢。
而LinkedList底层数据结构是链表,每个元素本身有一个地址值,在它前面一个元素就是通过这个地址值找到它;它还有一个属于它本身的值,另外它还有一个是链接到下一个元素的地址值的值,通过这个元素它就可以找到下一个元素。在增删时,只需把链接的地址值进行修改即可。而查询时,是需要从头进行查找,通过每个元素所链接的地址值来获取下一个元素,所以就比较慢。

ArrayList和LinkedList底层数据结构的区别.jpg (91.8 KB, 下载次数: 21)

ArrayList和LinkedList底层数据结构的区别

ArrayList和LinkedList底层数据结构的区别

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
你的迷惑产生的原因是没有明白链表是一个什么样的结构。(数组的查找快增删慢好理解就不说了)

链表是由结点组成,每个结点有两部分,一部分含有指向数据对象的引用,叫数据部分。还有一部分含有指向链表中下一个结点的引用,叫链接部分。

也就是说,每一个结点(元素)都记住了它下一个结点的位置且有自己的位置并包含了一部分数据(即当前的元素内容)。

所以在增删某一个数据的时候,只要改变其两边(实际上最多改变两个引用就可以增删任何结点)结点的引用就可以。

链表不像数组一样,链表是没有角标的。第一个元素记住第二个,第二个元素记住第三个,以此类推。遍历LinkedList时,不像数组一样要按角标迭代,

它有自己的迭代方式,就是第一个问第二个,第二个问第三个,直到问到最后一个,最后一个没有指向,然后结束。实现这个迭代的代码如下:

for(int counter=1;counter<length;counter++)   //length代表结点个数
       firstNode = firstNode.next();  //next代表对下一个结点的引用(记住的下一个结点的位置)

所以链表增删不需要移动,而且是按需分配内存。ArrayList实际上是动态扩展数组来实现的,一初始化就是个长度10的数组,满了再加。
但是正是因为这种迭代方式,链表在查找除第一个以外的数据,都要对链表进行遍历。举个例子,最后一个元素只有倒数第二个元素知道它在哪
倒数第二个只有倒数第三个知道它在哪,链表有个表头是记住第一个元素在哪的。所以如果你想知道最后一个在哪,就i需要问表头,一直问到倒数第二个。

这样应该很清楚了吧。如果还有迷惑,有两种办法:有时间的话学习下数据结构,没时间的话先记结论,以后有时间再学。

回复 使用道具 举报
若还有问题,继续追问; 没有的话,尽量及时将帖子分类改成【已解决】~
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马