Linked list with recursion

Question

Good morning, I'm learning and I want to make a Linked List with recursive function, I was looking for examples but I only found examples in Java or other types. From what I saw I suppose it would be something like that, but I can't get it to work. If someone could help me I would appreciate it very much. Thank you.

---

function ListRecurse () {
    this.head = null;
    this.size = 0;
}
function Node () {
    this.data = data; 
    this.next = next;
}
ListRecurse.prototype.add = function (data) {
    let NewNode = new Node(this.add(data), null)
    if (this.head === null) {
        this.head = NewNode;
    }
    else {
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current = NewNode
    }
    this.size ++;
}

---

Answer 1

There are several issues in your implementation:

1. Your use of recursion is going to lead to a stack overflow:

       let newNode = new Node(this.add(data));
   

   This will just keep calling itself without end. The code that you have below this statement will never be executed. Recursion always needs a base case, which will stop the recursion.

2. The Node constructor lacks parameters, so the variables data and next do not exist.

3. When assigning NewNode, you should not assign it to current, as that will break the list. You should assign it to current.next

With those problems fixed, it will work, but also take into account these remarks:

• Don't name variables with an initial capital, as it is common practice to reserve such notation for constructors (classes). So I would use the name newNode instead of NewNode
• Use default values for parameters which you might not use in a call. In your case you could give next a default value of null, so that you don't need to specify null in the call of Node.
• Use the modern class syntax for your constructors. It leads to cleaner code.
• Allow the add method to be chained. So make it return this.

So the recursive implementation could look like this:

class Node {
    // Accept arguments (the second one could be optional)
    constructor(data, next=null) {
        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
    }
}

let list = new ListRecurse();
list.add(1).add(2).add(3);
console.log(list);

The recursion now happens in this statement, which may need some explanation:

return this.next?.lastNode() || this;

This will check if the current node has a next node reference. If so, the recursive call to lastNode is made. If not, then we are in the "base case": the expression with the optional chaining operator (?.) is undefined and the OR operator (||) will then kick in to have this returned, since it is the final node in the chain.

More efficient

First, the use of recursion here might be a nice exercise, but it doesn't give much benefit. An iterative solution is fine.

It is a pity however that you need to walk along the whole linked list every time you want to add a node. As @Nina already answered, you can avoid this inefficiency by maintaining a reference to the tail node.

Answer 2

You could take the advantage of storing the last node and return this for have a fluent interface.

function ListRecurse() {
    this.head = null;
    this.last = null;
    this.size = 0;
}

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

ListRecurse.prototype.add = function(data) {
    const node = new Node(data, null);
    if (this.head === null) this.head = node;
    else this.last.next = node;
    this.last = node;  
    this.size++;
    return this;
}

const list = new ListRecurse().add(1).add(2).add(3);

console.log(list);

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