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
 Sets
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 tounshift

unshift
iterates withArray.forEach
over the values  Adding them with our new method_unshiftOneValue

_unshiftOneValue
adds one value and increments thelength
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 alength
 If we have a
head
 Grab the
head
s value  Set the current head to the previous
head
snext
 Decrease the
length
 Grab the
 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 foundvalue
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 thevalue
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 thehead
 Use
shift
 Return
this
 Use
 The previous node becomes the
head
 The node to compare is set to the
head
snext
 While we have a node
 If The nodes
value
strictly matches thevalue

break
out of the loop

 Set the previous node to the node
 Set node to
node.next
 If The nodes
 If our node is
null
then returnthis
 Set the previous nodes
next
to found nodesnext
 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 ourlength
(out of bounds)
 We don't have a
 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 toindex
return the node  Set our next node to
node.next
 Increment
i
by one
 If
 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) ornull
 If the
length
is 0  If the reducer function is not a function
 If the
 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
 If the accumulator is
 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
 If the nodes
 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.
Top comments (0)