链接列表中的递归 [英] 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 是否为null.如果是，我们返回当前列表(的副本).如果不是，则返回由当前数据形成的新列表，并递归调用以从存储为 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屋！