在Java中递归删除节点链表

2022-02-22 00:00:00 递归 linked-list java

我正在学习数据结构，并试图理解Java中的链表。我的问题是我在递归删除给定索引处的节点时遇到了问题。我的目标是得到O(Logn)，而不是使用循环，最终得到O(N)。

public class LinkedList {
    Node head;
    int index=0;
    Node temp;
    Node prev;
    public LinkedList(Node head){
        this.head=head;
        temp=head;
        prev=null;
    }
    public int length(){
        int counter=0;
        Node n= head.next;
        while(n!=null){
            counter=counter+1;
            n=n.next;
        }
        return counter;
    }
    public void push(Node newNode){
        newNode.next=head;
        head=newNode;
    }
    public void add(Node prevNode, int value){
        if(prevNode==null){
            System.out.println("The given previous node can not be null!");
            return;
        }
        Node newNode= new Node(value,null);
        newNode.next=prevNode.next;
        prevNode.next=newNode;
    }
    public void add(int index, int value){
        length();
        if((index<0)||(index>length())){
            System.out.println("Array out of bound!");
            return;
        }
        if(index==0){
            push(new Node(value,null));
            return;
        }
        Node newNode= new Node(value,null);
        Node prevNode=head;
            for(int i=1;i<index;i++){
            prevNode=prevNode.next;
        }
        newNode.next=prevNode.next;
        prevNode.next=newNode;
    }
    public void delete(){
        head=head.next;
    }
    public void delete(int index){
        if((index<0)||(index>length())){
            System.out.println("Array out of bound!");
            return;
        }
        if(index==0){
            delete();
        return;}
        if(head.next==null||head==null){
            head=null;
        return;}
        if(this.index!=index){
            this.index++;
            prev=temp;
            temp=temp.next;
            delete(index);
        }if(this.index==index){
            prev=temp.next;
        }
    }
    public void search(int value){
        if(head!=null){
        if(value!=head.value){
            head=head.next;
            index=index+1;
            search(value);
        }else if(value==head.value){
            System.out.println("The value ""+value+"" was found in index: "+index);}}}
    public void display(){
        Node n= head;
        System.out.print("{");
        while(n!=null){
            System.out.print(" ("+n.value+") ");
            n=n.next;
        }System.out.print("}");
        System.out.println("
------------------------------");
    }
    public static void main(String[]args){
        LinkedList ll= new LinkedList(new Node(2,null));
        ll.push(new Node(5,null));
        ll.push(new Node(6,null));
        ll.push(new Node(13,null));
        ll.push(new Node(1,null));
        ll.display();
        ll.add(ll.head.next,8);
        ll.display();
        ll.add(0, 0);
        ll.display();
        ll.add(6, 4);
        ll.display();
        System.out.println(ll.length());
        ll.search(13);
        ll.delete(2);
        ll.display();
    }
}

因此，当我尝试删除索引2处的条目时，它会删除该索引之前的所有数字，但不会删除该索引处的所有数字-因此它会删除[0]和[1]，但不会删除[2]。

例如，在此代码中，删除前的数组填充为：{0,1,13,8,6,5,4,2}。调用delete(2)后有以下条目：{13,8,6,5,4,2}

我只想删除13个，这样数组看起来就像这样：{0,1,8,6,5,4,2}

如果有任何改进代码的提示，我将不胜感激。

解决方案

链表中的JAVA递归删除方法

好的，让我们用一个例子来说明一下。它很简单，但是一旦您掌握了它的诀窍并理解了delete递归算法，您就可以轻松地制作generic样例类，负责封装，优化代码，然后继续生产。

本例中的类

出于示例目的，假设基本的单个LinkedList和Node类非常简单。内部静电Node类只存储原始int类型，并且它只包含对列表中以下Node元素的next引用。LinkedList只包括一个head节点，它是链表的开始。这不是双向链表，并且它没有对上一个节点的引用。遍历顺序是从给定的Node(通常是头节点)到next引用，一个接一个节点。我已经为两者添加了toString()实现，稍后会很方便：

public class LinkedList {

protected Node head;

public LinkedList(Node head) {
    super();
    this.head = head;
}

static class Node {

    protected int data;
    protected Node next;

    Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Node ");
        builder.append(data);
        if (null != next)
            builder.append(" -> ");
        return builder.toString();
    }
}

@Override
public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append("LinkedList [");
    Node node = head;
    while (node != null) {
        builder.append(node);
        node = node.next;
    }
    builder.append("]");
    return builder.toString();
}

}

实现递归删除方法

现在，让我们添加一个递归delete()方法。删除单链接列表中的节点只能通过将其从上一个节点的next引用取消链接来完成。该规则唯一的例外是head节点，我们要删除该节点为空。因此，很明显，我们需要(除了起点current node引用之外)对上一个节点的引用。

因此，我们的递归delete()方法签名可以是：

private LinkedList delete(Node node, Node prev, int key)

虽然此方法的返回类型可以完全省略(Void)，但它对支持链式功能非常有用，这样API调用就可以变成单行的、点分隔的语法，例如：

System.out.println(list.push(0).append(2).deleteAll(1));

因此，出于可链接性的考虑，我们还将从此方法返回对整个LinkedList实例的引用。根据参数列表：

第一个参数是当前节点，用于检查它是否与给定的key匹配。下一个参数是前一个节点，以防我们需要取消当前节点的链接。最后一个参数是我们要在所有要删除(取消链接)的节点中查找的键。

