黑马程序员技术交流社区

标题: 关于linkedlist数据结构的问题 [打印本页]

作者: 魏亮 时间: 2012-9-18 15:20
标题: 关于linkedlist数据结构的问题
本帖最后由魏亮于 2012-9-19 09:51 编辑

毕老师上课讲 LinkedList和ArrayList相比优势是增删慢，查询慢，因为他的数据结构是每个元素和相邻的两个元素相连接的。
我不理解为什么它的增删会比ArrayList快
比如说；LinkedList中增加了一个元素，两边的元素记住它了，那Linkedlist 中的其他元素角标不还是得重新移位吗？？
那效率也不高呀？求指教

作者: 汪小照 时间: 2012-9-18 15:37
ArrayList底层数据结构是数组结构的。查询只需要知道角标，而增删，需要移动元素，这就涉及到了数据结构这门课程的时间复杂度了。你可以找一本数据结构的书看一下，数组和链表之间的区别。
而linkedList底层数据结构是链表数据结构的，查询需要从表头查到所需要的运算（比数组只需要知道角标要慢），数据结构中有说链表查询时的时间复杂度。删除的话只需要移动相邻的两个元素（比数组移动整个元素要快）。

作者: 彭润生 时间: 2012-9-18 15:41
楼上说的对，链表修改只需要把前后的链接修改一下就可以了，数组就不一样了。链表查询要从头到尾。一个一个的。数组可以通过下标来确定

作者: 程金 时间: 2012-9-18 15:45
本帖最后由程金于 2012-9-18 16:34 编辑

在LinkedList中有一个私有的内部类
private static class Entry {
         Object element;
         Entry next;
         Entry previous;
      }
LinkedList中每个对象都有一个相对应的Entry对象，每个entry对象都对应于列表中的一个元素,记录元素的前后位置信息
当你在linkedList中插入时(删除同理)
比如第n个位置后面插入一个对象时,只要将"n位置的对象中的next变量"和"n+1位置的对象中的previous变量都改为要插入的对象的引用,当然要添加一条entry信息保存新加入对象的前后信息
当你在arraylist中插入时(删除同理)
比如在n位置后面插入,那么n后面所有值都要向后移动,然后插入对象,所以慢

这么说吧,在linkedlist中插入一个对象,只是插入一条entry对象相关信息,删除个对象,只是修改这个对象前后两个对象中的entry相关信息

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

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