链表的数据结构和算法 3 - 单向链表的插入、删除、修改和查找（Java 版）

最编程 2024-06-11 13:25:18

...

一、插入操作

插入操作需要考虑在链表表头插入和在链表表尾插入以及表中插入。

链表表头插入一个节点的情况如下：

具体过程说明:

1)创建一个空节点。空的含义是执行插入操作的程序并没有给该节点的域赋任何值。

2)节点的info域初始化为给定值

3)因为节点要放在表头，所以该节点的next域指向表中第一个节点的引用，即head的当前值

4)新节点领先于表中的所有节点，所以head更新为新节点的指针。

同时还要考虑一种情况：当在空链表中插入一个节点时，在空链表中head和tail都是空值，所以二者都将成为新表中唯一节点的引用。当在非空链表中插入时只需要更新head域。

具体代码如下：

public void addToHead(int e1){
    head=new SingleLinkNode(e1,head);if(tail==null)
        tail=head;
    }

链表表尾插入一个节点的情况如下：

具体过程如下：

1)创建一个空节点

2)将节点的info域设置为6

3)因为节点要在表尾，所以next域设置为空

4)将表中最后一个节点的next域指向该节点

5)新节点跟随与所有节点之后，所以将tail指向该节点

要注意一种情况：当链表为空时，它是指向一个不存在节点的不存在域的引用，这会报告空指针异常

具体代码如下:

public boolean isEmpty()
    {return head==null;
    }public void addToTail(int e1){if(!isEmpty())
    {
        tail.next=new SingleLinkNode(e1);
            tail=tail.next;
    }else{
        head=tail=new SingleLinkNode(e1);
    }
    
    }

在链表的表头和表尾进行插入操作的过程非常的相似，这是因为SingleLinkedList用了两个引用域，head和tail。所以方法addToHead()和方法addToTail()都能以常量时间O(1)执行。即不管这个链表中的节点数目有多少，操作数量都不会超过常量c。同时我们注意到，因为head引用允许我们访问整个链表，所有tail引用并不是不可或缺的，它的唯一作用就是能立即访问到表中最后一个点。当不使用tail引用时，向表尾添加节点的操作会变得复杂，因为增加的节点首先必须到达最后一个节点，这就需要扫描整个表。完成这个过程需要O(n)步。

表中插入一个节点时，在第i个节点之后，如下图：

具体过程如下:

1)创建一个空节点

2)将该空节点的info域赋值为6

3)遍历找到要插入的第i个点

4)将新的节点的next域指向第i+1个节点

5)将第i个节点指向新节点

具体代码如下:

/* * 表中插入:在第i个节点之后添加节点     */public void addToList(int i,int e1)
    {
    SingleLinkNode p=head;int j=1;    while(p!=null&&(j<i))
    {
        p=p.next;
        j++;
    }if(p==null||j>i)       return;
    
    SingleLinkNode s=new SingleLinkNode(e1);
    s.next=p.next;
    p.next=s;
    }

二、删除操作

删除操作包括删除表头节点并且返回它所存储的值。这个过程要考虑在表头和表尾删除节点以及在表中删除节点

在表头删除节点

1)将第一个节点的数据暂时存放在局部变量e1中

2)重置head域，使第二个节点变为第一个节点。

3)经过上述过程，第一个节点被废弃了，随后由无用单元处理

要注意的是这是先前的第一个节点仍然可以访问整个链表，但该节点本身是不可访问的，于是就认为它不存在。因为节点是立即可以访问的。所以删除一个节点的方法也是O(1)。

与前面不同的是，需要考虑两个特殊的情况。首先是试图在一个空链表中删除一个节点。一旦这样做了，程序会报出空指针异常而崩溃。为了解决这个问题，可以有两种方法：

1、使用throws语句

即public int deleteFromHead()throws NullPointerException{

…}

调用者的throws子句应该和try-catch子句匹配从而捕获异常。这个解决放方法可以时程序不至于造成致命的错误。

2、将方法isempty()加入到SingleLinkedList类中，判断链表是否为空。

第二个特例是当删除一个节点之后，链表为空，此时head和tail都应该设置为空值。

