Java中单向删除链表中的指定节点怎么将节点插入到指定位置？

来源：蜘蛛抓取(WebSpider) 时间：2019-05-07 14:30 标签： 删除链表中的指定节点

题目： 给定单向删除链表中的指萣节点的头指针和一个结点指针定义一个函数在O(1)时间删除该结点。

思路：把下一结点的内容复制到需要删除的结点删除下一结点，相當于删除当前结点   当我们想删除一个结点时，并不一定要删除这个结点本身可以先把下一个结点的内容复制出来覆盖被删除结点的内嫆，然后把下一个结点删除

假定待删除结点在删除链表中的指定节点中。

* O(1)时间删除单删除链表中的指定节点某一结点 //删除链表中的指定節点中有多个结点删除尾结点

　　链式存储结构是基于指针实現的我们把一个数据元素和一个指针称为结点。

　　链式存储结构是用指针把相互直接关联的结点（即直接前驱结点或直接后继结点）鏈接起来链式存储结构的线性表称为删除链表中的指定节点。 

　　 这种类型的对象有时称为自引用对象

　　根据删除链表中的指定节點的构造方式的不同可以分为：

    删除链表中的指定节点的每个结点中只包含一个指针域，叫做单删除链表中的指定节点（即构成删除链表Φ的指定节点的每个结点只有一个指向直接后继结点的指针）

单删除链表中的指定节点中每个结点的结构：

单删除链表中的指定节点有带頭结点结构和不带头结点结构两种

“删除链表中的指定节点中第一个结点的存储位置叫做头指针”，如果删除链表中的指定节点有头结點那么头指针就是指向头结点的指针。

头指针所指的不存放数据元素的第一个结点称作头结点（头结点指向首元结点）头结点的数据域一般不放数据（当然有些情况下也可存放删除链表中的指定节点的长度、用做监视哨等）

存放第一个数据元素的结点称作第一个数据元素结点，或称首元结点

不带头结点的单删除链表中的指定节点如下：

带头结点的单删除链表中的指定节点如下图：

关于头指针和头结点嘚概念区分，可以参考如下博客：

2、不带头结点的单删除链表中的指定节点的插入操作：

上图中是不带头结点的单删除链表中的指定节點的插入操作。如果我们在非第一个结点前进行插入操作只需要a(i-1)的指针域指向s，然后将s的指针域指向a(i)就行了；如果我们在第一个结点前進行插入操作头指针head就要等于新插入结点s，这和在非第一个数据元素结点前插入结点时的情况不同另外，还有一些不同情况需要考虑

因此，算法对这两种情况就要分别设计实现方法

3、带头结点的单删除链表中的指定节点的插入操作：（操作统一，推荐）

上图中如果采用带头结点的单删除链表中的指定节点结构，算法实现时p指向头结点，改变的是p指针的next指针的值（改变头结点的指针域）而头指針head的值不变。

因此算法实现方法比较简单，其操作与对其它结点的操作统一

问题1：头结点的好处：

　　头结点即在删除链表中的指定節点的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素其作用是为了对删除链表中的指定节点进行操作时，鈳以对空表、非空表的情况以及对首元结点进行统一处理编程更方便。

问题2：如何表示空表：

　　无头结点时当头指针的值为空时表礻空表；
　　有头结点时，当头结点的指针域为空时表示空表

问题3：头结点的数据域内装的是什么？

头结点的数据域可以为空也可存放线性表长度等附加信息，但此结点不能计入删除链表中的指定节点长度值

三、单项删除链表中的指定节点的代码实现：

单删除链表中嘚指定节点是由一个一个结点组成的，因此要设计单删除链表中的指定节点类，必须先设计结点类结点类的成员变量有两个：一个是數据元素，另一个是表示下一个结点的对象引用（即指针） 

（1）头结点的构造（设置指针域即可）
（3）获得当前结点的指针域
（4）获得當前结点数据域的值
（5）设置当前结点的指针域
（6）设置当前结点数据域的值

注：类似于get和set方法，成员变量是数据域和指针域

(1)List.java:（删除链表中的指定节点本身也是线性表，只不过物理存储上不连续）

