Understanding linked lists (listNode) in JavaScript

A simple linked list is a data structure that works like an array, but the elements haven't an index.

For example:

terminal
┌────────┐   ┌────────┐   ┌────────┐   ┌────────┐
|   3    |-->|   4    |-->|   2    |-->|   7    |
└────────┘   └────────┘   └────────┘   └────────┘

If you represent the previous structure as an object:

javascript
let list = {
    val: 3,
    next: {
        val: 4,
        next: {
            val: 2,
            next: {
                val: 7,
                next: null
            }
        }
    }
}

As you can see, a list is an object that contains multiple layers of data. Every layer on the list has a value and a next property. The next property contains a linked list (an object with val and next properties).

If you print the first element:

javascript
console.log(list.val)  // 3
console.log(list.next) // {val: 4, next: { val: 2, next: {...} }}

The formal definition of a node is:

javascript
function ListNode(val, next) {
    this.val  = val  === undefined ? 0    : val
    this.next = next === undefined ? null : next
}

You could create the previous object defining each node:

javascript
// This is equivalent to: let list = {val: 3, next: {...} }
let list = new ListNode(3, new ListNode(4, new ListNode(2, new ListNode(7))))

When to use this structure?

Maybe you are wondering why to use this structure if you could use an array rather than a linked list:

javascript
let list = [3, 4, 2, 7]

They are useful if you want to add or delete data. For example, in the previous array, let's assume that you wanted to add a 9 at index = 1.

javascript
let list  = [3, 4, 2, 7]
let index = 1

for(let i = list.length; i >= index; i --){
    list[i] = list[i - 1]
}

list[index] = 9

console.log(list) 
// [3, 9, 4, 2, 7]

Whereas if you use a linked list:

javascript
let list = {
    val: 3,
    next: {
        val: 4,
        next: {
            val: 2,
            next: {
                val: 7,
                next: null
            }
        }
    }
}

let _list = list.next

list.next.val  = 9
list.next.next = _list

console.log(list)
// {val: 3, next: {val: 9, next: {... }}}

In the first example, you are writing 4 new values. In the last example, you only write 1 new value while redirecting the pointers. That's why modifying an array has a time complexity of O(n), whereas modifying the linked list has a time complexity of O(1).