JavaScript Linked Lists Data Structure
In this article I will go over -
What is a linked list?
How is a linked list constructed in JavaScript?
How to Create, Add, and Remove a Data Point(Node) from our linked list.
Bonus: Finding middle of Link without a counter.
What is a Linked Array? Very simply, a linked list is a set of data that is “Linked” together through a pointer rather than being organized sequentially in a specified memory location, like a standard array. This allows for data to be stored and arranged without the worry of memory allocation or worrying about having to move your entire data-set. Arrays are great for pulling data from a specific index, they are not so great at being rearranged, it can become a lot of work.
Smart Definition “In computer science, a linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.” — Wikipedia
To Construct a linked list we will be using ES6 Classes; We will begin by creating a Node Class that will hold a constructor that will take in “data” and “next” it will look something like this.
class Node{
constructor(data, next = null){
this.data = data
this.next = next
}
}the Node class will be used to construct out data points;
Following the creation of out Node class we will need to create a Linked List Class, this is what we will be using to connect all the little Nodes we will be creating. the Linked List Class will have a constructor that will store the values head and count, head will be keeping track of out Linked List and count will be used to iterate through the list to keep track of where we are if we need to remove or add from specific points in our link list.
class LinkedList {
constructor(){
this.head = null;
this.size = 0;
}
}Now inside of our linked list we will create six methods, as follows “addToFirstIndex, insertLast, insertAtIndex, removeAt”
in our first method we will be inserting out first datapoint, the insertFirst method will take in data and assign it to the “head” value inside, and increase our counter by 1.
addToFirstIndex(data){
this.head = new Node(data, this.head)
;this.size++
}addToFirstIndex, is taking in data for example addToFirstIndex(100) it is using that data to define a new Node constructor, and if the this.head already holds value, that value is being assigned to the new Nodes next value; the new Node(x,x) is assigned to this.head, and our counter is increased console.log(this.head) would look like this:
Node{
data:100,
next: null
}if you want to type this on your own ensure you have created a new LinkedList
for example
const linkList = new LinkList()
linkList.addToFirstIndex(100);
console.log(linkList);if the addToFirstIndex method is called twice the second call will push the first data value to the next key, it should look like
linkList.addToFirstIndex(100);
linkList.addToFirstIndex(200);
console.log(linkList);
Node{
data:200,
next: Node{
data:100,
next: null
}
}now addToLastIndex, there is a little more complexity to it. Again, we are taking in data addToLastIndex(data), we will need to create out new node, and instantiate a current variable, for edge cases we will check to make sure the list is not empty, and if it is empty we will set out head to our newly created Node.
If there is a Linked List assigned to our head we will set our current variable to this.head and loop through our Linked list, assigning our head to our head.next until there is no more next value; at this point we exit the loop and assign the null next property our new node. It looks like this.
addToLastIndex(data){
let node = new Node(data);
let current;
if(!this.head){
this.head = node;
} else{
current = this.head;
console.log(this.head);
while(current.next){
current = current.next;
}
current.next = node;
}
this.size++
}InsertAtIndex
If you’re still here, thank you; I’m writing all of this to learn the material better, but I do like to think it will help someone, sometime.
Now, for inserting at a specific point, there will be a little bit of “if” logic, first off, if the index is ZERO, we will call are addToFirstIndex method; if the index is greater than the this.size, we will return out of the function.
Once past the first round of checks we will need to create our new Node and instantiate our current and previous positions.
Current will be set to this.head and we will create a count variable and set it to ZERO.
Following this we will go through a “while” loop and check if the count is less then the index, if this is true we will set out previous to current, add ONE to our count and set our current to our current.next property.
After we exit the loop we will set our node.next value to current and previous.next value to node.
<CODE BELOW/>
insertAtIndex(data, index){
if(index > 0 && index > this.size){
return;
}
if(index === 0){
this.insertFirst(data);
return;
}
const node = new Node(data);
let current, previous;
current = this.head;
let count = 0
while(count < index){
previous = current;
count++;
current = current.next;
}
node.next = current;
previous.next = node;
this.size++;
}RemoveAtIndex
To remove from a specific index we will need to be provided the index we are removing removeAtIndex(index) as we move into our method the first things we will do is check for validity in the search using an “if” statement
if(index > 0 && index > this.size){
return;
}the code above is checking whether the index is greater than zero and the index is greater than the size of the Link List; If so we will return, the index number is invalid;
let current = this.head;
let previous;
let count = 0;Once past our first check we will instantiate three variables, one to hold the current value, one we will set late to track the previous and we will set a counter to ZERO.
if(index ===0 ){
this.head = current.next
}else {
while(count < index){
count++
previous = current;
current = current.next
}
previous.next = current.next}
this.size--
}
After instantiating our variables, we are going to check the index value, if ZERO, than we will set its value to null by assigning it its next value. Else, we will loop through the passing through until we reach the specified index setting our previous to current, and our current to current.next.
Once we exit the loop we will set the last Nodes previous to null, removing the data from the node and redirecting the next pointer.
Finding the middle element without a counter
Something a little extra, Lets break it down; We start by creating our Node and LinkedList Classes, except this time we will need to keep track of all parts of the Linked List by placing a “tail”, this will be the end node, we will also set a mid and even boolean that will be true of false. Once set up, we will be adding three methods, addNode, updateMid, and getMidPoint.
addNode
our addNode method will take in data, first we will check the head value, if null we will set the head, tail and mid to a new Node with data and a next value set to the current head.
if, the head is not null, we will set the tails next value to a new tail node; this node has a next value of null.
after we will set the tail value to the this.tail.next value to null, followed by a call to our updateMid method.
addNode(data) {
if ((this.head === null)) {
this.head = this.tail = this.mid = new Node(data, this.head);
} else {
this.tail.next = new Node(data, null);
this.tail = this.tail.next;
this.updateMid();
}
}
updateMid() {
if (this.even) {
this.mid = this.mid.next;
this.even = !this.even;
} else {
this.even = !this.even;
}
}As shown above, in our updateMid method, we will check to see if this.even is true, if true we will set this to our this.mid to this.mid.next which had previously been set to the new Node, following we will toggle out even value to false.
If false, we will set it to true for the next iteration.
now for our final method call, getMidPoint, this method will return the this.mid.
to use these classes you can input the following code.
let linkedlist = new LinkedList();
linkedlist.addNode(200);
linkedlist.addNode(300);
linkedlist.addNode(400);
linkedlist.addNode(500);
linkedlist.addNode(600);
console.log(linkedlist.getMidPoint());Try it out, And thanks for reading.
-Anthony