在表尾删除节点

当删除节点之后，tail必须指向链表中的新的尾节点，也即tail需要移动一个节点。但直接向后移动式不可能的，因为从最后一个节点到它的前驱结点没有直接的连接。因此需要从表头开始查找tail的直接前驱节点。可以使用for循环借助临时变量tmp扫描整个表。变量tmp初始化为表头，循环体每重复一次，tmp就前进一个节点。如果for循环简化为如下的形式

for(;head.next!=tail;head=head.next);

那么链表仅能扫描一次，并且无法再访问表头，因head指针被永久更新为最后一个节点的前一个节点，而这个节点即将成为最后一个节点。像这样的情况，用临时变量使对表头的访问通路完好无缺是至关重要的操作。

在删除最后一个节点时，也有两个特殊情况：1、如果是空表，没有可删除的对象，此时可以按照上面的方法进行处理，2、当单节点表删掉它唯一的节点而变空时，仍然需要置head和tail为空。

在删除尾节点的方法中，最耗时的就是for循环查找尾节点之前的一个节点。显然n个节点的单向链表循环将执行n-1次，这就是造成尾节点删除算法的时间复杂度为O(n)的主要原因。

以上讨论的是从表头或者表尾删除节点，并且返回删除节点存储的整数的两种操作（总是从同一个位置）。当希望删除某个保存特定整数的节点而不管其在表中的位置是，要用到另外一种方法。被删除的节点可能正好在表头、表尾或者表中的任意一个位置。简而言之，必须先定位一个节点，然后直接将该节点的前驱结点和后继节点相连从而删除它。因为不知道节点在哪，所以寻找删除节点的过程要比上面讨论的复杂的多。

将一个节点的前驱节点和后继节点链接就可以将其从链表中删除。但是因为这是单向链表，从一个节点无法到达它的前驱结点，所以要先扫描整个链表找到要删除的节点，然后再次扫描找到其前驱结点。除了这一种情况，还有以下情况要考虑:

1)从空表中删除一个节点，直接退出

2)从仅有一个节点中的链表中删除唯一节点，head和tail均设置为空

3)从仅有两个节点的链表中删除第一个节点，这就需要重新更新head域

4)从仅有两个节点的链表中删除最后一个节点，这就需要重新更新tail域

5)删除链表中不存在的节点，不做处理。

很明显。对于这个方法而言，最好的情况是删除头节点。完成它仅需要O(1)的时间，最坏的情况是删除尾节点，这时候需要O(n)的时间。平均情况下依赖于for循环执行的次数。所以这个方法平均执行O(n)步。

删除表头节点代码如下：

public int  deleteFromHead()
    {int e1=head.info;    if(head==tail)
        head=tail=null;elsehead=head.next;return e1;
    }

删除表尾节点代码如下：

public int deleteFromTail()
    {int e1=tail.info;if(head==tail)
        head=tail=null;else{
        SingleLinkNode tmp;for(tmp=head;tmp.next!=tail;tmp=tmp.next)
        tail=tmp;
        tail.next=null;
    }return e1;
    }

删除任意一个节点代码如下：

public void delete(int e1)
    {//如果链表为空，直接返回if(!isEmpty())
    {//只有一个节点if(head==tail&&e1==head.info)
        head=tail=null;//多个节点else if(e1==head.info)//e1为表头节点        {
        head=head.next;
        }else{
        SingleLinkNode pred,tmp;for(pred=head,tmp=head.next;tmp!=null&&tmp.info!=e1;pred=pred.next,tmp=tmp.next)if(tmp!=null)
            {
            pred.next=tmp.next;//e1为尾节点if(tmp==tail)
                tail=pred;
            }
        }
        
    }
    }

三、查找

插入和删除都是修改链表，而查找只是扫描一个链表判断一个数据是否在链表内。和delete()函数的推理十分类似。可知在最好的情况下时间复杂度是O(1)，最坏的情况下是O(n)。

查找代码如下：

public boolean isInList(int e1)
    {
    SingleLinkNode tmp;    for(tmp=head;tmp!=null&&tmp.info!=e1;tmp=tmp.next);           return tmp!=null;
    }

