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

Question

Okay so I'm learning Data Structures where my tutorial is following class syntax. So now I am trying to convert it to function declarations as I want to practice Linked Lists with that notation. Can anybody help me with the conversion? I need only one method to be converted and I'll be able to do the rest of them.

Here's the code I have with class syntax:

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' );

Here's what I tried so far to achieve function-based approach:

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()

This is what I could achieve so far. And I'm stuck with it and I don't know what to do next. Someone please help

Answer 1

functional heritage

The linked list is a functional structure and so using it with functional style yields the best results. This means avoiding things like mutation and variable reassignments. Below we implement a functional-style immutable linked list in an object-oriented interface -

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))

Notice how each call to .push returns a new, unmodified list -

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

modules preferred, classes optional

But I think you can do a lot better than that. By mixing functional designs and concerns directly with class-oriented semantics, we end up with strange and often inefficient programs. In functional style we write modules with ordinary functions. If an object-oriented interface is desired, only a thin wrapper around our plain functions is needed -

// 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 }

In your main module we will import list from our list module -

// 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 -> ∅

Expand the snippet below to verify the results in your browser -

// 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))