Question

IMPLEMENT AN IMMUTABLE SINGLY LINKED LIST IN JAVASCRIPT

-------------------------------------------------------------------------------------------------------------------------

So I am trying to implement a singly linked list that given the below function will pass the bottom four tests when ran.

Please help me generate the singly linked list that will work and pass the tests. I will only use this as a reference so please add comments to explain what you are doing so I can understand and write this myself. I think a join method may need to be used in the linked list section but i'm not sure.

I am currently using node.js to run and test this code and called 'runTests()' to test it.

--------------------------------

FUNCTION

--------------------------------

function join(list, delim) {
var retval = "[";
while (list instanceof Cons &&
!(list.tail() instanceof Nil)) {
retval += list.head().toString() + delim;
list = list.tail();
}
if (list instanceof Cons) {
retval += list.head().toString();
}
retval += "]";
return retval;
} // join

___________________

LINKED LIST WOULD BE HERE TECHNICALLY

-------------------------------

--------------------------------

TESTS THE LIST SHOULD PASS

--------------------------------

function runTest(test) {
process.stdout.write(test.name + ": ");
try {
test();
process.stdout.write("pass\n");
} catch (error) {
process.stdout.write("FAIL\n");
console.log(error);
}
} // runTest
  
function assertEquals(expected, received) {
if (expected !== received) {
throw ("\tExpected: " + expected.toString() + "\n" +
"\tReceived: " + received.toString());
}
} // assertEquals

function test_nil_join() {
let nil = new Nil();
assertEquals("[]",
nil.join(", "));
} // test_nil_join

function test_nil_toString() {
let nil = new Nil();
assertEquals("[]",
nil.toString());
} // test_nil_toString

function runTests() {
// ---begin tests for nil---

// instanceof
runTest(test_nil_instanceof_list);

// join
runTest(test_nil_join);

// toString
runTest(test_nil_toString);

} //runTests()

Answer 1

class Node{
    constructor(data, next = null){
        this.data = data,
        this.next = next
    }
}

// In the above code, a Node class is defined. When an instance of the Node class is formed, the constructor function will be called to initialize the object with two properties, data and a pointer named next. The pointer next is initialized with a default value of null, incase no value is passed as an argument.

class LinkedList{
    constructor(){
        this.head = null;
    }
        
        insertAtBeginning = (data) => {
                // A newNode object is created with property data and next = null
                let newNode = new Node(data);
                // The pointer next is assigned head pointer so that both pointers now point at the same node.
                newNode.next = this.head;
                // As we are inserting at the beginning the head pointer needs to now point at the newNode. 
    
                this.head = newNode;
                return this.head;
        }
        
        insertAtEnd = (data) => {
                // A newNode object is created with property data and next=null
    
                let newNode = new Node(data);
                // When head = null i.e. the list is empty, then head itself will point to the newNode.
                if(!this.head){
                        this.head = newNode;
                        return this.head;
                }
                // Else, traverse the list to find the tail (the tail node will initially be pointing at null), and update the tail's next pointer.
                let tail = this.head;
                while(tail.next !== null){
                        tail = tail.next;
                }
                tail.next = newNode;
                return this.head;
        }
        
        // A helper function getAt() is defined to get to the desired position. This function can also be later used for performing delete operation from a given position.
    getAt = (index) => {
        let counter = 0;
        let node = this.head;
        while (node) {
            if (counter === index) {
               return node;
            }
            counter++;
            node = node.next;
        }
        return null;
    }
        
        // The insertAt() function contains the steps to insert a node at a given index.
    insertAt = (data, index) => {
                // if the list is empty i.e. head = null
                if (!this.head) {
                        this.head = new Node(data);
                        return;
        }
                // if new node needs to be inserted at the front of the list i.e. before the head. 
        if (index === 0) {
                        this.head = new Node(data, this.head);
                        return;
        }
                // else, use getAt() to find the previous node.
                const previous = this.getAt(index - 1);
        let newNode = new Node(data);
        newNode.next = previous.next;
        previous.next = newNode;       

        return this.head
        }
        
        
        deleteFirstNode = () => {
                if(!this.head){
                        return;
                }
                this.head = this.head.next;
                return this.head;
        }
        
        deleteLastNode = () => {
                if(!this.head){
                        return null;
                }
                // if only one node in the list
                if(!this.head.next){
                        this.head = null;
                        return;
                }
                let previous = this.head;
                let tail = this.head.next;
   
                while(tail.next !== null){
                        previous = tail;
                        tail = tail.next;
                }
   
                previous.next = null;
                return this.head;
        }
        
        deleteAt = (index) => {
                // when list is empty i.e. head = null
                if (!this.head) {
                        this.head = new Node(data);
                        return;
                }
                // node needs to be deleted from the front of the list i.e. before the head.
                if (index === 0) {
                        this.head = this.head.next;
                        return;
                }
                // else, use getAt() to find the previous node.
                const previous = this.getAt(index - 1);
    
                if (!previous || !previous.next) {
                        return;
                }
    
                previous.next = previous.next.next;     
                return this.head
        }
        
        // Delete the complete linked list
        deleteList = () => {
                this.head = null;
        }
        
}


// A list object is created with a property head, currently pointing at null

let list = new LinkedList();

// Insert xyz as data in the beginning of the list
list.insertAtBeginning('xyz');

// Use the remaining functions the same way :)