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问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
链表中插入链表
问题:在里面的注释里rn[code=Java]rnpublic class Node rnrn private int data;rn private Node next;rnrn public Node(int data) rn this.data = data;rn this.next = null;rn rnrn public void setData(int data) rn this.data = data;rn rnrn public int getData() rn return data;rn rnrn public Node getNext() rn return next;rn rnrn public void setNext(Node next) rn this.next = next;rn rn rnrn[/code]rn[code=Java]rnpublic class LinkList rnrn Node head;rnrn public LinkList() rn head = null;rn rn rnrnrn[/code]rn[code=Java]rn//实现将输入的数组转化成单链表,并将其插入到给出的单链表的指定位置rn public static LinkList linkInsert_L(LinkList l, int idx, int[] arrs)rn int count=0;rn Node tail=null;rn //将数组转换成链表rn LinkList head = new LinkList();rn for(int i=0;i=lc)rn Node ltail=l.head;rn for(int i=1;i
结构元素
国内首套将HTML与CSS整合,以应用场景划分课程模块的前端入门课程。近两百个视频课程,上百张制作精美的PPT,几十张课程内容分析图,以及课程代码等资料。让你全面、系统地学习HTML与CSS制作静态网站技能。
在链表中插入和删除结点
#include #include #define N 5 typedef struct node { int data; struct node *next; }sn; sn *createlist(int a[]) { sn *h; sn *p,*q; int i; q=(sn *)malloc(sizeof(sn)); h=q; for(i=0;i { p=
Java 实现链表的插入,遍历
PS本文基于节点类中午getter/setter方法的实现,下篇文档介绍有getter/setter的实现。 实现原理基本相同。链表节点类public class ListNode { int val;//数据 ListNode next;//指针 ListNode(int val) { this.val = val; this.next =
Java 版本的单项链表插入
前言:今天去一家公司去面试,聊了一会然后让我手写一段单项链表的插入,其实题目很简单。可是自己把自己绕到递归中去了。然后我就呵呵了。 晚上下班回家,自己又重新整理了一下思路,写了一下代码。 import java.util.Random; /** * 单项列表插入的测试类 * @date 2016-09-18 * @author Henry * */ public class YK
链表之链表的结点插入
师–链表的结点插入 Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Problem Description 给出一个只有头指针的链表和 n 次操作,每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。 Input 多组输入。每组数据首先输入一个整数n(n∈[1...
HTML5的结构元素
链表的插入
链表的插入,通过对链表的遍历查询来进行堆链表插入。
链表插入
看算法第四版看的头大,换了本啊哈算法看,觉得更好接受一些,不过这书的确有些缺点,不够严谨。 #include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; struct node { int data; struct node *next; }; int...
链表中结点的插入和删除
该课程为“C语言及程序设计”系列课程中的第三部“进阶篇”。作为终结篇C语言教程,介绍了在实际应用中应用广泛的结构体数据表示和处理、利用文件进行输入输出、利用多文件组织项目开发,并结合对程序设计的进一步学习需求,概述数据结构及其选择问题和问题求解方法。以实践为主线的学习将继续,“银行储蓄系统”的开发将会迭代到第5版和第6版。
c++中链表插入问题
一个单链表,要求在值为“jone”的结点前插入值为“marit”的结点,若没有值为“jone”的结点,则插在链表最后。请帮我看下下面的程序:当有jone这个结点时,程序可以输出正确结果,没有jone结点,要插入在链表末尾时,程序跳到调试状态了,是什么原因?rn#include rn#include rnstruct Nodernrn char a[20];rn Node* next;rn;rnvoid insert(Node* head);rnvoid main()rnrn Node* head;rn Node* x1=new Node;rn strcpy(x1->a,"hello");rn head=x1;rn x1->next=NULL;rn Node* x2=new Node;rn strcpy(x2->a,"jone");rn x1->next=x2;rn x2->next=NULL;rn Node* x3=new Node;rn strcpy(x3->a,"good");rn x2->next=x3;rn x3->next=NULL;rn Node* x4=new Node;rn strcpy(x4->a,"better");rn x3->next=x4;rn x4->next=NULL;rn cout<<"插入之前"<next)rn rn cout<a<<"->";rn rn cout<<'0'<next)rn rn cout<a<<"->";rn rn cout<<'0'<a,"marit");rn Node* p1=head;rn while(strcmp(p1->next->a,"jone")!=0 && p1->next)rn rn p1=p1->next;rn rn if(p1->next==NULL)rn rn p1->next=p;rn p->next=NULL;rn rn elsern rn p->next=p1->next;rn p1->next=p;rn rnrn
线性结构元素
matlab线性结构体子程序。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
HTML5新增的主体结构元素和非主体结构元素
记录自己学习的点点滴滴。—-前(潜)行 主体元素 1、article元素 article元素代表文档、页面或应用程序中独立的、完整的、可以独自被外部引用的内容。他可以说以一篇博客或者报刊中的文章,一篇论坛帖子、一段用户评论或独立的插件,或其他任何独立的内容。 article元素是可以嵌套使用的。 article元素可以用来表示插件。
HTML结构元素
一个网页文档可以展现出各种不同的元素。而能够将元素组织起来并显示在正确位置的原因是,每个元素在网页文档中都有它所对应的角色,这些角色都可以通过一定的规范组织起来,而这些规范就是由HTML中的结构元素确定的。结构元素用来描述内容的表现意图,也用于组织文件的内容和指导文件的输出格式。结构元素并没有指示浏览器的显示方式,但是在一般情况下,大多数浏览器都标准化了这些结构元素的显示方式和内容。 base ...
结构元素的使用
会使用html5和css3完成前端开发任务
理解结构元素
全面系统的学习MATLAB在图像处理中的应用
算法数据结构笔记 链表,栈链表,链表中插入
链表 链表通过一个结构体或类,比如: class node //指针结构体 { public: next* next; int data; }; 第一个结构体的子元素,指向下一个结构体,下一个结构体再指向下下一个结构体.....这样反反复复,即构成链表。 了解链表之前,先看看怎么创造一块空间: q = (next*)malloc(sizeof(next)); //创造一块新...
链表——师--链表的结点插入
师–链表的结点插入 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 给出一个只有头指针的链表和 n 次操作,每次操作为在链表的第 m 个元素后面插入一个新元素x。若m 大于链表的元素总数则将x放在链表的最后。 Input 多组输入。每组数据首先输入一个整数n(n∈[1,100]),代表有n次操作。 接下来的...
链表的认识及链表元素的插入
链表的定义: 链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。 因为链表不用必须按顺序进行存储,因此可以对链表进行增、删、改、查等操作,下面先介绍链表的几个插入的例子: 1.链表的插入: 链表的插入可以分为头插和尾插和按位置插入,顾名思义就是从头插入元素和从尾部插入元素还有从...
HTML5结构元素
article元素 article元素“在文档,页面,应用或是站点上的一个独立部分,并且大体上,是可独立分配,或是重复使用的,例如在发布时。这个可以是论坛帖子,杂志或是新闻,博客条目,用户提交的评论,互动的小工具或小工具,或任何其他独立项目的内容。”article>元素专用于结构化文章,总的来说,article用于发表文章,代码如下: 标题党 小标题 div class="p
链表的头插入和尾插入
分2个子函数描述了链表的头插入和尾插入,通过条件编译来控制选择具体算法。
删去链表中的元素,然后插入另一个链表中
对一个数据为数值的单链表,将表中元素大于5的值输出,并从原单链表中摘除后,插入到一个新的单链表中。这题怎么做?
java 链表的操作(查找,插入,删除,反转)
节点的定义 public class ListNode { int val; //链表的元素值 ListNode next; //下一个节点的位置 ListNode(int x) { val = x; } } 链表的查找操作 //按值查找 public ListNode ListFind(int x,ListNo...
Java实现链表的插入,删除,排序,输出
//链表的数据结构: package test;  class Node {      Node next=null;      int data;      public Node(int data){     this.data=data;      } } //链表操作 的实现: package test; import com.oj.Main1;
链表的建立、插入、删除操作的JAVA实现
链表的JAVA实现 链表的建立、插入、删除操作
Java实现单链表的插入、删除、计算链表的长度和输出链表
首先定义单链表(以下统称为链表):链表有两部分:数据和指向下一个节点的指针。这里引用书中的一张图片:一般是知道头指针,然后根据头指针做插入、删除、反转、排序、输出等操作。使用Java实现链表的结构如下:/** * 链表的结构 * @author haoge */ public class Node { //链表节点的数据 int data; //链表指向的下一个节点的指
html语义化标签之结构元素
除了常规的div元素,h5还引入了很多许多语义化的结构元素来配置网页区域。 header元素:包含网页文档或者文档区域的标题; nav元素:建立一个导航链接区域。nav是块显示模块; main元素:包含网页文档的主要内容; footer元素:为网页或者网页区域创建页脚。 接下来一个简单的例子来实践下: &amp;lt;header&amp;gt; &amp;lt;h1&amp;gt;Trillium Med...
新增主体结构元素
section的用法: 代码示例: section的用法 大标题 小标题1 第一个小标题中的内容 小标题2 第二个小标题中的内容 小标题3 第三个小编题(段落)中的内容 结果展示: article用法 代码示例: article的用法 小标题1 放入文本信息或者图片等等
Java 中的链表分析
容器 我们平时都经常遇到容器这个词,那么 Java 集合中的容器指的是什么呢?**容器就是利用某种特定的数据结构来存储数据的。**在研究 Java 集合源码中时,我发现理解容器的关键要素很重要,因为这些关键元素在各个容器之间是通用的。 关键要素: 物理结构 数据结构分物理结构、逻辑结构。物理结构就是数据在计算机中是怎么存储的,有数组和链表两种方式。数组是内存中一块连续的存储空间,所以可以随机...
Java中的链表的基本操作
package cn.mdln.program; /**  * Java中的链表的基本操作  * @author Administrator  *  */ public class PracticeTestDemo5 { public static void main(String[] args) { Links all=new Links(); all.add(
JAVA中实现链表
由于数据本身不具备先后的关系,所以使用Node类来封装数据,同时利用Node来指向下一个节点。 1 简单链表的实现 节点类(Node): package com.test; /** * @author 1 * 定义节点类Node */ public class Node { private String data ; //保存数据 private Node next ; //
JAVA中链表的实现
以下代码是创建一个链表并输出,其中主要用到了内部类,链表的实现是面试中常常遇到的问题,除了链表输出外也可能遇到链表的删除、查找等,参照链表的输出,其他的功能实现并不难。 import java.util.ArrayList; import java.util.Scanner; public class MyLinked { public static void main(String ar
java中的链表
顺序表:数组,有下标链表:堆上,用指针相连  0-&amp;gt;0-&amp;gt;... (扩展:双向链表 环 树 图) 插入A:A-&amp;gt;next= flag-&amp;gt;next;   flag-&amp;gt;next= A; 删除flag:while(tmp-&amp;gt;next!=flag)    tmp= tmp-&amp;gt;next;    tmp-&amp;gt;next= flag-&amp;gt;next;    flag...
java中链表的操作
本人初学java有个问题想问一下,希望各位大虾帮下忙,先谢谢了!rn 在java中不是没有了指针吗,那么java中是如何对链表进行操作的呢??rn请附上例子讲一下,再次谢谢!
JAVA链表中的错误
从书上一字不变的抄下来,发现有错误。不知道怎么改正?rn[code=Java]rnpublic class LinkNodern private int data=-1;rn private LinkNode next=null;rn public int getData() rn return data;rn rn public void setData(int data) rn this.data = data;rn rn public LinkNode getNext() rn return next;rn rn public void setNext(LinkNode next) rn this.next = next;rn rnrn public class LinkTablern private LinkNode head=null;rn private int counts=0;rn public void insert(int d)rn if(head==null)rn head=new LinkNode;rn rn LinkNode n=new LinkNode(); //定义新的链表结点, 并将数值赋给新结点。rn n.setData(d);rn if (head.getNext()==null) //如果头结点后继无结点,注意头结点中无数据。rn head.setNext(n);rn rn elsern n.setNext(head.getNext()); //如果头结点的后继结点存在。rn head.setNext(n);rn rn counts++;rn rn public void print()rn LinkNode n=head.getNext();rn int iCounter=1;rn while(n!=null)rn System.out.println(n.getData()+" ");rn n=n.getNext();rn iCounter++;rn rn rn public int size()rn return this.size();rn rn public static void main(String arge[])rn LinkTable linkTable=new LinkTable();rn linkTable.insert(1);rn linkTable.insert(2);rn linkTable.insert(3);rn linkTable.insert(4);rn linkTable.insert(5);rn linkTable.insert(6);rn linkTable.insert(7);rn linkTable.print();rn rnrn[/code]
java中的数据结构——链表
链表 链表也是线性数据结构,与数组相比,在内存分配、内部结构及数据插入和删除的操作上均有不同。 链表用途广泛,适用于许多通用的数据库,也可以取代数组,作为其他存储结构的基础。 在链表中,每个数据项都被包含在链节点中,一个链节点是某个类的对象,这个类叫做Link。因为一个 链表中有许多类似的链节点,所以要用一个不同于链表的类来表达链节点。每个Link对象都包含一个对 下一个链节点引用的字段,即nex...