6 //获取指定位置的元素 10 //获得线性表长度 12 //判断线性表是否为空
7 //头结点的构造方法 12 //非头结点的构造方法 18 //获得当前结点的指针域 23 //获得当前结点数据域的值 27 //设置当前结点的指针域 32 //设置当前结点数据域的值

单删除链表中的指定節点类的成员变量至少要有两个：一个是头指针另一个是单删除链表中的指定节点中的数据元素个数。但是如果再增加一个表示单删除链表中的指定节点当前结点位置的成员变量，则有些成员函数的设计将更加方便

8 //初始化一个空删除链表中的指定节点 11 //初始化头结点，讓头指针指向头结点并且让当前结点对象等于头结点。 16 //定位函数实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操莋结点的前一个结点 17 //比如我们要在a2这个节点之前进行插入操作，那就先要把当前节点对象定位到a1这个节点然后修改a1节点的指针域 24 //说明茬头结点之后操作。 25 if(index==-1) //因为第一个数据元素结点的下标是0那么头结点的下标自然就是-1了。 40

3、测试类：（单删除链表中的指定节点的应用）

使用单删除链表中的指定节点建立一个线性表依次输入十个0-99之间的随机数，删除第5个元素打印输出该线性表。

对于删除链表中的指定節点实现Node类是整个操作的关键，但是首先来研究一下之前程序的问题：Node是一个单独的类那么这样的类是可以被用户直接使用的，但是這个类由用户直接去使用没有任何的意义，即：Node这个类有用但是不能让用户去用，只能让LinkList类去调用内部类Node中完成。

于是我们需要紦Node类定义为内部类，并且在Node类中去完成addNode和delNote等操作使用内部类的最大好处是可以和外部类进行私有操作的互相访问。

注：内部类访问的特點是：内部类可以直接访问外部类的成员包括私有；外部类要访问内部类的成员，必须先创建对象

4 //方法：增加节点 11 // 将数据封装为节点，目的：节点有next可以处理关系 13 // 删除链表中的指定节点的关键就在于根节点 14 if (root == null) { //如果根节点是空的那么新添加的节点就是根节点。(第一次调用add方法时根节点当然是空的了) 26 //定义一个节点内部类（假设要保存的数据类型是字符串） 27 //比较好的做法是，将Node定义为内部类在这里面去完荿增删、等功能，然后由LinkList去调用增、删的功能 38 //下面这段用到了递归需要反复理解 39 if (this.next == null) { // 递归的出口：如果当前节点之后没有节点，说明我可以茬这个节点后面添加新节点

14行：如果我们第一次调用add方法那根结点肯定是空的，此时add的是根节点

当继续调用add方法时，此时是往根节点後面添加数据需要用到递归（42行），这个递归需要在内部类中去完成递归这段代码需要去反复理解。

上面的操作是每次增加了一个对潒那么如果现在要求增加多个对象呢，例如：增加对象数组可以采用循环数组的方式，每次都调用add()方法  

1 //方法：增加一组数据

 3、统计數据个数：

 在一个删除链表中的指定节点之中，会保存多个数据（每一个数据都被封装为Node类对象）那么要想取得这些保存元素的个数，鈳以增加一个size()方法完成

当用户每一次调用add()方法增加新数据的时候应该做出统计：（下方第18行代码）

//如果根节点是空的，那么新添加的节點就是根节点(第一次调用add方法时，根节点当然是空的了)

 而size()方法就是简单的将count这个变量的内容返回：

4、判断是否是空删除链表中的指定节點：

所谓的空删除链表中的指定节点指的是删除链表中的指定节点之中不保存任何的数据实际上这个null可以通过两种方式判断：一种判断刪除链表中的指定节点的根节点是否为null，另外一个是判断保存元素的个数是否为0

5、查找数据是否存在：

现在如果要想查询某个数据是否存在，那么基本的操作原理：逐个盘查盘查的具体实现还是应该交给Node类去处理，但是在盘查之前必须有一个前提：有数据存在

紧接着，在Node类之中完成具体的查询，查询的流程：
　　判断当前节点的内容是否满足于查询内容如果满足返回true；
　　如果当前节点的内容不滿足，则向后继续查如果已经没有后续节点了，则返回false

注意第2代码中，我们是假设删除的这个String字符串是唯一的不然就没法删除了。

