无法将 class 语法转换为链接列表的函数语法

Question

好的，我正在学习数据结构，我的教程遵循 class 语法。所以现在我试图将它转换为 function 声明，因为我想用该符号练习链接列表。有人可以帮我转换吗？我只需要转换一种方法，其余的我就能完成。

这是我使用 class 语法的代码：

class Node {
    constructor( val ) {
        this.val = val;
        this.next = null;
    }
}

class SinglyLinkedList {
    constructor () {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    push( val ) {
        const newNode = new Node( val );

        if ( !this.head ) {
            this.head = newNode;
            this.tail = this.head;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.length++
        return this;
    }

}

const list = new SinglyLinkedList();

list.push( 'HELLO' );
list.push( 'WORLD' );

这是我迄今为止为实现基于函数的方法所做的尝试：

function Node( val ) {
  this.val = val;
  this.next = null;
}

let head = null;
let tail = null;
let length = 0;

const SinglyLinkedListFunc = function() {
    const newNode = new Node( 'HELLO' );
};

SinglyLinkedListFunc()

这是我目前所能达到的。我被它困住了，我不知道下一步该怎么做。有人请帮忙

Answer 1

功能方法如下：

function Node( val, next ) {
  this.val = val;
  this.next = null;
}
 
const SinglyLinkedListFunc = function() {
    this.head = null;
    this.tail = null;
    this.length = 0;
};

SinglyLinkedListFunc.prototype.push = function( val ) {

  const newNode = new Node( val );

  if( !this.head ){
    this.head = newNode;
    this.tail = newNode;
  } else{
    this.tail.next = newNode;
    this.tail = newNode;
  }

    this.length++;
    return this;
}


let list = new SinglyLinkedListFunc();
list.push('HELLO');
list.push('WORLD');

Answer 2

功能性遗产

链表是一种函数式结构，因此以函数式风格使用它会产生最好的结果。这意味着要避免诸如突变和变量重新分配之类的事情。下面我们在面向对象的接口中实现一个函数式风格的不可变链表-

class Node {
  constructor(head, tail) {
    this.head = head
    this.tail = tail
  }
}

const empty = Symbol("empty")
  
class List {
  constructor(t = empty) {
    this.t = t
  }
  push(v) {
    return new List(new Node(v, this.t))
  }
  toString() {
    if (this.t == empty)
      return "∅"
    else
      return `${this.t.head} -> ${new List(this.t.tail)}`
  }
}

const l = (new List).push("a").push("b").push("c")
console.log(String(l))
console.log(String(l.push("d").push("e").push("f")))
console.log(String(l))

注意每次调用 .push returns 一个新的、未修改的列表 -

c -> b -> a -> ∅
f -> e -> d -> c -> b -> a -> ∅
c -> b -> a -> ∅

首选模块，class可选

但我认为你可以做得更好。通过将功能设计和关注点直接与面向 class 的语义混合，我们最终会得到奇怪且通常效率低下的程序。在函数式风格中，我们编写具有普通函数的模块。如果需要一个面向对象的接口，只需要一个简单的包装器来包裹我们的普通函数 -

// list.js
const empty = Symbol("empty")

const pair = (left, right) =>
  ({ left, right })

const push = (t, v) =>
  pair(v, t)

const list = (...args) =>
  args.reduce(push, empty)

const toString = t =>
  t == empty
    ? "∅"
    : `${t.left} -> ${toString(t.right)}`
  
class List {
  constructor(t = empty) { this.t = t }
  static empty() { return new List() }
  static of(...args) { return new List(list(...args)) }
  push(v) { return new List(push(this.t, v)) }
  toString() { return toString(this.t) }
}

export { default:List, empty, pair, push, list, toString }

在您的 main 模块中，我们将从 list 模块导入 list -

// main.js
import List from "./list.js"

const l = List.empty().push("a").push("c").push("d")
console.log(String(l))
console.log(String(l.push("d").push("e").push("f")))
console.log(String(l))

c -> b -> a -> ∅
f -> e -> d -> c -> b -> a -> ∅
c -> b -> a -> ∅

展开下面的代码片段以在浏览器中验证结果 -

// list.js
const empty = Symbol("empty")

const pair = (left, right) =>
  ({ left, right })

const push = (t, v) =>
  pair(v, t)

const list = (...args) =>
  args.reduce(push, empty)

const toString = t =>
  t == empty
    ? "∅"
    : `${t.left} -> ${toString(t.right)}`
  
class List {
  constructor(t = empty) { this.t = t }
  static empty() { return new List() }
  static of(...args) { return new List(list(...args)) }
  push(v) { return new List(push(this.t, v)) }
  toString() { return toString(this.t) }
}

// main.js
const l = List.empty().push("a").push("c").push("d")
console.log(String(l))
console.log(String(l.push("d").push("e").push("f")))
console.log(String(l))

无法将 class 语法转换为链接列表的函数语法

Unable to convert class syntax to function syntax for a Linked List

javascript

algorithm

linked-list

data-structures

singly-linked-list