java 如何实现单链表中的头插法

短命女 2023-10-05 23:36 10阅读 0赞

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

*   *  头插法
     *   *  1 思路
         *  2 插入过程
         *   *  2.1 定义node节点
             *  2.2 将node插入到原来head前面的位置
             *  2.3 将node节点与下一个结点链接起来
             *  2.4 更改head的指向
         *  3 注意点
         *  4 为空的情况
         *  5 代码实现

![7de32ebb87f14e46bf74b90d46da63ef.gif_pic_center][]

### 头插法 ###

![在这里插入图片描述][b84e846033e742a08f4e2b01b677b7c8.png]

#### 1 思路 ####

*  先定义一个新的节点，命名为node。
 *  将node插入到原来单链表头节点的前面。
 *  使node指向下一个结点，也就是原表的head。
 *  再将node改成头节点，head指向node。

原来的单链表：  
  
![987da473e163481ca9c5742ab6d73b70.png_pic_center][]

插入后的单链表：  
  
![3a172da65e1447d3a5cf6760424c61a5.png_pic_center][]

#### 2 插入过程 ####

![在这里插入图片描述][9f92b1ba65b448a08b7b2017dd1c3e1d.png]

##### 2.1 定义node节点 #####

![4e11502d9b994c7f81a482151d1d6e7f.png_pic_center][]

##### 2.2 将node插入到原来head前面的位置 #####

![81d6350d55074332bbc7af168648684f.png_pic_center][]

##### 2.3 将node节点与下一个结点链接起来 #####

![7cf1e97b4e6344029642caba123d0698.png][]  
将node节点的地址域**存上下一个节点的地址**。  
具体的做法是：**node.next = head**，将node的地址域指向原来的头节点。

##### 2.4 更改head的指向 #####

![f5c19e9b3104409499da0575a12672e3.png_pic_centerg][]  
让head重新指向单链表的node。  
具体做法是：**head = node**

#### 3 注意点 ####

在头插的时候，**要先与后面的结点绑定，再更改head的指向**。就是先让要插入的结点与下一个结点链接之后再让head指向新的头结点位置。  
  
先更改head指向再绑定后面结点的情况：

1.  执行**head = node**前：  
      
    ![90a8af1b967348e4860b060e84bb628e.png_pic_center][]
2.  执行**head = node**后：  
      
    ![8e8d2908e5904badb3ee48e6e36f5087.png_pic_center][]
3.  当执行过后，head此时与node指向了同一个节点，而在执行**node.next = head**的时候相当于让它自己指向自己。  
      
    ![cd9d5a99a1904202b15cf0e9816cec63.png_pic_center][]  
    当前node结点的地址是0x10，因为**node和head指向同一个位置**，head的地址也是0x10，所以node的地址域存的是0x10，会因为无法连接到下一个结点而带来错误。

#### 4 为空的情况 ####

如果要在一个空的单链表中的插入一个node结点，步骤和上面不为空的情况相同，先绑定后面，再更改head的指向。

只不过在实现头插法的时候，不需要考虑单链表是不是空的，因为它总是在头部插入。

#### 5 代码实现 ####

//头插法 - 插入结点到头部
    //头插法可以不考虑表是不是null - 即使表是空的node的地址域也是null，也能找到下一个结点
    public void addStart(int data) {
        
       //1.定义一个要插入的结点node
       ListNode node = new ListNode(data);
    
       //2.让node的地址域指向原表的头结点
       node.next = this.head;
    
       //3.再让原表的头结点直向新表的头结点（node）
       head = node;
    }

![fae8352999fe4ad585b6e09da8b9d968.jpeg_pic_center][]

[7de32ebb87f14e46bf74b90d46da63ef.gif_pic_center]: https://img-blog.csdnimg.cn/7de32ebb87f14e46bf74b90d46da63ef.gif#pic_center
[b84e846033e742a08f4e2b01b677b7c8.png]: https://img-blog.csdnimg.cn/b84e846033e742a08f4e2b01b677b7c8.png
[987da473e163481ca9c5742ab6d73b70.png_pic_center]: https://img-blog.csdnimg.cn/987da473e163481ca9c5742ab6d73b70.png#pic_center
[3a172da65e1447d3a5cf6760424c61a5.png_pic_center]: https://img-blog.csdnimg.cn/3a172da65e1447d3a5cf6760424c61a5.png#pic_center
[9f92b1ba65b448a08b7b2017dd1c3e1d.png]: https://img-blog.csdnimg.cn/9f92b1ba65b448a08b7b2017dd1c3e1d.png
[4e11502d9b994c7f81a482151d1d6e7f.png_pic_center]: https://img-blog.csdnimg.cn/4e11502d9b994c7f81a482151d1d6e7f.png#pic_center
[81d6350d55074332bbc7af168648684f.png_pic_center]: https://img-blog.csdnimg.cn/81d6350d55074332bbc7af168648684f.png#pic_center
[7cf1e97b4e6344029642caba123d0698.png]: https://img-blog.csdnimg.cn/7cf1e97b4e6344029642caba123d0698.png
[f5c19e9b3104409499da0575a12672e3.png_pic_centerg]: https://img-blog.csdnimg.cn/f5c19e9b3104409499da0575a12672e3.png#pic_centerg
[90a8af1b967348e4860b060e84bb628e.png_pic_center]: https://img-blog.csdnimg.cn/90a8af1b967348e4860b060e84bb628e.png#pic_center
[8e8d2908e5904badb3ee48e6e36f5087.png_pic_center]: https://img-blog.csdnimg.cn/8e8d2908e5904badb3ee48e6e36f5087.png#pic_center
[cd9d5a99a1904202b15cf0e9816cec63.png_pic_center]: https://img-blog.csdnimg.cn/cd9d5a99a1904202b15cf0e9816cec63.png#pic_center
[fae8352999fe4ad585b6e09da8b9d968.jpeg_pic_center]: https://img-blog.csdnimg.cn/fae8352999fe4ad585b6e09da8b9d968.jpeg#pic_center