A Linked List in JavaScript
Tags: javascript
Published: 2018-11-30 13:04:34

---
title: A Linked List in JavaScript 
published: true
description: Implementing a linked list in JavaScript
tags: JavaScript
---

# Introduction

Hello dev.to!

There are [many great posts about linked lists on dev.to](https://dev.to/search?q=linked%20lists) 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](https://dev.to/hardy613/notes-on-ecmascript-6-es6-267l).

# 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](https://en.wikipedia.org/wiki/Linked_list#Basic_concepts_and_nomenclature).

# Getting started

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

```javascript
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.

```javascript
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](https://github.com/hardy613/es6-notes/blob/master/rest-parameters.md).
- 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.

```javascript
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 `head`s value
    - Set the current head to the previous `head`s `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`

```javascript
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).

```javascript
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 `head`s `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.

```javascript
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 `head`s 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.

```javascript
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
```javascript
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.

```javascript
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](https://github.com/hardy613/js-data-structures/blob/master/test/test.linked-list.js). 

As always, thanks for reading.