黑马程序员技术交流社区

标题: 【暂解决】List中的LinkedList的问题 [打印本页]

---

作者: 黄玉昆    时间: 2013-2-20 22:58
标题: 【暂解决】List中的LinkedList的问题


今天刚看我Vector枚举的前一部分，对LinkedList产生了疑问。
毕老师说List的特点是有序的，元素可重复的，是因为该集合体系有索引，简单来说，索引就是所谓的角标。
那么对于LinkedList，也是隶属于List体系的，对吧？那为什么它没有索引呢？而只是作为一种增删快速，查询缓慢的链表呢？
那对于LinkedList和ArrayList，各有千秋，在开发中如何选择使用呢？或者说哪种方式更合适，更大众呢？更专业呢？

---

作者: 寇弘禄    时间: 2013-2-20 23:04
记得毕老师说过实在选不出来用哪个就用ArrayList

---

作者: 柴乔军    时间: 2013-2-20 23:28
LinkedList没有索引？？？？？？{:soso_e103:}

---

作者: 江华    时间: 2013-2-20 23:47
很想回答，困了，睡觉

---

作者: 贾文泽    时间: 2013-2-21 00:01
ArrayList    底层使用数组数据结构，查询很快，增删很麻烦，线程不同步，JDK1.2出现。默认长度为10，为可变长度数组，超过10时，50%延长，原来的copy到新数组中来，再添加数据
LinkedList  底层使用链表数据结构，查询很慢，增删容易，线程不同步，
               特有方法：addFirst();  //在头部添加，打印会反向          addLast();    //在尾部添加，打印会正向
                              getFirst();     getLast();    //获取不删除       removeFirst();     removeLast();    //获取删除
                              在JDK1.6中分别被代替：  offerFirst();    offerLast();    peekFirst();    peekLast();     poolFirst();     poolLast();
Vector     底层使用数组数据结构，线程同步，默认长度为10，超过10时，100%延长，JDK1.0中出现，当时没有集合框架，增删查都慢，后被  ArrayList 取代，
              枚举是Vector特有的取出方式，后因为枚举的名称和方法名都过长，所以被迭代器取代

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。所以LinkedList是没有索引的。。。

---

作者: 冯佩    时间: 2013-2-21 02:22
public class LinkedListDemo {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                LinkedList link = new LinkedList();
                link.offerFirst("ting01");
                link.offerFirst("ting02");
                link.offerFirst("ting03");
                link.offerFirst("ting04");
                link.add("ting05");
                link.add("love");
               
                System.out.println(link.get(5));
        }
}
谁说链表结构就不能有索引呢，看代码演示，LinkedList是有索引的，再则说，LinkedList继承的父类中有很多带索引的方法，如果LinkedList不能调用这些有索引的方法的话，恐怕也不太合适吧。ArrayList底层使用的是数组结构，查询快，增删慢。LinkedList底层使用的是链表数据结构。查询慢，增删快。如果需要查询快些就用ArrayList，想要增删快些就用LinkedList,如果想创建堆栈或队列数结构时也最好用LinkedList,如果不知道该用哪个时，就直接用ArrayList.

---

作者: 黄玉昆    时间: 2013-2-21 16:30

张熙韬 发表于 2013-2-20 23:45
这是ArrayList的代码片段。通过代码发现，当你new一个ArrayList的时候，它首先初始化了一个数组！那么理所 ...

童鞋，有点答非所问了:L ，不过还是感谢你这么细心的解答。

---

作者: 黄玉昆    时间: 2013-2-21 16:31

江华 发表于 2013-2-20 23:47
很想回答，困了，睡觉

休息才最重要，不过，期待你的解答啊

---

作者: 黄玉昆    时间: 2013-2-21 16:32

贾文泽 发表于 2013-2-21 00:01
ArrayList    底层使用数组数据结构，查询很快，增删很麻烦，线程不同步，JDK1.2出现。默认长度为10，为可 ...

似乎有些道理，谢谢

---

作者: 黄玉昆    时间: 2013-2-21 16:41

冯佩 发表于 2013-2-21 02:22
public class LinkedListDemo {

