Linked Lists are dynamic data structures that can grow and shrink as need be without the need for declaring a maximum size on creation. Because of not needing to allocate memory beforehand, linked lists are generally more memory efficient that other data structures such as arrays. Adding and removing values from the front of a list can be done in constant time and operations done at the end or middle of the list can be done easily in linear time.
Disadvantages of linked lists include memory consumption (twice the memory needed because you're storing a pointer in addition to a value) and there isn't constant time, random access to values located inside of the list. Returning a value would require following pointers starting at the head of the list until the value is discovered.
Below is an implementation of a linked list in JavaScript using 2 classes - a Node class and a Linked List class. Please read through the code below and let me know if you're aware of a better, more efficient way to implement linked lists!
Hey, Tyler here. I'm currently working on some great web development and digital marketing products and services over at ZeroToDigital.
If that sounds interesting to you, please check it out!
JavaScript
class Node {
constructor(data) {
this.data = data // data or value of node is equal to parameter data value
this.next = null // the node's pointer is null by default
}
}Our node class will be pretty simple as each node will contain only a value and a pointer to the next node in the list. The pointer will be null by default and we'll update the pointer later when new nodes are added to the list.
JavaScript
class LinkedList {
constructor() {
this.head = null // head node of linked list is null by default
}The LinkedList class will only be concerned about holding a head node in the list. This node and all subsequent nodes will contain the meat of the linked list from here on our (values and pointers).
Note: all functions from here on out in this post will belong to this LinkedList class and should be placed inside accordingly.
JavaScript
size() {
let temp = this.head // create temp variable and set equal to head node of linked list
let i = 0 // create counter variable
while (temp) { // while temp is not null
temp = temp.next // set temp variable equal to next node in list
i++ // increment counter
}
return i // return counter value
}The linked list's size function will return the size of our linked list in total number of nodes. We'll create a temp variable to hold the value of the head of our linked list and variable i to be used to hold the actual size of our list. Then, while our temp variable is not equal to null, we'll loop through the linked list and increment our counter variable which we'll return once our loop is finished.
JavaScript
empty() {
return this.head == false // if linked list of empty, this conditional statement will be true, else false
}Our empty function will allow us to check if the linked list is empty or not, simply by returning the conditional statement that the head of our linked list is equal to false. This function will return true if the list is indeed empty and false if the list is not empty.
JavaScript
front() {
return this.head // return head node of linked list
}We'll also create 2 functions that will return to us the first and last values in our linked list without removing them. The front function will simply return the node located at the head of our linked list.
JavaScript
back() {
let temp = this.head // create temp variable and set equal to head node of linked list
while (temp.next) { // while node has a pointer value
temp = temp.next // set temp variable equal to next node in linked list
}
return temp // return last node
}The back function will return the very last node in our list. However, to get there it will loop through our list until the current node's pointer is null. When this is the case then the current node will be returned.
JavaScript
pushFront(data) {
let node = new Node(data) // create new node
let next = this.head // set next variable equal to head node of linked list
this.head = node // set head of linked list equal to new node
if (next) { // if next variable is not null
node.next = next // set pointer for new node equal to node previously at head of list
}
}Our LinkedList class will need 2 methods created for adding new values to our list - to the front of the list and the back.
The pushFront function will allow us to add a new node to the front of our linked list. We'll create a new node, then get the node located at the head of the linked list. Then we'll set the head equal to our new node and set the first node's pointer equal to the next node in our list (the node that was formerly at the head).
JavaScript
pushBack(data) {
let node = new Node(data) // create new node
if (this.head == null) { // if head of linked list is null
this.head = node // set head equal to node
} else { // if head of linked list is not null
let temp = this.head // create temp variable and set equal to head node
while (temp.next) { // while current node has a pointer that's not equal to null
temp = temp.next // set temp variable equal to next node in list
}
temp.next = node // after while loop, set current node's pointer equal to new node
}
}We'll create the pushBack function to allow us to add new nodes to the back of our linked list. In order to do this, we'll need to loop through our entire linked list (following the pointers) to find the final node in our list. This operation will need to be done in linear time - O(n) - which is a negative drawback to using linked lists.
After we follow the pointers to the final value, we'll change it's pointers value from null to the new node that we created.
JavaScript
popFront() {
let first = this.head // create first variable and set equal to first node in linked list
if (first.next) { // if current node has a pointer to another node
let second = first.next // create second variable and set equal to next node
this.head = second // set head equal to second node
this.head.next = second.next // set head node pointer equal to second node's pointer
} else { // if head node doesn't have a pointer
this.head = null // set head equal to null
}
return
}We'll now create 2 functions to be used for removing nodes from our list. The first - popFront will allow us to remove the first node in our linked list. We'll just set the head of our list equal to the second node (if it exists) and then if the second node's pointer points to a node, we'll set this as the new head node's pointer.
As opposed to arrays which require linear time - O(n) - for this operation due to having to shift all subsequent items forward, this operation can be done in constant time - O(1) - for linked lists since we're simply updating the first value and it's pointer and don't need to visit the following items.
JavaScript
popBack() {
let temp = this.head // create temp variable and set equal to first node in linked list
let prev = null // create prev variable and set equal to null
while (temp) { // while temp is not null
if (temp.next) { // if current node has a pointer to next node in list
prev = temp // set prev variable equal to current node
temp = temp.next // set temp variable equal to next node
} else { // If current node doesn't have a pointer to next node in list
temp = null // set current node equal to null
prev.next = null // set previous node's pointer equal to null
return // return from function
}
}
}To remove a value from the end of our list, we do have to follow our entire list starting at the first, head node. We'll then loop through our list as long as the current node's pointer points to a valid node. Once we've come across a node whose pointer is null, we'll set that node equal to null and set the previous node's pointer equal to null.
JavaScript
valueAt(index) {
let temp = this.head // create temp variable and set equal to first node in linked list
let i = 0 // set i = 0 to be used as counter
if (temp && i == index) { // if temp is not null and i is equal to index value
return temp.data // return temp node's value
}
while (temp) { // while temp is not equal to null
if (i == index) { // if is is equal to index value
return temp.data // return temp node's value
}
i++ // increment counter
temp = temp.next // set temp variable equal to next node in list
}
}There may be occasion to get the value of a list item at a specific index in our list. Since linked lists aren't index-based lists like arrays, we don't have random access to each value and would need to follow our pointers until we arrived at the nth-node item.
To do this, we'll create a variable - i to hold our counter. Then we'll loop through our list while nodes exist until we've reached the point where our counter equals the index value that we're searching for. At that point we'll return the value (or data in this case) of the node.
JavaScript
remove(data) {
let temp = this.head // create temp variable and set equal to first node in linked list
let prev = null // create prev variable and set to null
if (temp && temp.data == data) { // if temp is not null and temp node's data is equal to value to be removed
this.head = temp.next // set head of linked list equal to next node
temp = null // set temp variable equal to null
return // return from function
}
while (temp) { // while temp is not null
if (temp.data == data) { // if node's data equals data to be removed
break // break from loop
}
prev = temp // set prev variable equal to temp node
temp = temp.next // set temp equal to next node in linked list
}
if (!temp) { // If temp is null
return // return from function
}
prev.next = temp.next // set previous node's pointer equal to current node's next node
temp = null // set temp variable equal to null
}We'll need a way to delete specific values from our list, so we'll create a method in our linked list class called remove that will accept a paramater called data that will contain the value to be removed.
We'll loop through our linked list, following the pointers, until we find the value. While we're looping, we'll need to keep track of the current node's previous node so that we can update its pointer to the list item after the item we delete.
JavaScript
reverse() {
let prev = null // create prev variable and set to null
let temp = this.head // create temp variable and set equal to first node in linked list
while (temp) { // while node is not null
let next = temp.next // set next equal to next node in list
temp.next = prev // set temp node's pointer equal to prev node
prev = temp // set prev variable equal to current node
temp = next // set temp variable equal to next node in list
}
this.head = prev // at the end, set the head node equal to node at prev variable
}If a factor in our program has changed that requires the order of our list to be flipped, we'll need a way to change or reverse our linked list. At first thought, it seems like we may have to loop through our list, put the items into an array, and then recreate a new list working backwards in the array. That's not very efficient, however, and would require a time equivalent to O(n * 2). Since we're only dealing with pointers, we don't need to pluck the values out of our list, we can just update our pointers.
So we'll visit each node in our list, starting with the node located at the linked list's head, and update it's pointer to point to the node previous to it instead of the next node, then, after iterating through our list, we'll set the head node equal to the very last node we come to. This can be done in linear time - O(n) - which is exactly half of the time that the previous way would require.
JavaScript
print() {
let temp = this.head // create current variable and set equal to first node in linked list
while (temp) { // while node is not null
console.log(temp.data) // log value
temp = temp.next // set temp equal to next node in list
}
}If we want an easy way to see our values (whether it's logging them or echoing them to the browser window), we'll need to create a print function. This will just loop through our linked list and log each value (data) that it comes across to the console.
JavaScript
var list = new LinkedList
list.pushBack(5)
list.pushBack(3)
list.pushBack(4)
list.pushBack(6)
list.pushBack(2)
list.pushFront(8)
console.log(list.size()) // 6
list.print() // 8,5,3,4,6,2Start using the linked list by creating a new LinkedList object, pushing to, checking the size, printing, etc.