链表中的递归 [英] Recurse in Linked List

问题描述

我一直在练习链表，想在上面实现递归，虽然在某些情况下我能够有效地实现它，但在其他情况下我却很失败.我想知道一种进行递归的方法，以便不必使用while"为了遍历链表，我使用递归遍历数组，但是当我想在这种情况下进行类似的操作时，它失败了.

I have been practicing the linked list and wanted to implement the recurse on it, although in some cases I was able to implement it efficiently, in other cases I failed miserably at doing so. I would like to know a method to do the recursive so as not to have to use the "while" to go through the Linked List, I have used the recurse to go through the arrays but when I wanted to do it similar in this case it fails.

我在实现递归方面没有太多经验，并想在这种方法中应用它以获得更多使用它的经验，但至少它帮助我通过一遍又一遍地执行它来更多地理解链表.谢谢.

I don't have much experience in implementing recursion and wanted to apply it in this method to get more experience with it, but at least it helped me understand the Linked List more by having to do it over and over again. Thank you.

class Node {
    // Accept arguments (the second one could be optional)
    constructor(data, next) {
        this.data = data; 
        this.next = next;

    }
    lastNode() { // new method that uses recursion
        return this.next?.lastNode() || this;
    }
}
class ListRecurse {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    add(data) {
        let newNode = new Node(data); // No second argument. It has a default value
        if (this.head === null) {
            this.head = newNode;
        } else {
            // The lastNode implementation uses recursion:
            this.head.lastNode().next = newNode;
        }
        this.size ++;
        return this; // to allow chaining
    }
    insertAdd(data, index) {
        if (index < 0 || index > this.size) {
            return null;
        }
        let newNode = new Node(data);
        let current = this.head;
        let prev;
        if (index === 0) {
            newNode.next = current;
            this.head = newNode;
        }
        else {
            for (let i = 0; i < index; i++) {
                prev = current;
                current = current.next;
            }
            this.head.lastNode().next = current;
            prev.next = newNode;
        }
        this.size++;
        return this;
    }
    Print() {
        if (!this.size) {
            return null;
        }
        let current = this.head;
        let result = "";
        while(current) {
            result += current.data += "=>";
            current = current.next;
        }
        result += "X";
        return result;
        }
    DeletexData(data) {
           let current = this.head;
           let prev = null;
           if (this.head === null) {
               return null;
           }
           else if (current.data === data) {
               if(!prev) {
                   this.head = this.head.next;
               }
               else
               prev.next = current.next
           }
           return this.SearchDelete(data)
           }
    SearchDelete (data) {
            let current = this.head;
            let prev = null;
            while(current != null) {
                if (current.data === data) {
                    if (!current.next) prev.next = null
                else prev.next = current.next
                    this.size--;
                    return data;
                    }
                prev = current;
                current = current.next;
            }
        return null;
        }
    DeleteLastNode() {
        let current = this.head;
        if (current === null) {
            return 1
        }
        else if (current.next === null) {
            this.head = null;
        }
        else return this.LastNode()
        };
    LastNode() {
        let current = this.head;
        while (current.next.next != null) {
            current = current.next;
        }
        current.next = null;
        this.size--;
    }
    Search(data) {
        let current = this.head;
        if (current === null) {
            return null;
        }
        else 
        return this.RainbowSix(data)
    }
    RainbowSix(data) {
        let current = this.head; 
        while (current) {
            if (current.data === data) {
                return current;
            }
            current = current.next;
        }
        return null;
    }
    Size(){
        return this.size
    }
}
let list = new ListRecurse();
list.add(1).add(2).add(3).add(44).add(66);
list.insertAdd(33,0)
list.DeleteLastNode()
console.log(list.Search(3))
console.log(list.Size())
console.log(list.Print())
console.log(list);

推荐答案

这可能有帮助，也可能没有帮助.它提出了一种完全不同的方式来构建您的列表.

This may or may not help. It suggests a substantially different way to build your lists.

这个想法是递归，虽然偶尔用于面向对象 (OO) 系统，但与函数式编程 (FP) 的联系更紧密.因此，如果您打算在列表上使用递归，则不妨将其与 FP 列表一起使用.

The idea is that recursion, although occasionally used with Object-Oriented (OO) systems, is much more closely tied to Functional Programming (FP). So if you're going to use recursion on your lists, you might as well use it with FP lists.

创建和操作列表是 FP 的优势之一，我们可以更简单地编写您的代码.我们通过调用 const list1 = ins (42) (null) 创建了一个包含一项的裸列表，42.我们通过调用 const list2 = ins (17) (list1) 在它前面加上 17.或者我们可以像这样写一个完整的链:

