如何在单链表中的任意一个位置插入一个结点

Bertha 。 2023-10-05 23:53 4阅读 0赞

#### 文章目录 ####

*  在指定位置插入一个节点
 *   *  1. 思路
     *  2. 注意点
     *  3. 插入位置是否合法的判断
     *  4. 头插和尾插的情况
     *  5. 在中间位置插入的情况
     *  6. 中间位置下标的求解
     *  7. 代码实现

![a814aec4233c4ad791f5c9b38123ee4b.gif_pic_center][]

## 在指定位置插入一个节点 ##

node结点插入前：  
![在这里插入图片描述][49d50762e9414776a689c5edbcbb38d6.png_pic_center]

插入后：  
![c324197497a241f8ace0cfaee411cfa0.png_pic_center][]  
这里的下标指得是逻辑上定义的下标，用来表示index（插入位置）位置。  
并不是真是存在的。  
  
下面将会实现在**2下标**位置插入一个结点，即使node结点的下标为2。

### 1. 思路 ###

> 1.  定义一个node结点，即要插入的结点。
> 2.  判断要插入的位置是不是合法的。
> 3.  判断要插入的位置是在头部、尾部还是在中间位置。
> 4.  如果是在中间插入，则找到这个中间位置。
> 5.  改变结点的指向，使node结点的与前一个和后一个结点连接起来。

### 2. 注意点 ###

*  index位置在头部的时候就是头插法。
 *  index位置在尾部的时候就是尾插法。
 *  index其余可能会出现的位置是中间。
 *  **index位置不能超过单链表长度**。
 *  **index位置不能是负数**。

![2e4baa416a144755bb3a858739fe1152.jpeg_pic_center][]

### 3. 插入位置是否合法的判断 ###

我们要插入的位置有**可能是负数**或者**超过了单链表的长度**。  
  
为负数的情况：  
![在这里插入图片描述][636b840957384a0f8f0f03ca0d3e1811.png_pic_center]  
  
超过了单链表长度的情况：  
![98fcd4e038bb4fb6b40358174bfc71ca.png_pic_center][]

可以看到这两种情况要插入的位置都不在单链表的范围内，于是就会发生错误。  
我们可以在这里写一个异常，当index位置不合法的时候，抛一个异常来提示此时index位置不合法。  
  
下面的是实现异常的代码：

class IndexWrongFullExcetion extends RuntimeException{
        
        public IndexWrongFullExcetion() {
        
        }
    
        public IndexWrongFullExcetion(String message) {
        
            super(message);
        }
    }

### 4. 头插和尾插的情况 ###

如果是在头部或者尾部插入一个结点，直接调用之前写过的头插法和尾插法的方法即可。

这是属于头插法的情况  
  
![fcb67eb1c9b848bdb7e277196ec4070d.png_pic_center][]  
此是要在0下标插入一个结点。

这是属于尾插法的情况  
  
![77425c393f614b1a91bb6d1f93c8d64c.png_pic_center][]  
直接在最后一个结点的后面插入一个结点。

### 5. 在中间位置插入的情况 ###

如果是在中间位置插入，需要先求出这个位置具体的下标，然后在改变指向插入一个结点。  
  
插入前：  
![8f863b1290d44e91b6c31b25bf00f05f.png_pic_center][]

现在要在下标为2的位置插入一个结点，在插入后node结点的下标就变成了2，其他结点的位置向后推一个。

插入后：  
  
![fdb80121348c49c09602dd63ab4ae04b.png_pic_center][]

### 6. 中间位置下标的求解 ###

中间位置下标的求解思路：

*  定义一个cur来遍历单链表。
 *  当cur走到index-1步，也就是在index前面的位置停止遍历。
 *  此时的cur就是要插入的位置。

![b42899efb3574b1b860833265b5d1070.png_pic_center][]  
此时的cur还没有指向 **index-1** 的位置，cur指向下一个。

cur = cur.next;

此条语句使cur指向它的下一个结点。

![a0e6b17c1a5046bdb7a3303b5437cba7.png_pic_center][]  
此时的cur指向了 **index-1** 的位置

while (index - 1 != 0) {
        
        cur = cur.next;//找到下一个结点
        index--;//更加接近index位置
     }

写一个循环是cur走 index-1 步。

### 7. 代码实现 ###

