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

缺乏、安全感 2023-10-05 23:51 21阅读 0赞

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

*  尾插法
 *   *  1 思路
     *  2 插入过程
     *   *  2.1 定义node节点
         *  2.2 定义一个cur来查找单链表的尾部位置
         *  2.3 将node插入到单链表的尾部位置
         *  2.4 让node结点与前一个结点连接起来
     *  3 注意点
     *  4 为空的情况
     *  5 代码实现

![7de32ebb87f14e46bf74b90d46da63ef.gif_pic_center][]

## 尾插法 ##

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

### 1 思路 ###

*  先定义一个新的节点，命名为node。
 *  找到尾部位置
 *  将node插入到单链表的尾部位置。
 *  使node指向前一个结点，也就是原表的尾部位置。

插入前的单链表：  
  
![3ea024a102104cea84d64640354cbeef.png_pic_center][]  
  
插入后的单链表：  
![75681f87386d44158f7005f511c23dd3.png_pic_center][]

### 2 插入过程 ###

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

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

![0c3f83571d1c405d85892b88bb292469.png_pic_center][]

#### 2.2 定义一个cur来查找单链表的尾部位置 ####

![82c86f26c7cc49f68e87dd433039f814.png_pic_center][]  
定义一个cur来遍历单链表，如果**cur.next != null**，cur就往后走，直到遇到null，停止遍历，此时cur指向的位置就是单链表尾部位置。

#### 2.3 将node插入到单链表的尾部位置 ####

![2f27a37b684a4040844c26f7efabd528.png_pic_center][]

将node结点放到尾结点的后一个节点的位置。

#### 2.4 让node结点与前一个结点连接起来 ####

![0d83580e0f914356b1d76888e61c0553.png_pic_center][]  
旨在修改当前cur节点的指向，**将cur的地址域中存放node的地址**。

### 3 注意点 ###

在遍历单链表的时候，循环的判断条件应该是**cur.next != null**，而不应该是**cur != null**。  
  
解释：

*  cur.next != null 的情况  
    ![3f084affff6641b59ec5f4a0fc62567d.png_pic_center][]  
    1.cur.next != null 这条语句的含义是，cur指向的结点的地址域里的地址不是null。  
    2.单链表结点的地址域存放的是下一个节点的地址，cur.next 正好访问到的是下一个结点的地址。  
    3.如果cur的地址域的地址是null，说明cur的下一个节点就是空，即cur为末尾结点。
 *  **cur != null 的情况**  
    ![6bf197eaf2e44605895f2ca2867ca361.png_pic_center][]  
    当cur == null 的时候多遍历了一次，代码设计不合理。

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

如果单链表是空的，就不需要找尾结点是哪一个了，node就是第一个结点，**直接让head指向node即可**。  
  
![f7f90357581741f887f48e5c81fdfd90.png_pic_center][]

### 5 代码实现 ###

//尾插法 - 插入几点到尾部
    public void addEnd(int data) {
        
       //1.定义一个结点和cur
       ListNode cur = this.head;//代替head向后移动
       ListNode node = new ListNode(data);//新结点node
       //现在分两个情况：1.链表不为空，即链表的尾结点在最后一个结点处. 2.链表为空，即head就是尾结点.
    
       //2.找到尾结点 - cur指向的地址为空就是尾结点
       //情况2：链表为空
       if(cur == null) {
        
          this.head = node;//直接将头结点指向node结点
       }else{
         //情况1：链表不为空
          while(cur.next != null) {
        
             cur = cur.next;//找到下一个结点
          }
          //3.此时已经找到了尾结点，可以开始将结点串联起来了
          cur.next = node;//cur的地址域指向node结点
       }
    }

![2ea7652bdbd243e3bf8536c57a6f8309.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
[3ea024a102104cea84d64640354cbeef.png_pic_center]: https://img-blog.csdnimg.cn/3ea024a102104cea84d64640354cbeef.png#pic_center
[75681f87386d44158f7005f511c23dd3.png_pic_center]: https://img-blog.csdnimg.cn/75681f87386d44158f7005f511c23dd3.png#pic_center
[9f92b1ba65b448a08b7b2017dd1c3e1d.png]: https://img-blog.csdnimg.cn/9f92b1ba65b448a08b7b2017dd1c3e1d.png
[0c3f83571d1c405d85892b88bb292469.png_pic_center]: https://img-blog.csdnimg.cn/0c3f83571d1c405d85892b88bb292469.png#pic_center
[82c86f26c7cc49f68e87dd433039f814.png_pic_center]: https://img-blog.csdnimg.cn/82c86f26c7cc49f68e87dd433039f814.png#pic_center
[2f27a37b684a4040844c26f7efabd528.png_pic_center]: https://img-blog.csdnimg.cn/2f27a37b684a4040844c26f7efabd528.png#pic_center
[0d83580e0f914356b1d76888e61c0553.png_pic_center]: https://img-blog.csdnimg.cn/0d83580e0f914356b1d76888e61c0553.png#pic_center
[3f084affff6641b59ec5f4a0fc62567d.png_pic_center]: https://img-blog.csdnimg.cn/3f084affff6641b59ec5f4a0fc62567d.png#pic_center
[6bf197eaf2e44605895f2ca2867ca361.png_pic_center]: https://img-blog.csdnimg.cn/6bf197eaf2e44605895f2ca2867ca361.png#pic_center
[f7f90357581741f887f48e5c81fdfd90.png_pic_center]: https://img-blog.csdnimg.cn/f7f90357581741f887f48e5c81fdfd90.png#pic_center
[2ea7652bdbd243e3bf8536c57a6f8309.jpeg_pic_center]: https://img-blog.csdnimg.cn/2ea7652bdbd243e3bf8536c57a6f8309.jpeg#pic_center