An Introduction to Data Structures in JavaScript
Photo by JJ Ying on Unsplash
What?s the best way to store data in a list? In computer science courses, linked lists are one of the first data structures learners encounter. They?re an abstract data type, in which each element points to the next one and ? in theory ? that brings certain advantages for performance.
There?s plenty of information about linked lists in lower-level languages like C and C++, where they?re more likely to be applied. But, in this article, I want to make this information more accessible to others ? like self-taught developers or bootcampers ? who are more comfortable working in higher-level, web development languages like JavaScript.
Will I Ever Need to Implement a Linked List in JavaScript?
This may seem like a strange answer for an article dedicated to the subject ? but no, you probably won?t.
In theory, linked lists should be faster than arrays in certain situations, such as inserting new items. But, in practice, they?re not. That?s because arrays are highly optimised by JavaScript engines like Google?s V8, written in C++. Unless linked lists were introduced to the ECMAScript specification and given the same kind of optimisations, arrays (or Sets) remain the fastest choices.
So, Why Bother?
Well, as JavaScript becomes the language of choice for more and more programmers, it seems appropriate that important computer science topics should be explained in a language people are comfortable with.
Going through this process has helped deepen my knowledge of the kind of considerations and trade-offs that go into making a library, compiler or even an entire programming language. This knowledge can help us make better decisions in our production code, even if we?re not using linked lists.
Plus, this popular npm package has over 50,000 weekly downloads, so there?s clearly some demand!
What?s the Difference Between an Array and a Linked List?
Both an array and a linked list are ordered collections of data, but ? at scale ? one offers more efficient access to data and the other offers more efficient insertion. There may be other differences, depending on the implementation, but those are the most significant.
Array
Each item in an array has a number attached to it, called a numeric index, that allows you to access it. This makes accessing elements very efficient.
Say we had a list of four strings, ‘A’ , ‘B’ , ‘C’ and ‘D’ . If we were to structure this list as an array, it would look like this:
| Value: | ‘A’ | ‘B’ | ‘C’ | ‘D’ ||——–|——|——|——|——|| Index: | 0 | 1 | 2 | 3 |
Linked List
Instead of using a numeric index, each element points to the next element. We don?t have to update the numeric index each time we insert or delete an element. In particular, inserting elements into linked lists is more efficient than inserting elements into arrays.
Here?s what our list would look like, structured as a linked list:
| Value: | ‘A’ | ‘B’ | ‘C’ | ‘D’ ||——–|——|——|——|——|| Next: | ‘B’ | ‘C’ | ‘D’ | null |
So, how do we go about implementing a linked list in JavaScript? Oleksii Trekhleb?s brilliant JavaScript Algorithms repository has a good implementation. In this article, we?ll be using Trekhleb?s implementation as the foundation of our own linked list, but we?ll be changing it in a few significant ways, by?
- adding an additional method (includes),
- adding an additional property (size), and by
- making some of Trekhleb?s existing methods (such as the constructor function) more versatile.
Before we get into the code, open up a new folder in your favourite IDE and create three new JavaScript files: index.js , LinkedList.js and LinkedListNode.js . It?s good practice to keep our LinkedList and the individual nodes as separate classes, so first we?ll build our node class, so we?ll start in LinkedListNode.js .
Part 1: Class Constructors
LinkedListNode
Each node needs to hold its own value and the value of the next node in the list, so we can specify each as a property in our class constructor:
class LinkedListNode { constructor(value, next) { this.value = value; this.next = next || null; }}module.exports = LinkedListNode
That?s all we need for our LinkedListNode class! Back in index.js , we can import our new class and try it out:
const LinkedListNode = require(‘./LinkedListNode’);console.log(new LinkedListNode(3));console.log(new LinkedListNode(3, 10));console.log(new LinkedListNode(‘string’, true));
LinkedList Constructor
Now, let?s move into LinkedList.js , which is going to be a much bigger class. We?ll begin working on the constructor. We want to hold the first entry (the head) and the final entry (the tail) in memory, which are null by default.
For this implementation, I?d also like to keep the list?s size in memory, so it?s easy to find out how many items are in the list at any one time:
const LinkedListNode = require(‘./LinkedListNode’);class LinkedList { constructor() { this.size = 0; this.head = null; this.tail = null; }}module.exports = LinkedList
Note that all the following code ? unless otherwise specified ? will be inside the LinkedList class.
Part 2: Adding New Entries
prepend
Before we can test our new class, we?ll need a way to add new values. We?ll start with a prepend method to add values to the front of the list, similar to Array.unshift :
prepend(value) { this.size += 1; const newNode = new LinkedListNode(value, this.head); this.head = newNode; if (!this.tail) this.tail = newNode; return this;}
- First, we define a new node, based on the value provided and the current head node.
- Then, we update the head to equal this new node.
- Third, if no tail has been specified (because this is the first item in the list), then the head and tail should be the same.
- Finally, we use this to return the whole LinkedList .
append
We?ll also want a way to add elements to the end of the list, similar to Array.push . There are a few more steps necessary to do this:
append(value) { this.size += 1; const newNode = new LinkedListNode(value); if (!this.head) { this.head = newNode; this.tail = newNode; return this; }; this.tail.next = newNode; this.tail = newNode; return this;}
- We start by creating a new LinkedListNode as before, but this time we don?t need to specify a second argument (as there is no next value).
- If this is the first element in the list, we?ll also want to update this.head and we can return the function early.
- Finally, we need to change the next property of the current final node, before inserting our newNode at the end.
To see what?s going on, I recommend going back into index.js to try adding values to our list.
Part 3: Converting To and From an Array
For convenience, it should be possible to provide an array in the constructor and get a LinkedList of items in that order ? similar to the Set constructor.
fromArray
First, let?s create a fromArray method, where we append each item in the array:
fromArray(values) { values.forEach(value => this.append(value)); return this;}
constructor
Next, we can trigger our new method back in the constructor :
constructor(value) { this.size = 0; this.head = null; this.tail = null; if (value) { if (Array.isArray(value)) return this.fromArray(value); return new TypeError(value + ‘ is not iterable’); }; return this;}
If an array is passed, we run the fromArray method. If a value other than an array is passed, we return a TypeError . And if no value is provided, we set this.head and this.tail as null , like before.
toArray
We?ll also want a way to turn our linked list back into an array.
toArray(useNodes = false) { const nodes = ; let currentNode = this.head; while (currentNode) { nodes.push(useNodes ? currentNode : currentNode.value); currentNode = currentNode.next; }; return nodes;}
This method contains an argument named useNodes , which ? when true ? will fill the array with each LinkedListNode object, rather than just the value, which could be helpful for debugging.
Back in index.js , we can test the differences:
const LinkedList = require(‘./LinkedList’);let list = new LinkedList([1, 2, 3]);console.log(list.toArray());console.log(list.toArray(true));
Part 4: Deleting Entries
delete
The delete operation is the most complex of any of our linked list methods, as it requires slightly different steps, depending on whether the head, tail or any other node needs to be deleted.
By default, our function will delete all nodes of a certain value. But we can pass true as our second argument to just delete the first node we encounter with the given value.
delete(value, deleteOne = false) { if (!this.head) return false; let deletedNode = null; // If the head needs to be deleted while (this.head && this.head.value === value) { this.size -= 1; deletedNode = this.head; this.head = this.head.next; if (deleteOne) return true; }; let currentNode = this.head; // If any node except the head or tail needs to be deleted if (currentNode !== null) { while (currentNode.next) { if (currentNode.next.value === value) { this.size -= 1; deletedNode = currentNode.next; currentNode.next = currentNode.next.next; if (deleteOne) return true; } else { currentNode = currentNode.next; }; }; }; // If the tail needs to be deleted if (this.tail.value === value) { this.tail = currentNode; }; if (deletedNode === null) { return false; } else { return true; };}
For me, this code makes clear why deleting items can be a much more expensive operation than inserting them!
deleteHead
It would also be useful to delete items from the beginning or the end of our list. For the first item, this is straightforward:
deleteHead() { if (!this.head) return false; this.size -= 1; const deletedHead = this.head; if (this.head.next) { this.head = this.head.next; } else { this.head = null; this.tail = null; } return true;}
deleteTail
Deleting the final item is a more expensive operation, since ? when there is more than one item in our list ? we need to iterate through the entire list to locate the penultimate item.
deleteTail() { if (this.size === 0) return false; if (this.size === 1) { if (this.head === null) { return false; } else { this.head = null; this.tail = null; this.size -= 1; return true; } } const deletedTail = this.tail; let currentNode = this.head; while (currentNode.next) { if (!currentNode.next.next) { this.size -= 1; currentNode.next = null; } else { currentNode = currentNode.next; } } this.tail = currentNode; return deletedTail;}
Part 5: Accessing Entries
In linked lists, accessing values has a linear time complexity because we must iterate through the entire list ? always from the first entry to the last.
includes
In our implementation, we want our includes method to accept either a value or an instance of the LinkedListNode class. It should return true if an element with the correct value exists in our list, and false otherwise.
includes(value) { if (!this.head) return false; let isNode = value.constructor.name === ‘LinkedListNode’; if (isNode) value = value.value; let currentNode = this.head; while (currentNode) { if (value !== undefined && value === currentNode.value) { return true; }; currentNode = currentNode.next; }; return false;}
find
Our find method should return the value of the first element in the linked list that satisfies a provided callback function. Otherwise, it should return undefined . If the callback provided is not a function, we?ll throw a TypeError :
find(callback) { if (Object.prototype.toString.call(callback) !== ‘[object Function]’) { return new TypeError(callback + ‘ is not a function’); }; if (!this.head) return undefined; let currentNode = this.head; while (currentNode) { if (callback && callback(currentNode.value)) { return currentNode; }; currentNode = currentNode.next; }; return undefined;}
Conclusion
And that?s a wrap!
To see the complete code of our implementation, check out this GitHub gist.
These methods should be sufficient to cover the core use cases of linked lists. Of course, there are lots of ways we could extend the functionality of our LinkedLists . If you?re interested in building on what we?ve made so far, you could try adding a sort , filter, reverse , forEach , toString or clear method.
I hope you found this a useful introduction to one of computer science?s fundamental data types, and if you have any questions or feedback, feel free to leave a comment.
Further Reading
For alternative JavaScript implementations of a linked list, check out:
linked-list
Small double linked list. Subclassing: Create a new Linked List. Create a new this and adds the given array of items?
www.npmjs.com
trekhleb/javascript-algorithms
You can’t perform that action at this time. You signed in with another tab or window. You signed out in another tab or?
github.com
And if you?re keen to learn more about data structures and algorithms written in JavaScript, I strongly recommend you take a look at Oleksii Trekhleb?s full JavaScript Algorithms repository:
