链表增删操作问题及解决方法

傷城~ 2024-02-21 10:07 43阅读 0赞

#### 目录 ####

*  链表增加元素
 *   *  首部
     *  中间
     *  尾部
 *  链表删除元素
 *   *  首部
     *  中间
     *  尾部

链表是一种常用的数据结构，用于存储和组织数据。在链表中，增加和删除元素是常见的操作。然而，在进行链表的增删操作时，对于首部、中间和尾部位置的元素，都存在一些问题需要解决。

## 链表增加元素 ##

### 首部 ###

当需要在首部插入一个新的元素时，**需要将该元素的引用指向原本的首部节点，并将链表的头引用指向新的元素**。这样做会花费O(1)的时间，即常量时间，因为只需要修改两个引用的指向。

### 中间 ###

当需要在链表中间插入一个元素时，需要先找到**插入位置的前一个节点**，然后**通过修改引用来插入新的节点**。这个过程需要花费O(n)的时间，其中n是链表的长度。  
需要注意的是修改引用的顺序不能颠倒。  
![在这里插入图片描述][6a7772f3ee1f4d0d871024a5ed9d3919.png]

### 尾部 ###

链表的尾部是指链表中的最后一个节点。当需要在尾部插入一个新的元素时，只需要找到尾部节点，并将其引用指向新的元素。这样做同样花费O(n)的时间，因为需要遍历整个链表找到尾部节点。

代码演示：

public static Node insert(Node head, Node nodeInsert, int position) {
        
            //判断链表是否为空，如果为空，则直接返回新节点作为头节点
             if(head== null){
        
                 return nodeInsert;
             }
             //链表元素个数
             int size = getLength(head);
             //检查插入位置是否合法
             if(position > size+1 ||  position<1){
        
                 System.out.println("插入位置不合法");
                 return head;
             }
            //如果插入位置为1,将新节点的next指针指向原头节点，然后将新节点作为新的头节点返回。
             if(position == 1){
        
                 nodeInsert.next = head;
                 head = nodeInsert;
                 return head;
             } else {
        
                 Node node = head;
                // 遍历链表，找到插入位置的前一个节点(node),将新节点的next指针指向该节点的next指针，然后将该节点的next指针指向新节点
                 for (int i = 1; i < position - 1; i++) {
        
                     node=node.next;
                 }
                 nodeInsert.next = node.next;
                 node.next = nodeInsert;
                 return head;
             }
        }

## 链表删除元素 ##

### 首部 ###

删除首部元素时，情况会稍微复杂一些。需要将链表的头节点引用指向原本首部的下一个节点，并释放原本的首部节点。这同样需要花费O(1)的时间，而不会受到链表长度的影响。

### 中间 ###

在删除链表中部的元素时，同样需要先找到要删除的节点的前一个节点，然后将其引用指向要删除节点的下一个节点，然后释放要删除的节点。这个过程同样需要花费O(n)的时间。  
![在这里插入图片描述][a3fefb04e17945f6a686a2a0bcfb84f5.png]

### 尾部 ###

删除链表尾部的元素时，同样需要遍历整个链表找到尾部节点的前一个节点，并将其引用指向null。这个过程同样需花费O(n)的时间。

代码演示：

public static Node deletNode(Node head, int position){
        
            //判断链表是否为空，如果为空则直接返回null。
           if(head == null){
        
               return null;
           }
           int size = getLength(head);
           //判断要删除的位置position是否合法，即大于链表长度或小于1
           if(position> size ||  position < 1){
        
               System.out.println("删除位置不合法");
               return head;
           }
           //如果要删除的位置position为1,说明要删除的是头节点，直接返回头节点的下一个节点作为新的头节点。
           if(position == 1){
        
             return head.next;
    
           } else {
        
             Node node = head;
               for (int i = 1; i < position -1 ; i++) {
        
                   node = node.next;
               }
               node.next = node.next.next;
               return head;
           }
        }

综上所述，链表的增删操作在首部、中间和尾部位置都会存在一些问题，时间复杂度也有所不同。为了解决这些问题，我们可以在实际应用中采取一些优化措施，比如使用双向链表，可以加快在中间和尾部进行插入和删除操作的速度。此外，还想了解更多可查阅[我的专栏][Link 1]。

[6a7772f3ee1f4d0d871024a5ed9d3919.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/26a3fc3f42a6437a8923a22111ced6c8.png
[a3fefb04e17945f6a686a2a0bcfb84f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/e5ee56551600499f85aa767e2af7ebd4.png
[Link 1]: http://t.csdnimg.cn/aCQjp