黑马程序员技术交流社区

标题: LinkedList接口（在代码的使用过程中和ArrayList没有什么区别） [打印本页]

作者: 王--明 时间: 2011-12-14 18:51
标题: LinkedList接口（在代码的使用过程中和ArrayList没有什么区别）
LinkedList接口（在代码的使用过程中和ArrayList没有什么区别）

作者: 小春同学 时间: 2011-12-14 19:10
ArrayList底层是数组结构，LinkedList底层是数组结构，这两个结构之间的区别我想楼主已经知道，说其他的：
LinkedList不仅实现了List接口，还实现了Deque接口，Deque接口又是Queue（队列）接口的子接口，所以····可想而知：LinkedList能实现更强大的功能，只是我们暂时水平有限，用不到那么多，实际做开发的时候可能就不一样了，，，楼主可以查查API看看以上两个接口的方法，和LinkedList的特有方法，想想它的存在还是很有必要的。

作者: 马伟奇 时间: 2011-12-14 19:54
LinkedList类
　　LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。
　　注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：
　　　　List list = Collections.synchronizedList(new LinkedList(...));

ArrayList类
　　ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。
size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。
　　每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。
　　和LinkedList一样，ArrayList也是非同步的（unsynchronized）。

作者: 李振元 时间: 2011-12-14 20:07
个人觉得一楼的"LinkedList底层是数组结构"观点不是很正确。
1、通过观察LinkedList的源代码，我们可以看到：
private static class Entry {
　　Object element;
　　Entry next;
　　Entry previous;
}
这说明了LinkedList内部封装的是一个个的entry对象，和前一个以及后一个entry对象的引用。
每个entry对象对应LinkedList中的一个元素。

2、至于ArrayList,底层肯定是数组实现的，这个就不多说。

作者: 周敏2011nc 时间: 2011-12-20 13:45
基本的ArrayList ：它长于随机访问元素，在list的中间插入和移除元素时比较慢
linkedList ：通过代价较低List中间进行插入和删除操作，提供了优化的顺序访问。在随机访问方面相对比较慢。

作者: 冯瑞君老师 时间: 2011-12-20 13:53
两者区别：
1．对ArrayList和LinkedList而言，在列表末尾增加一个元素固定的。对 ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个是统一的，分配一个内部Entry对象。
2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的是固定的。
3．LinkedList不支持高效的随机元素访问

作者: 海中的游弋草 时间: 2011-12-20 13:56
ArrayList 底层采用数组实现，当使用不带参数的构造方法生成 ArrayList 对象时，实际上会在底层生成一个长度为 10 的Object 类型数组，当向 ArrayList 添加一个对象时，实际上就是将该对象放置到了 ArrayList 底层所维护的数组当中。LinkedList 底层采用双向链表实现，当向 LinkedList 中添加一个对象时，实际上 LinkedList 内部会生成一个Entry 对象，该 Entry对象的结构为：
Entry
{
  Entry previous;
  Object element;
  Entry next;
}
其中的 Object 类型的元素 element 就是我们向 LinkedList 中所添加的元素，然后 Entry又构造好了向前与向后的引用 previous、next，最后将生成的这个 Entry对象加入到了链表当中。换句话说，LinkedList中所维护的是一个个的 Entry对象。
  当执行插入或者删除操作时，采用LinkedList比较好。
  当执行搜索操作时，采用ArrayList 比较好。

作者: hello world 时间: 2011-12-20 20:10
ArrayList代表长度可变的数组。允许对元素进行快速的随机访问，但是向ArrayList中插入与删除元素的速度较慢。
LinkedList在现实中采用链表数据结构。对顺序访问进行了优化，向List中插入和删除元素的速度较快，但是访问速度则相对较慢。随机访问是指检索位于特定索引位置的元素。LinkedList可以作为堆栈、队列和双向队列来使用。

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

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