对于单链表的基本操作的完整代码如下：

package com.linkedlist;public class SingleLinkedList {protected SingleLinkNode head,tail;    
public boolean isEmpty()
    {return head==null;
    }    public SingleLinkedList()
    {
    head=tail=null;
    }/* * 头插法     */public void addToHead(int e1){
    head=new SingleLinkNode(e1,head);if(tail==null)
        tail=head;
    }/* * 表中插入:在第i个节点之后添加节点     */public void addToList(int i,int e1)
    {
    SingleLinkNode p=head;int j=1;    while(p!=null&&(j<i))
    {
        p=p.next;
        j++;
    }if(p==null||j>i)       return;
    
    SingleLinkNode s=new SingleLinkNode(e1);
    s.next=p.next;
    p.next=s;
    }    /* * 尾插法     */public void addToTail(int e1){if(!isEmpty())
    {
        tail.next=new SingleLinkNode(e1);
            tail=tail.next;
    }else{
        head=tail=new SingleLinkNode(e1);
    }
    
    }    public int  deleteFromHead()
    {int e1=head.info;if(!isEmpty()){          if(head==tail)
            head=tail=null;          elsehead=head.next;
    }return e1;
    }    public int deleteFromTail()
    {int e1=tail.info;if(!isEmpty()){if(head==tail)
        head=tail=null;else{
        SingleLinkNode tmp;for(tmp=head;tmp.next!=tail;tmp=tmp.next)
        tail=tmp;
        tail.next=null;
    }
        
       }return e1;
    }    public void delete(int e1)
    {//如果链表为空，直接返回if(!isEmpty())
    {//只有一个节点if(head==tail&&e1==head.info)
        head=tail=null;//多个节点else if(e1==head.info)//e1为表头节点        {
        head=head.next;
        }else{
        SingleLinkNode pred,tmp;for(pred=head,tmp=head.next;tmp!=null&&tmp.info!=e1;pred=pred.next,tmp=tmp.next);if(tmp!=null)
            {
            pred.next=tmp.next;//e1为尾节点if(tmp==tail)
                tail=pred;
            }
        }
        
    }
    }    /* * 查找     */public boolean isInList(int e1)
    {
    SingleLinkNode tmp;    for(tmp=head;tmp!=null&&tmp.info!=e1;tmp=tmp.next);           return tmp!=null;
    }public void printAll(){    for(SingleLinkNode tmp=head;tmp!=null;tmp=tmp.next)
    {if(tmp.next==null)
        System.out.println(tmp.info);elseSystem.out.print(tmp.info+"->");
    }
    }    public static void main(String args[]){  
           int a[]=new int [10];  
           for(int i=0;i<a.length;i++){  
           a[i]=i;  
           }  
           SingleLinkedList list= new SingleLinkedList();           for(int i=0;i<a.length;i++)
           {
          list.addToHead(a[i]);   
           }
           System.out.println(" 链表输出如下：");  
           list.printAll();           //插入节点   list.addToList(2, 10);
           System.out.println(" 链表输出如下：");  
           list.printAll();           //删除节点   list.delete(10);
           list.printAll();
           System.out.println(" 插入元素后链表的输出如下：");  
         
             
   }  
}class SingleLinkNode {    public int info;//存储该节点的信息public SingleLinkNode next;//指向下一个节点的引用public SingleLinkNode(int info)
    {this(info,null);
    }/* * 初始化节点信息以及初始化下一个节点的引用     */public SingleLinkNode(int info,SingleLinkNode next)
    {this.info=info;this.next=next;
    }

}

上一篇：如何实现观察者模式和发布-订阅模式？

下一篇：链式表头插入和表尾插入 - I. 表头插入

链表的数据结构和算法 3 - 单向链表的插入、删除、修改和查找（Java 版）

一、插入操作

链表的数据结构和算法 3 - 单向链表的插入、删除、修改和查找（Java 版）

数据结构］单链表解释 + 完整代码（插入、删除、尾部插入、头部插入、按值和按位查找、前向插入和后向插入），包含和不包含头部节点的两种实现方式