        public static void main(String[] args) {

很想问一下，如果链表有索引，那为什么不通过索引查找，或者说通过索引查找更快，为什么链表的查询速度还会那么慢呢？还有，你应该用的是eclipse吧，测试了一下，发现找不到LinkedList，才明白，没导入包。

---

作者: 冯佩    时间: 2013-2-21 18:50
是的，用的是eclipse,在LinkedList集合中可以通过get(int index)方法根据索引来获取元素，这说明索引是存在的，索引只是标记，具体查询的方式是由数据结构来决定的，举个例子来说:甲和乙要从一个地方到另一个地方去，都知道要去的那个地方名，但是甲走的是一条直线路，乙却只能走另一条曲线路，甲肯定是先到。那个地方名就如同索引，甲和乙分别如同ArrayList和LinkedList，直线路和曲线路分别对应数组结构和链表结构。这是我的理解，关于LinkedList的索引问题，我看的一些资料也未见有具体说明，如果你看到一些资料有明确说明和解释的话，请分享一下，我期待和你更多的交流。

---

作者: 黄玉昆    时间: 2013-2-21 20:37

冯佩 发表于 2013-2-21 18:50
是的，用的是eclipse,在LinkedList集合中可以通过get(int index)方法根据索引来获取元素，这说明索引是存在 ...

其实，我是理解LinkedList底层使用的是链表数据结构的，只是不太理解的是为何有索引而不使用索引，或者具体是怎么实现这个链表的还不太明白，如果我看到相关资料，一定会分享给大家的。谢谢你。问题基本就是这个了，其他的明白了。

---

作者: Rancho_Gump    时间: 2013-2-21 20:51


list集合的共性就是元素可重复，有索引。

QQ截图20130221211214.jpg (11.87 KB, 下载次数: 47)

下载附件

2013-2-21 21:12 上传

---

作者: Rancho_Gump    时间: 2013-2-21 21:25
我的理解： 链表结构中，每个元素包含比数组结构更多的信息，所以读取速度会比数组结构稍慢。
数组结构在增删是，要依次操作被修改元素之后的所有元素。
而链表结构不需要，只要修改元素的前置地址和后置地址就可以了。

---

作者: Rancho_Gump    时间: 2013-2-21 21:30

黄玉昆 发表于 2013-2-21 20:37
其实，我是理解LinkedList底层使用的是链表数据结构的，只是不太理解的是为何有索引而不使用索引，或者具 ...

按我的理解调用get(int index)方法的话就是使用索引找，只不过链表结构要复杂与数组结构，所以速度要稍慢

---

作者: 黄玉昆    时间: 2013-2-21 21:40

张向辉 发表于 2013-2-21 21:30
按我的理解调用get(int index)方法的话就是使用索引找，只不过链表结构要复杂与数组结构，所以速度要稍慢 ...

那是不是可以理解为，由于链表结构的复杂性，限制了它的索引查询，因此，虽然可以使用索引查相应的数据，但是对于这种操作却和数组的查询方式不同，从而导致查询速度的变慢？

---

作者: 黄玉昆    时间: 2013-2-21 21:47

张向辉 发表于 2013-2-21 21:25
我的理解： 链表结构中，每个元素包含比数组结构更多的信息，所以读取速度会比数组结构稍慢。
数组结构在增 ...

就你上面的图中所表示的索引来说，既然对其进行了修改，位置（索引）也要跟着改变，那么，位置应该是以某种方式对应着的，这种方式应该和数组的对应方式是不一样的。那么，可不可能，这个索引是动态绑定的呢？

---

作者: Rancho_Gump    时间: 2013-2-21 21:47

黄玉昆 发表于 2013-2-21 21:40
那是不是可以理解为，由于链表结构的复杂性，限制了它的索引查询，因此，虽然可以使用索引查相应的数据， ...

如果知道了一个值，查询他在链表中的索引位的话，是比较麻烦的  等下我整理下思路 今天有点蒙 :lol

---

作者: 黄玉昆    时间: 2013-2-21 21:53

冯佩 发表于 2013-2-21 02:22
public class LinkedListDemo {

        public static void main(String[] args) {

我想了想，LinkedList有这种查询是必然的，因为List中定义的是那些抽取出的共性方法，那么它的子类必然可以使用它的方法了。但子类就相对灵活多了，为了实现子类的特有结构，必然会改变一些共性的东西，或许LinkedList的索引方式就已经改变的和List大相径庭了呢。所以，虽然我不知道这种方式是怎么实现的，但是一定要比数组的索引复杂，我觉得你这样是不能说明实质问题的。

---

作者: 黄玉昆    时间: 2013-2-21 21:57

张向辉 发表于 2013-2-21 21:47
如果知道了一个值，查询他在链表中的索引位的话，是比较麻烦的  等下我整理下思路 今天有点蒙  ...

按你这么一说，我想起来了，毕老师说链表查询的慢应该在于：通过数据查索引很慢，因为是链表，要从头一个一个问询，是不是存在要查的值，如果这个值是在最后，那么要遍历前面所有的数据，所以就慢了。但是是不是通过索引查数据，会不会就不一样了呢？有待研究啊。谢谢张版主啊，让我拨开了第一层迷雾。嘿嘿:D

---

作者: Rancho_Gump    时间: 2013-2-21 21:58
get方法的速度应该差不多，indexOf(Object o) 方法就差多了
数组的底层算法很多 比如二分查找等  链表的查找方法除了根据前置或后置地址连接查找，其他的还没研究过，不是很清楚。

---

作者: 朱玉玺    时间: 2013-2-21 22:19


LinkedList是有索引的哦。就像老毕说的，每一种容器，它针对的都是特殊的存储方式，或者说数据结构。每一种数据结构都是对某一类问题解决比较有效，同时又有局限性。Collection选择那个子类，你可以这样来：
是否允许重复元素？
允许---List
                  如果查询频繁，则选择ArrayList；如果是增删操作频繁，则选择LinkedList。不同，增删频繁的情况很少见，一般都是查询频繁，所以在实在搞不清楚的时候，ArrayList是首先。
不允许--Set
   Set中的元素是否需要排序？不需要选择HashSet，需要就选择TreeSet。
实际开发中，我们可能要对这些容器进行再次封装，已使其与实际项目的关系更为紧密。
     

---

作者: 冯佩    时间: 2013-2-22 07:56
关于LinkedList索引的讨论起来越有点意思了，LinkedList是List体系中的成员，而且又能使用带索引的方法，所以它有索引这是肯定的，相对于数组结构的根据索引查找值的get(int index)方法来说，链表结构更像是查找到索引以后再取值，链表结构每次都要从前往后去核对每一个值是不是要找的值，直到找到为止，这种查找方式是由它的结构决定的，所以与它的索引没多大关系，需要明确的一点就是：有索引未必会按索引去查找，查找的方式取决于数据结构。

---

作者: 黄玉昆    时间: 2013-2-22 07:59

朱玉玺 发表于 2013-2-21 22:19
LinkedList是有索引的哦。就像老毕说的，每一种容器，它针对的都是特殊的存储方式，或者说数据结构。每一种 ...

回得很好，不错，谢谢

---

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

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