方法修饰符是private，因为它不打算公开使用。我们将把它包装在一个用户友好的facade方法中，该方法将以head作为当前节点，以null作为上一个节点开始递归：

public LinkedList deleteAll(int key) {
    return delete(head, null, key);
}

现在，让我们看看如何实现递归delete(...)方法，并从终止递归的两个基本条件开始：当前节点为空或列表中的单个节点，也就是head节点：

private LinkedList delete(Node node, Node prev, int key) {
    if (node == null)
        return this;
    if (node == head && head.data == key && null == head.next) { // head node w/o next pointer
        head = null;
        return this;
    }
    //...more code here
}

达到第一个基本条件意味着我们已经到达链表的末尾(是否找到key)，或者链表是空的。我们已完成，并返回对链表的引用。

第二个基本条件检查我们的当前节点是否是头节点，以及它是否与key匹配。在这种情况下，我们还检查它是否恰好是链表中的单个节点。在这种情况下，头节点需要"特殊"处理，并且必须被分配null才能被删除。当然，删除head节点后，列表为空，我们就完成了，因此我们返回对链接列表的引用。

下一个条件检查当前节点是否与key匹配，如果它是头节点，但不是列表中的唯一节点。

private LinkedList delete(Node node, Node prev, int key) {
    //...previous code here
    if (node == head && head.data == key) { // head with next pointer
        head = head.next;
        return delete(head, null, key);
    }
    //...more code here
}

我们稍后将优化此代码，但现在，在这种情况下，我们只需将对head的引用向前移动一步，因此head将被有效删除(旧引用将被垃圾收集)，并且我们将重新使用新的head作为当前节点，而null仍然是前一个节点。

下一个案例涉及与key：

匹配的常规(中间或尾部)节点

private LinkedList delete(Node node, Node prev, int key) {
    //...previous code here
    if (node.data == key) {
        prev.next = node.next;
        return delete(prev, null, key);
    }
    //...more code here
}

在这种情况下，我们通过将上一个节点的next指针从当前节点取消链接并将其分配给当前节点地址的下一个来删除当前节点。我们实质上"跳过"了当前节点，它变成了杂草。然后，我们循环使用上一个节点作为当前节点，并将NULL作为上一个节点。

在所有这些已处理的案例中，我们都有key的匹配项。最后，我们处理不匹配的情况：

private LinkedList delete(Node node, Node prev, int key) {
    //...previous code here
    return delete(node.next, node, key);
}

显然，我们重复使用下一个节点作为当前节点，将旧的当前节点作为上一个节点。在所有递归调用中，key保持不变。

整个(未优化)方法现在如下所示：

private LinkedList delete(Node node, Node prev, int key) {
    if (node == null)
        return this;
    if (node.data == key && node == head && null == node.next) { // head node w/o next pointer
        head = null;
        return this;
    }
    if (node.data == key && node == head) { // head with next pointer
        head = head.next;
        return delete(head, null, key);
    }
    if (node.data == key) { // middle / tail
        prev.next = node.next;
        return delete(prev, null, key);
    }
    return delete(node.next, node, key);
}

尾递归优化

许多编译器(包括javac)可以优化递归方法，如果它们使用尾递归的话。当递归调用是递归方法执行的最后一件事时，该方法就是尾递归方法。然后，编译器可以用简单的goto/label机制替换递归，并为每个递归帧节省运行时所需的额外内存空间。

我们可以轻松地优化递归delete(...)方法以符合要求。我们可以保留对当前node和前一个节点prev的引用，而不是递归地从每个已处理的条件(案例)返回，并在每个案例处理中为它们分配适当的值。这样，唯一的递归调用将发生在方法的末尾：

private LinkedList delete(Node node, Node prev, int key) {
    if (node == null)
        return this;
    if (node.data == key && head == node && null == node.next) { // head node w/o next pointer
        head = null;
        return this;
    }
    Node n = node.next, p = node;
    if (node.data == key && head == node) { // head with next pointer
        head = head.next;
        n = head;
        p = null;
    } else if (node.data == key) { // middle / tail
        prev.next = node.next;
        n = prev;
        p = null;
    }
    return delete(n, p, key);
}

要测试此递归方法：

我添加了一个简单的main测试驱动方法，通过facade方法deleteAll(...)测试delete(...)方法实现：

public static void main(String[] args) {
    LinkedList list = new LinkedList(new Node(0, new Node(1, new Node(1, new Node(2, new Node(2, new Node(3, null)))))));
    System.out.println(list);
    System.out.println(list.deleteAll(6));
    System.out.println(list.deleteAll(1));
    System.out.println(list.deleteAll(3));
    System.out.println(list.deleteAll(2));
    System.out.println(list.deleteAll(0));
}

输出(使用我提供的toString()方法)为：

LinkedList [Node 0 -> Node 1 -> Node 1 -> Node 2 -> Node 2 -> Node 3]
LinkedList [Node 0 -> Node 1 -> Node 1 -> Node 2 -> Node 2 -> Node 3]
LinkedList [Node 0 -> Node 2 -> Node 2 -> Node 3]
LinkedList [Node 0 -> Node 2 -> Node 2]
LinkedList [Node 0]
LinkedList []

虽然距离最初的帖子已经过去了3年，但我相信其他一些初学Java程序员(如果不是OP的话)会发现这个解释很有用。

相关文章