java中链表结构元素的插入

java的LinkedList类提供了add(int index,E element)方法, 这个方法不需要从头开始数到index位置吗, 请问跟查找有什么区别, 为什么说LinkedList查找慢, 增删快呢? 谢谢!_

0

4个回答

LinkedList实际上是通过双向链表去实现的。既然是双向链表,那么它的顺序访问会非常高效,而随机访问效率比较低。
既然LinkedList是通过双向链表的,但是它也实现了List接口{也就是说,它实现了get(int location)、remove(int location)等“根据索引值来获取、删除节点的函数”}。LinkedList是如何实现List的这些接口的,如何将“双向链表和索引值联系起来的”?
实际原理非常简单,它就是通过一个计数索引值来实现的。例如,当我们调用get(int location)时,首先会比较“location”和“双向链表长度的1/2”;若前者大,则从链表头开始往后查找,直到location位置;否则,从链表末尾开始先前查找,直到location位置

1

查找是按照值找,索引是根据index找。
查找需要从头开始遍历直到找到。插入删除也需要查找,这里的快是和数组对比而言的,数组因为是连续存储,所以插入、删除需要把需要插入、删除的地方到结尾的元素全部拷贝一次。
甚至如果长度不足,还要重新分配内存。

0

您好,楼主,很高兴可以为您解答问题,在LinkedList集合中,您可以看一下它的底层,它的底层是由一个双向链表实现的,您说的add(int index,E element)这个方法,它的实现
原理是,取index与链表的长度的1/2相比较,如果大于1/2就从尾部遍历找您所要插入的位置,如果小于1/2,就从头部开始遍历查找您要插入的位置,linkedList的
get(index)的实现原理也是如此的,相比较于ArrayList,ArrayList中的每个元素都是有索引的,所以在查询的时候可以直接找到该元素的位置,所以LinkedList相
比较ArrayList查找慢, 但是ArrayList在添加时是从头开始遍历寻找要插入的索引位置,在这一点上LinkedList的添加更快一些

0

其实这个问题是跟数据结构有关系,数据结构中的线性表链表方式,就是这么一个特性。删除只需要一步修改指针指向。而查找读取节点的值,需要从头查找到节点。
LinkedList的add(int index,E element)方法,我觉得也是通过从头(或从尾,因为内部是双向链表,包含first,last两个指针)定位到那个index的位置去设置值的。
好吧,看看源码:

 public void add(int index, E element) {
        checkPositionIndex(index);//忽悠之

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

如果index等于size,表示直接在最后插入元素element,调用linkLast,根据last指针修改一下指向。
否则这里用了node去查找那个节点(就是这里有可能会慢),最后调用linkBefore去做指针修改。
完毕!!请采纳

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!