A Linked List in JavaScript

Introduction

Hello dev.to!

There are many great posts about linked lists on dev.to and this one will be about implementing a linked list in JavaScript with base features: length, unshift, shift, remove by value, find also by value and get by index. Then we'll add a few other features: map, reduce, and filter.

This post will use ECMAScript6.

What is a linked list

A linked list is a collection of data, where each node points to the next node instead of using their placement in memory. The most basic form of a linked list is a Singly Linked List where the node contains only a value and next property. We'll implement a singly linked list, however other types of linked lists do exist.

Getting started

We can start with a class and our main method unshift.

class LinkedList {
    constructor(value) {
        this.head = null
        this.length = 0
        return this.unshift(value)
    }

    unshift(value) {
        const node = { value }
        node.next = this.head
        this.head = node
        this.length += 1
    }
}

const list = new LinkedList('test')
console.log(list) // LinkedList {head: "test", length: 1, next: null} 

Our constructor initializes two properties head and length.

• head points to the first node in the list
• length will keep track of how many items are added
• unshift creates a new node
  • Sets next to the previous head node
  • Sets the head to the new node
  • Increases the length

Now we can initialize an empty list and a list with one value. Let's make a small change to allow multiple values for the constructor and unshift. To do that effectively we can make a method for adding one value and use in our unshift method that will accept multiple values.

class LinkedList {
    constructor(...values) {
        this.head = null
        this.length = 0
        return this.unshift(...values)
    }

    _unshiftOneValue(value) {
        const node = { value }
        node.next = this.head
        this.head = node
        this.length += 1
    }

    unshift(...values) {
        values.forEach(value => this._unshiftOneValue(value))
        return this
    }
}

Our constructor and unshift accept multiple values with rest parameters.

• The constructor will pass the values on to unshift
• unshift iterates with Array.forEach over the values - Adding them with our new method _unshiftOneValue
• _unshiftOneValue adds one value and increments the length

Returning this allows us to chain the method as well.

Adding a shift starts with making sure we have an item to remove, null otherwise.

class LinkedList {

    // ...

    shift() {
        if (this.length === 0) {
            return null
        }
        const { value } = this.head
        this.head = this.head.next
        this.length -= 1
        return value
    }
}

• Return null without a length
• If we have a head
  • Grab the heads value
  • Set the current head to the previous heads next
  • Decrease the length
• Return the value removed.

find by value

So far we've been returning a value or null, let's keep with that design pattern. Our find will:

• Accept one value.
• Return null or the found value

class LinkedList {

    // ...

    find(value) {
        let node = this.head
        while (node) {
            if (node.value === value) {
                return node
            }
            node = node.next
        }
        return node
    }
}

We set node to the head which we set to null in the constructor.

• While we have a node
• If the node.value strictly matches the value parameter
  • Return the node
• Set node.next as the next node
• Return the node

node.next is null if it is not there. If we have nodes and the value parameter is not found we still return null.

remove by value

A linked list is like a chain and to remove a value we'll need the previous node and the current nodes next. If we find the node as the head then we can reuse our shift method. We don't need to return the value removed because it is known from the author's integrating with our list. Let's return the new list (or the same list if nothing is removed).

class LinkedList {

    // ...

    remove(value) {
        if (this.length === 0) {
            return this
        }

        if (this.head.value === value) {
            this.shift()
            return this
        }
        let prevNode = this.head
        let node = prevNode.next
        while (node) {
            if (node.value === value) {
                break
            }
            prevNode = node
            node = node.next
        }

        if (node === null) {
            return this
        }
        prevNode.next = node.next
        this.length -= 1
        return this
    }
}

• If we have no list, return this.
• If the value is the head
  • Use shift
  • Return this
• The previous node becomes the head
• The node to compare is set to the heads next
• While we have a node
  • If The nodes value strictly matches the value
    • break out of the loop
  • Set the previous node to the node
  • Set node to node.next
• If our node is null then return this
• Set the previous nodes next to found nodes next - removing the found node
• Decrease the length
• Return this

get by index

We have enough information about our linked list that we do not need to add an index property to each node. A Singly linked list always starts a search at the head (index 0) and moves on to the next node. A single parameter is required and must be a Number equal to or greater than 0 but less than our length property.

class LinkedList {