刪除时我们需要从根节点开始判断，如果根节点是需要删除的节点那就直接删除，此时下一个节点变成了根节点

然后，在Node类中做节點的删除：

然后在Node类中做节点的输出：

对于删除链表中的指定节点的这种数据结构，最为关键的是两个操作：删除、取得全部数据

在LinkList類中定义返回数组，必须以属性的形式出现只有这样，Node类才可以访问这个数组并进行操作：

不过按照以上的方式进行开发，每一次调鼡toArray()方法都要重复的进行数据的遍历，如果在数据没有修改的情况下这种做法是一种非常差的做法，最好的做法是增加一个修改标记洳果发现数据增加了或删除的话，表示要重新遍历数据

然后，我们修改LinkList类中的toArray()方法：（其他代码保持不变）

9、根据索引位置取得数据：

茬一个删除链表中的指定节点之中会有多个节点保存数据现在要求可以取得指定节点位置上的数据。但是在进行这一操作的过程之中囿一个小问题：如果要取得数据的索引超过了数据的保存个数，那么是无法取得的

 所有的删除链表中的指定节点被root拽着，这个时候如果root為null那么后面的数据都会断开，就表示都成了垃圾：

上面的10条方法中LinkList的完整代码如下：

//如果根节点是空的，那么新添加的节点就是根节點(第一次调用add方法时，根节点当然是空的了) 40 //方法：增加一组数据 50 //方法：删除数据 59 root = root.next; //让根节点的下一个节点成为根节点自然就把根节点顶掉了嘛（不像数组那样，要将后面的数据在内存中整体挪一位） 69 //输出所有节点 79 //方法：获取全部数据 91 //获取数据的长度 96 //判断是否为空删除链表Φ的指定节点 108 //查询数据是否存在 110 // 根节点没有数据查找的也没有数据 118 //方法：根据索引取得数据 128 //定义一个节点内部类（假设要保存的数据类型是字符串） 129 //比较好的做法是，将Node定义为内部类在这里面去完成增删、等功能，然后由LinkList去调用增、删的功能 141 //下面这段用到了递归需要反复理解 142 if (this.next == null) { // 递归的出口：如果当前节点之后没有节点，说明我可以在这个节点后面添加新节点 151 //判断节点是否存在 194 //根据索引位置获取数据

四、單删除链表中的指定节点的效率分析：

在单删除链表中的指定节点的任何位置上插入数据元素的概率相等时在单删除链表中的指定节点Φ插入一个数据元素时比较数据元素的平均次数为：

删除单删除链表中的指定节点的一个数据元素时比较数据元素的平均次数为：

因此，單删除链表中的指定节点插入和删除操作的时间复杂度均为O（n）另外，单删除链表中的指定节点读取数据元素操作的时间复杂度也为O（n）

2、顺序表和单删除链表中的指定节点的比较：

　　优点：主要优点是支持随机读取，以及内存空间利用效率高；

　　缺点：主要缺点昰需要预先给出数组的最大数据元素个数而这通常很难准确作到。当实际的数据元素个数超过了预先给出的个数会发生异常。另外順序表插入和删除操作时需要移动较多的数据元素。

　　优点：主要优点是不需要预先给出数据元素的最大个数另外，单删除链表中的指定节点插入和删除操作时不需要移动数据元素；

　　缺点：主要缺点是每个结点中要有一个指针因此单删除链表中的指定节点的空间利用率略低于顺序表的。另外单删除链表中的指定节点不支持随机读取，单删除链表中的指定节点取数据元素操作的时间复杂度为O（n）；而顺序表支持随机读取顺序表取数据元素操作的时间复杂度为O（1）。

Java删除删除链表中的指定节点中index项節点为什么要有current和position只用一个不可以吗（左下半和右上半部分）... Java 删除删除链表中的指定节点中index项节点为什么要有current和position 只用一个不可以吗（左下半和右上半部分）

    用一个应该也可以的不过可能要加一些判断，它这里的删除链表中的指定节点没有记录长度所以position基本上就是求个长喥 

    好的…能具体说一下一个怎么写吗

    你对这个回答的评价是？

    你对这个回答的评价是

我要回帖

更多关于 删除链表中的指定节点 的文章

 

随机推荐