//查找index位置的方法
    private ListNode findIndexSubOne(int index) {
         
       ListNode cur = this.head;//代替head向后移动
       //index不等于0则说明还没找到index的结点
       while (index - 1 != 0) {
        
          cur = cur.next;//找到下一个结点
          index--;//更加接近index位置
       }
       return cur;//此时cur指向的就是index的位置
    }
    
    //在链表指定位置插入一个结点
    public void addIndex(int index, int data) throws IndexWrongFullExcetion{
          //index是位置，逻辑上定义的下标；data是要插入的结点
        ListNode node = new ListNode(data);//新结点node
        //下标不能是负数，不能超过表的结点数
        if (index < 0 || index > size()) {
        
           System.out.println("index位置不合法！！！");
           throw new IndexWrongFullExcetion("index位置不合法！！！");
        }
        //如果index在0位置则属于头插法
        if (index == 0) {
         
           addStart(data);//头插法 - 调用头插法方法
           return;
        }
        //如果index在size()位置则属于尾插法
        if (index == size()) {
          
           addEnd(data); //尾插法 - 调用尾插法
           return;
        }
    
        //剩下的情况就是在中间位置插入
        //1.先让cur找到index-1的位置，即我要插入的位置
        //调用方法接收了cur的index结点位置
        ListNode cur = findIndexSubOne(index);
        //2.改变结点的指向来完成插入
        node.next = cur.next;//要插入结点的地址域指向index位置的下一个结点的地址域
        cur.next = node;//再将index的地址域指向node结点的数据域
    }

当是头插或者尾插的时候可以直接调用之前写过的两个方法，而如果是在中间位置插则就需要具体的实现了。

![7dcb960003ec4ce092e023a4dbfd2055.gif_pic_center][]

[a814aec4233c4ad791f5c9b38123ee4b.gif_pic_center]: https://img-blog.csdnimg.cn/a814aec4233c4ad791f5c9b38123ee4b.gif#pic_center
[49d50762e9414776a689c5edbcbb38d6.png_pic_center]: https://img-blog.csdnimg.cn/49d50762e9414776a689c5edbcbb38d6.png#pic_center
[c324197497a241f8ace0cfaee411cfa0.png_pic_center]: https://img-blog.csdnimg.cn/c324197497a241f8ace0cfaee411cfa0.png#pic_center
[2e4baa416a144755bb3a858739fe1152.jpeg_pic_center]: https://img-blog.csdnimg.cn/2e4baa416a144755bb3a858739fe1152.jpeg#pic_center
[636b840957384a0f8f0f03ca0d3e1811.png_pic_center]: https://img-blog.csdnimg.cn/636b840957384a0f8f0f03ca0d3e1811.png#pic_center
[98fcd4e038bb4fb6b40358174bfc71ca.png_pic_center]: https://img-blog.csdnimg.cn/98fcd4e038bb4fb6b40358174bfc71ca.png#pic_center
[fcb67eb1c9b848bdb7e277196ec4070d.png_pic_center]: https://img-blog.csdnimg.cn/fcb67eb1c9b848bdb7e277196ec4070d.png#pic_center
[77425c393f614b1a91bb6d1f93c8d64c.png_pic_center]: https://img-blog.csdnimg.cn/77425c393f614b1a91bb6d1f93c8d64c.png#pic_center
[8f863b1290d44e91b6c31b25bf00f05f.png_pic_center]: https://img-blog.csdnimg.cn/8f863b1290d44e91b6c31b25bf00f05f.png#pic_center
[fdb80121348c49c09602dd63ab4ae04b.png_pic_center]: https://img-blog.csdnimg.cn/fdb80121348c49c09602dd63ab4ae04b.png#pic_center
[b42899efb3574b1b860833265b5d1070.png_pic_center]: https://img-blog.csdnimg.cn/b42899efb3574b1b860833265b5d1070.png#pic_center
[a0e6b17c1a5046bdb7a3303b5437cba7.png_pic_center]: https://img-blog.csdnimg.cn/a0e6b17c1a5046bdb7a3303b5437cba7.png#pic_center
[7dcb960003ec4ce092e023a4dbfd2055.gif_pic_center]: https://img-blog.csdnimg.cn/7dcb960003ec4ce092e023a4dbfd2055.gif#pic_center