#14 Data Structures with JS examples: Linked List
This article belongs to the JS Data Structures series, which contains these articles:
- Arrays
- Stacks
- Queues
- Linked List
- Sets (soon)
- Dictionary and Hashes (soon)
- Trees: Binary Search Tree (BST) (soon)
- Trees: AVL Tree (soon)
- Trees: Red-black Tree (soon)
- Trees: Binary Heap / Heapsort (soon)
- Graphs (soon)
Linked Lists are a collection of elements where is possible to add items in any position that you want, we have several practical examples of linked lists like:
- Creating a music player (next, previous, skip back/forward)
- Manage low-level memory where each node representing a used or available (free) block of memory
- The train wagons (probably the most famous example).
- And my favourite: A dog conga line:
This article will cover the following content:
- Basic structure
- Linked list methods
- Doubly linked list
- Instantiating your linked list
- Time and space complexity
Basic structure
Let’s create a closure function that will allow us to output only the public Linked List methods, avoiding changes in internal attributes, the skeleton will be:
const LinkedList = (() => {
let head = null
let length = 0 class Utils {
...the utils methods
} class PublicLinkedList {
...the linked list methods will be here
} return PublicLinkedList
})();
With this approach, the only public methods will be the methods included in PublicLinkedList class, if you want to know more about closures this article is really useful:
You’ll need to create a Utils class with a static node method to each one of Linked List elements as well a reference to the next node.
class Utils {
static node(element){
return {
element,
next: null
}
}
}Using the static before the item function name, we are able to call this function without instantiating the Utils class. If you want to know more about static methods in JS this article will help you:
Linked List methods
After we created the basic structure we are ready to implement the required linked list methods:
- size
- isEmpty
- append
- insert
- removeAt
- remove
- indexOf
- getHead
- toString
size()
This method returns how many items there are inside a linked list, you’ll need simply return the length variable:
size(){
return length
}isEmpty()
This method returns if the linked list contains or not contains items inside, to do that you’ll use the size linked list attribute is equal to zero:
isEmpty(){
return this.size() === 0
}append(element)
This method allows to add an item at the end of a list, when we append an item we need to change the next attribute of the current last item of a list to refer to this new item, we don’t need to do that when the list is empty, but we need to change the head of the list to refer to this new item, the visual concept is this:
The code that we need to do that is this:
append(element){
const newItem = Utils.node(element) if(this.isEmpty()){
head = newItem
} else {
let currentLastItem = head
while(currentLastItem.next !== null){
currentLastItem = currentLastItem.next
} currentLastItem.next = newItem
} length++
}
insert(position, element)
This method allows adding a new item in any position of a Linked List, to do that we need:
- Checks if the desired position is the first, in this case, we need to store the current head value as the next value of the new element, after this, we need to replace the head by this new element.
- If is not the first element we need to get the element that is currently placed in the same position that we need to add the new element and then:
2.1. Change the next value of this element, pointing to the new item
2.2. Change the next value of the new element, pointing to the element that is currently placed in the next position after that we need to add the new element - Increase the length value
The code that we need to do that is:
insert(position, element){
if (position < 0 || position > length) {
throw new Error("Invalid position")
} const newNode = Utils.node(element) if (position === 0) {
newNode.next = head
head = newNode
} else {
let previousNode = head
let nextNode = head.next
let currentNode = head
let currentPosition = 0 while (currentPosition++ < position) {
previousNode = currentNode
nextNode = currentNode.next
currentNode = currentNode.next
} previousNode.next = newNode
newNode.next = nextNode
} length++ return true
}
removeAt(position)
This method allows removing an item in any position, to archive that we need:
- If the element is the first element we need to set the head value to the next value of the current head attribute.
- If this element is not the first element we need to:
2.1. Get the element placed before the position that we want to remove.
2.2. Get the element placed after the position that we want to remove.
2.3. Change the next value of the element before to refer to the element after the position that we want to remove.
3. Return the element removed.
The code to do that is:
removeAt(position) {
if (position < 0 || position > length - 1) {
throw new Error("Invalid position")
} length-- if (position === 0) {
const currentHeadELement = Object.assign({}, head)
head = head.next
return currentHeadELement.element
} let currentPosition = 0,
nodeBefore,
currentNode while (currentPosition++ < position) {
nodeBefore = currentNode
currentNode = currentNode.next
} nodeBefore.next = currentNode.next
return currentNode.element
}
remove(element)
This method allows removing a given element from linked this, to do that we need:
- Go through the linked list until we find this element.
- Store the previous element before this and the next element after this.
- Change the reference in the previous element next value to point to the next element after the element that will be deleted.
- If the element is not found, return false, if the element is found first decrease the length attribute and after returns true.
The code is:
remove(element) {
if (this.isEmpty()) {
throw new Error("The linked list is empty")
} if (head.element === element) {
head = head.next
length--
return true
} let currentNode = head
let previousNode while (currentNode !== null && currentNode.element !== element) {
previousNode = currentNode
currentNode = currentNode.next
} if (currentNode === null || currentNode.element !== element) {
return false
}
previousNode.next = currentNode.next
length--
return true
}
indexOf(element)
This method allows checking the position where is some element inside a linked list, to archive this we need to do:
- Go through the linked list until we find this element.
- When finding the item returns the index of the item, or return -1 case the item is not found
The code is:
indexOf(element) {
if (this.isEmpty()) {
throw new Error("The linked list is empty")
} for (
let currentItem = head, positionItem = 0;
currentItem !== null;
currentItem = currentItem.next, positionItem++ ) {
if (currentItem.element === element) {
return positionItem
}
} return -1
}
In this example, we are using FOR structure with more than one variable and increment, some developers don’t know all things that are possible with FOR, most people only know this:
for(let index = 0; index < 10; index++){
...some code here
}But is possible to create as well as increment more variables when you create the FOR loop, like this example:
for(
// you could define more than one initial variable, separing with comma
let index = 0, myVar = ''; index < 10; // you could increment more than one variable, separing them with comma
index++,myVar=index*2
){
console.log(index, myVar)
}/* will output:
0, 0
1, 2
2, 4
3, 6
4, 8
5, 10
6, 12
7, 14
8, 16
9, 18
10, 20
*/
If you want to know more about loops in JS I wrote this article about this:
getHead()
This method is fundamental because it allows retrieving all data inside our Linked list, its implementation is very simple
getHead() {
return head
}Calling this method and using the next attribute is possible to get all elements.
toString()
The javascript has a default toString method to Objects and Arrays, if you try to use to string in an array JS will return this:
[1, 2, 3, 4, 5, 6].toString()
// will output: "1,2,3,4,5,6"If you try an object:
({hello: 'world'}).toString()
// will output: "[object Object]"But none of these behaviours is what we want to our linked list when we call toString method, what we want is this function outputs all our element values inside our nodes, to do that we need to reimplement this method to override the default JS one.
To archive this we need:
- Go through the linked list and store all elements values in a string
- Output this string
This is the code:
toString() {
if (this.isEmpty()) {
throw new Error("The linked list is empty")
} let outputString = "" const addComma =
currentString => (currentString !== "" ? ", " : "") for (
let currentItem = head;
currentItem !== null;
currentItem = currentItem.next
) {
outputString = `${outputString}${addComma(outputString)}${currentItem.element}`
} return outputString
}
Putting all together
If you want to check out other Javascript Data Structures examples take a look in this GitHub repository:
Doubly linked list
The main difference between a common linked list and a doubly-linked list is inside a doubly linked list each node has an additional attribute to refer to the previous node, also a doubly linked list has a new attribute called tail that allows knowing what is the last node without the need go through all items, this makes the append function faster.
The methods list remains the same, but inside some of them we have some differences that we need to implement
append(element)
Unlike a Linked List in a Doubly Linked List, we don’t need to go through all items to find the last item and add a new item after this, we simply do that:
- If the Linked List is empty, we need to refer to this new node to the head and put the tail as a null value
- Add a reference in the old tail to the new tail using the next attribute
- In the new node, we refer the prev value to old tail
- Finally, we replace the tail with the new node
append(element) {
const newNode = Utils.node(element)
if (this.isEmpty()) {
// its means that this item will be the head and tail
head = newNode
tail = newNode
} else if (this.size() === 1) {
// its means that this DLL have only the head, so we need refer the newNode to the head
head.next = newNode
newNode.prev = head
tail = newNode
} else {
// its means that this DLL have more than 1 item so we only need change the tail
tail.next = newNode
newNode.prev = tail
tail = newNode
} // in the end we need increase the length of our DLL
length++
return true
}
insert(position, element)
The difference between inserting items in a simple Linked Linked list and in a Doubly Linked List is you’ll need to change the previous value of the nodes involved in this operation.
Bellow the code with the differences from the Linked List explained:
insert(position, element) {
if (position < 0 || position > length) {
throw new Error('Invalid position')
} const newNode = Utils.node(element) if (position === 0) { // will add as fist item
if (this.isEmpty()) {
// the DLL is empty, its meand that this element is the head and tail
head = newNode
tail = newNode|
} else if (this.size() === 1) {
// the DLL has only one node, its meand that this current node is the new tail and the new node is the head
head.prev = newNode
tail = head
newNode.next = tail
head = newNode
} else {
// the DLL has more than one item, it's meand that the newNode is the head, and the current head will refer to newNode
newNode.next = head
head.prev = newNode
head = newNode
}
} else if (position === length) {
// this means that this item will be added in the end, so is possible to use the append method - we need add return to avoid increase the length 2 times
return this.append(element)
} else {
// this means that this item will be added between the first and the last, we need search the current item that is placing the desired position and add the new item before this item
let currentNode = head
let currentPosition = 0
while (currentPosition < position) {
currentNode = currentNode.next
currentPosition++
} const prevNode = currentNode.prev
prevNode.next = newNode
newNode.prev = prevNode
newNode.next = currentNode
currentNode.prev = newNode
} // in the end we need to increase the length
length++ return true}
removeAt(position)
To remove an item from a doubly-linked list we need to change the next value from the element left from the element that will be removed and change the prev value from the element in the right:
removeAt(position) {
if (position < 0 || position >= length) {
throw new Error('Invalid position')
} if (position === 0) {
// will remove a item from the beggining, to we need use the head attribute to do that
if (this.size() === 1) {
// we need change the head and the tail once this DLL has only one element
head = null
tail = null
} else {
// this DLL has more than one item, we need change the head
head = head.next
head.prev = null
}
} else if (position === length - 1) {
//this case means that this item will be removed from tail
tail = tail.prev
tail.next = null
} else {
// this case means that this item will be remove from the middle
let currentPosition = 0
let currentNode = head while (currentPosition < position) {
currentPosition++
currentNode = currentNode.next
} const prevNode = currentNode.prev
const nextNode = currentNode.next
prevNode.next = nextNode
nextNode.prev = prevNode
} // in the end we reduce the length and return true
length--
return true
}
remove(element)
Remove an item using the element name in a doubly-linked list is almost the same process, the difference is you need to change the next value from the item in the left of the removed item and the previous value from the item in the right
remove(element) {
if (this.isEmpty()) {
throw new Error('The linked list is empty')
} // first will check if the removed item is the head
if (head.element === element) {
if (this.size() === 1) {
// in this case we'll need to remove the tail and the head
head = null
tail = null
} else {
// this case means that this DLL has at leat 2 items, so we need only change the head
head = head.next
head.prev = null
}
length--
return true
} if (tail.element === element) {
// this means that we need remove the tail from this DLL
tail = tail.prev
tail.next = null
length--
return true
} // this case means that we need search though all elements
let currentNode = head.next
while (currentNode !== null && currentNode.element !== element) {
currentNode = currentNode.next
} if (currentNode.element === element) {
//this means that the item was found, so we could remove them
let previousNode = currentNode.prev
let nextNode = currentNode.next
previousNode.next = nextNode
nextNode.prev = previousNode
length--
return true
} //this means that the item was not found
return false
}
The other methods (size, isEmpty, indexOf and toString) remains the same.
Putting all together
This is the result of a Doubly Linked List
If you want to check out other Javascript Data Structures examples take a look in this GitHub repository:
Instantiating our linked list
After declaring your Linked List, you could call it in this way:
const myLinkedList = new LinkedList();// adding items in the bottom
myLinkedList.append("a new item");// adding items in the top
myLinkedList.insert(0, "first item");// searching for a item
myLinkedList.indexOf("first item");// getting the LL size
myLinkedList.size()// checking if the LL is empty
myLinkedList.isEmpty()// removing item by index
myLinkedList.removeAt(1);// removing item by name
myLinkedLIst.remove("a new item")// getting all elements inside your LL
myLinkedList.toString()
Time and space complexity
Time complexity defines how faster is your algorithm, and space complexity defines how much memory your algorithm needs to run, this is also called Big-O notation.
Let’s analyse the methods inside our linked list to find out this:
- size: We have O(1) to time and O(1) to space, both to Linked List and Doubly Linked List, once the time and memory that we need to run this operation remains the same regardless of the number of items inside our Linked List.
- isEmpty: Same thing here, O(1) to time and O(1) to space to both linked list types.
- append: The complexity in the append method varies according to the type of Linked list:
— Linked List: To add an item at the bottom we need to go through all items until we found the last item and connect this last item with the new one that we want to add, it means that the time complexity is O(n), but the memory that we need remains constant because we don't need to store the sequence of nodes, only the last node, so the space complexity is O(1).
— Doubly Linked List: In this case, we have the tail variable that helps us to identify faster which is the last item of our Doubly Linked List, making the time to append this item constant regardless of the number of items, the same applies to memory, its usage doesn’t increase according to the number of items, so we have O(1) to time and space.
- insert: To insert an item in our lists we need to find the element that is currently placed in the same position that we want to add and move this element, it means that this operation will take more time with more items thus its time complexity is O(n), but the memory that we need to allocate is the same if the list has one or one million items so O(1) is the space complexity.
- removeAt: To remove an item from a given position we need to go through our Linked List until we found this position, it means that this operation will take more time when the Linked List grows, but the memory that we need remains the same, thus O(n) to time complexity and O(1) to space complexity.
- remove: Same thing here O(n) to time complexity and O(1) to space complexity.
- indexOf: To find an item that matches with a given string we need to go through our Linked List until we found it, it means that this operation will take more time when the Linked List grows, but the memory that we need remains the same, thus O(n) to time complexity and O(1) to space complexity.
- toString: You need to go through all items and join all them in a string to print, so space and time complexity will be O(n) once you need more memory and time according to the Linked List size.
If you want to know more about Big O Notation and how to calculate this I wrote this article that will help you:
If you to want to know more about Javascript and Data Structures I recommend these books:
- You Don’t Know JS Serie by Kyle Simpson (My favourite)
- Eloquent JS by Marijn Haverbeke
- Head First Javascript by Michael Morrison
- Secrets of the JavaScript Ninja by Bear Bibeault and John Resig
- Learning JavaScript Data Structures and Algorithms by Loiane Groner
Thanks for reading! Feel free to hit the recommend button below if you found this piece helpful, also, please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
If this post was helpful, please click the clap 👏 button below to show your support! ⬇⬇
