Creating linked list using JavaScript objects

Linked lists can be better choice when changing the data is a more frequent operation than accessing the data. For example, let's say sales data for a company has to be updated every day while sales report is generated only once a month.

Advantages of Linked List

• Adding and removing items is quicker($O(1)$ time) than arrays($O(n)$ time).
• No requirement of contiguous memory availability.

Some downsides

• Reading an element takes $O(n)$ time.
• Binary search cannot be used.

Creating linked list

Linked list consist of nodes where each node has two pieces of information, 1) the data stored in the node and 2) pointer to the next node. This is a good fit for object implementation. We will also create a function that can be used to append an item to the end of the list (noting that the last node always points to null).

After defining the constructor, we can define methods associated with the constructor using protoype keyword in function definitions. The append method in the following example is creating using this approach.

// linked.js -- implementing linked-list in JavaScript
function LLNode(data){
    this.data = data;
    this.next = null;
}

var head = new LLNode();  // declare an empty linked list
console.log(head);

LLNode.prototype.append = function(x) // writing method for LLNode using prototype
{
    if (head.data == undefined) // if empty, set head to x
    {
        head.data = x;
        return;
    }
    var tmp = head;
    while (tmp.next != null)
        tmp = tmp.next;
    tmp.next = new LLNode(x);
};

head.append(33); // calling append method on head
head.append(64);
head.append(69);
console.log(head);

Output

LLNode { data: undefined, next: null }
LLNode {
  data: 33,
  next: LLNode { data: 64, next: LLNode { data: 69, next: null } }
}