    // ...
    get(index = 0) {
        if (this.length === 0 || Number.isNaN(index)
            || index < 0 || this.length <= index) {
            return null
        }

        if (index === 0) {
            return this.head
        }
        let node = this.head.next
        let i = 1
        while (node) {
            if (i === index) {
                return node
            }
            node = node.next
            i += 1
        }
        return null
    }
}

• Return null if
  • We don't have a length
  • index is not a number
  • index is less than 0 (out of bounds)
  • index is greater or equal to our length (out of bounds)
• If index is 0 return the head
• Set node to the heads next
• Set i to 1 (our nodes position)
• While we have a node
  • If i is strictly equal to index return the node
  • Set our next node to node.next
  • Increment i by one
• Return null

reduce

We'll follow the same implementation in arrays. Execute a reducer function on each value of the list resulting in a single output value. The reducer function has four parameters:

• Accumulator - accumulates the callback's return values
• Current Value - the value being processed
• Current Index - Starts at 0 with an initialValue, 1 otherwise.
• Source - the list being reduced

The reducer function will also accept a starting initialValue as the second parameter.

class LinkedList {

    // ...
    reduce(func = () => {}, initialValue) {
        if (this.length === 0 || typeof func !== 'function') {
            return typeof initialValue !== 'undefined' ? initialValue : null
        }
        let node = this.head
        let acc = initialValue
        let i = 0
        while (node) {
            if (typeof acc === 'undefined') {
                acc = node.value
                node = node.next
                i += 1
            }
            acc = func(acc, node.value, i, this.head)
            node = node.next
            i += 1
        }
        return acc
    }

}

• Return the initialValue (if defined) or null
  • If the length is 0
  • If the reducer function is not a function
• Set the node to the head
• Set the accumulator as the initialValue
• Set i to 0
• While we have a node
  • If the accumulator is undefined
    • Set the accumulator as the value
    • Set the current node to node.next
    • Increment i by 1
  • Set the accumulator as the result of the reducer
  • Set the node to node.next
  • Increment i by 1
• Return the accumulator

map

map has two approaches, one is recursive and one is imperative. We will do both.
Just as we did with reduce let's also follow the arrays implementation. map will create a new list with the results of calling a provided function on every element in the calling list. The Provided function has three arguments

• CurrentValue - The current element being processed in the array
• Index - The index of the current element being processed in the array
• Array - The array map was called upon

class LinkedList {

    // ...
    mapRecursive(func = () => {}) {
        if (this.length === 0 || typeof func !== 'function') {
            return new LinkedList()
        }
        let i = -1
        const _map = (node, list) => {
            if (node.next) {
                _map(node.next, list)
            }
            i += 1
            return list.unshift(func(node.value, i, this.head))
        }
        return _map(this.head, new LinkedList())
    }

    map(func = () => {}) {
        if (this.length === 0 || typeof func !== 'function') {
            return new LinkedList()
        }
        const list = new LinkedList()
        let node = this.head
        let i = 0
        while (node) {
            list.unshift(func(node.value, i, this.head))
            i += 1
            node = node.next
        }
        return list
    }


}

filter

filter will be just like map in that we'll do both recursive and imperative while following the array implementation of filter. filter will create a new list with all elements that pass the test implemented by the provided function. The provided function has three arguments:

• Element - The current element being processed in the array
• Index - The index of the current element being processed in the array
• Array - The array filter was called upon.

class LinkedList {

    // ...
    filterRecursive(func = () => {}) {
        if (this.length === 0 || typeof func !== 'function') {
            return new LinkedList()
        }
        let i = -1
        const _filter = (node, list) => {
            if (node.next) {
                _filter(node.next, list)
            }
            i += 1
            if (func(node.value, i, this.head)) {
                return list.unshift(node.value)
            }
            return list
        }
        return _filter(this.head, new LinkedList())
    }

    filter(func = () => {}) {
        if (this.length === 0 || typeof func !== 'function') {
            return new LinkedList()
        }
        const list = new LinkedList()
        let node = this.head
        let i = 0
        while (node) {
            if (func(node.value, i, this.head)) {
                list.unshift(node.value)
            }
            i += 1
            node = node.next
        }
        return list
    }
}

• Return a new list
  • If there is no length
  • If the parameter is not a function
• Create a new list
• Set node to head
• Set i to 0
• While we have a node
  • If the nodes value passes the test
    • Add the node to the new list
  • Increment i
  • Set node to node.next
• Return the list

Conclusion

We now have a linked list with a bunch of added features!

If you wanted to you could also write tests for the list.

As always, thanks for reading.