Creating and manipulating lists is one of the strengths of FP, and we can write your code much more simply. We create a bare list of one item, 42 by calling const list1 = ins (42) (null). We prepend that with 17 by calling const list2 = ins (17) (list1). Or we can write a whole chain of these like this:

const list3 = ins (1) (ins (2) (ins (3) (ins (4) (ins (5) (null)))))

与您的代码有很多不同之处，但最基本的区别之一是它将列表视为不可变对象.我们的代码都不会改变一个列表，它只会创建一个具有改变属性的新列表.

There are many differences from your code, but one of the most fundamental, is that this treats lists as immutable objects. None of our code will change a list, it will just create a new one with the altered properties.

这就是 ins 的样子:

const ins = (data) => (list) => 
  ({data, next: list})

我们可以选择将其写为 (data, list) =>... 而不是 (data) =>(列表) =>....这只是个人对风格的偏好问题.

We could choose to write this as (data, list) => ... instead of (data) => (list) => .... That's just a matter of personal preference about style.

但基本结构是一个列表

• 一个值
• 紧随其后
  • 另一个列表
  • 或null

  以下是这些想法的实现:

  Here is an implementation of these ideas:

  const ins = (data) => (list) => 
    ({data, next: list})
  
  const del = (target) => ({data, next}) =>
    target == data ? next : next == null ? {data, next} : {data, next: del (target) (next)}  
  
  const delLast = ({data, next}) =>
    next == null ? null : {data, next: delLast (next)}
  
  const size = (list) => 
    list == null ? 0 : 1 + size (list.next)
  
  const search = (pred) => ({data, next}) => 
    pred (data) ? {data, next} : next != null ? search (pred) (next) : null
  
  const fnd = (target) => 
    search ((data) => data == target)
  
  const print = ({data, next}) => 
    data + (next == null ? '' : ('=>' + print (next)))    
  
  const list1 = ins (1) (ins (2) (ins (3) (ins (44) (ins (66) (null)))))
  const list2 = ins (33) (list1)
  const list3 = delLast (list2)
  
  console .log (fnd (3) (list3))
  console .log (size (list3))
  console .log (print (list3))
  console .log (list3)

  .as-console-wrapper {max-height: 100% !important; top: 0}

  注意所有这些函数，除了ins 和find 都是直接递归的.他们都自称.而 find 只是将递归工作委托给 search.

  Note that all of these functions, except for ins and find are directly recursive. They all call themselves. And find simply delegates the recursive work to search.

  试图描述所有这些功能太多了，但让我们看看两个.print 是一个简单的函数.

  It's too much to try to describe all of these functions, but lets look at two. print is a simple function.

  const print = ({data, next}) => 
    data + (next == null ? '' : ('=>' + print (next)))    
  

  我们通过包含我们的数据后跟以下两件事之一来构建我们的输出字符串:

  We build our output string by including our data followed by one of two things:

  • 一个空字符串，如果next是null
  • '=>' 加上 next 上的递归 print 调用，否则.
  • an empty string, if next is null
  • '=>' plus the recursive print call on next, otherwise.

  del 是一个稍微复杂一些的函数:

  del is a somewhat more complex function:

  const del = (target) => ({data, next}) =>
    target == data
      ? next 
      : next == null 
        ? {data, next: null} 
        : {data, next: del (target) (next)}  
  

  我们测试我们当前的数据是否是我们要删除的目标.如果是，我们只需返回存储为 next 的列表.

  We test if our current data is the target we want to delete. If it is, we simply return the list stored as next.

  如果不是，我们检查next是否为空.如果是，我们返回(副本)当前列表.如果不是，那么我们返回一个由当前数据形成的新列表，并递归调用以从存储为 next 的列表中删除目标.

  If not, we check whether next is null. If it is, we return (a copy of) the current list. If it is not, then we return a new list formed by our current data and a recursive call to delete the target from the list stored as next.

  如果您想了解更多关于这些想法的信息，您可能需要搜索缺点列表"；(这里的con"不是pro"的反义词，而是与构造"某物有关.)

  If you want to learn more about these ideas, you probably want to search for "Cons lists" ("con" here is not the opposite of "pro", but has to do with "construct"ing something.)

  我使用了与那里最常用的术语不同的术语，但想法大致相同.如果您遇到术语 car 和 cdr，它们分别相当于我们的 data 和 next.

  I used different terms than are most commonly used there, but the ideas are much the same. If you run across the terms car and cdr, they are equivalent to our data and next, respectively.

  这篇关于链表中的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！