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)