黑马程序员技术交流社区

标题: 关于 LinkedList 的 问题 [打印本页]

---

作者: lucy198921    时间: 2013-4-4 15:48
标题: 关于 LinkedList 的 问题


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

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

---

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

---

作者: lcjasas    时间: 2013-4-4 16:03
元素存储方式
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的增删都只需要改变对应的指针就可以了。

---

作者: 郝勇    时间: 2013-4-4 16:09
LinkedList中增加了一个元素，两边的元素记住它了，那Linkedlist 中的其他元素角标不还是得重新移位吗？？   

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

---

作者: 朱盛文    时间: 2013-4-4 16:11
如图所示：
ArrayList底层数据结构是数组，每个元素都有自己的索引，所以通过索引进行查找就比较快，但是增删的话就会引起大部分的数据移位，所以比较慢。
而LinkedList底层数据结构是链表，每个元素本身有一个地址值，在它前面一个元素就是通过这个地址值找到它；它还有一个属于它本身的值，另外它还有一个是链接到下一个元素的地址值的值，通过这个元素它就可以找到下一个元素。在增删时，只需把链接的地址值进行修改即可。而查询时，是需要从头进行查找，通过每个元素所链接的地址值来获取下一个元素，所以就比较慢。

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

下载附件

2013-4-4 16:03 上传

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

---

作者: 黑马伍哲沂    时间: 2013-4-4 16:24
你的迷惑产生的原因是没有明白链表是一个什么样的结构。（数组的查找快增删慢好理解就不说了）

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

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

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

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

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

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

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

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

---

作者: 打工人    时间: 2013-4-4 16:26
若还有问题，继续追问； 没有的话，尽量及时将帖子分类改成【已解决】~

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2