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

在指定位置插入一个节点

node结点插入前：

插入后：

这里的下标指得是逻辑上定义的下标，用来表示index（插入位置）位置。
并不是真是存在的。

下面将会实现在2下标位置插入一个结点，即使node结点的下标为2。

1. 思路

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

2. 注意点

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

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

我们要插入的位置有可能是负数或者超过了单链表的长度。

为负数的情况：


超过了单链表长度的情况：

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

下面的是实现异常的代码：

class IndexWrongFullExcetion extends RuntimeException{
    public IndexWrongFullExcetion() {
    }

    public IndexWrongFullExcetion(String message) {
        super(message);
    }
}
1
2
3
4
5
6
7
8

4. 头插和尾插的情况

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

这是属于头插法的情况


此是要在0下标插入一个结点。

这是属于尾插法的情况


直接在最后一个结点的后面插入一个结点。

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

如果是在中间位置插入，需要先求出这个位置具体的下标，然后在改变指向插入一个结点。

插入前：

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

插入后：

6. 中间位置下标的求解

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

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

此时的cur还没有指向 index-1 的位置，cur指向下一个。

cur = cur.next;
1

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

此时的cur指向了 index-1 的位置

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

写一个循环是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结点的数据域
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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