A linked list is a data structure composed of nodes. Each node has at least 2 components, the data that it holds and a reference to the next node in the list (called a pointer). The first node in a linked list is called the head, the last node in a linked list is called the tail. There are several kinds of linked lists. Singly-linked lists only contain a pointer to the node after them, doubly linked lists contain a pointer to the node before and after them, and in circular linked lists the tail points to a node earlier in the list (generally the head) as the following node, which creates a loop, or circle.
Arrays vs Linked Lists
An array takes a contiguous space in memory. That is to say that each element of the array resides next to the other elements of that array in physical memory. An array also sets aside the same amount of memory for each of its elements. Because of this, it is easy to perform a random lookup for an element in the array. If we know the location in memory for the first element of the array, and each element takes up the same amount of space and is located next to the prior elements, we can figure out the memory address for any of the elements in the array. The nodes of a linked list, on the other hand, do not reside next to each other in memory, and that is why we have a reference pointing to the next node in the linked list. However, because of this, each node needs to only take up how much space is required to store its data and pointer(s) to the other node(s).
Pros
- Doesn’t waste memory. As mentioned earlier, each node in a linked list will only take the memory that it needs to store its data and pointers.
- Easy insertion of new nodes. In an array when you add an element, you have to shift each element occurring after it so that they still remain in contiguous memory. In a linked list, the new node can go wherever there is free space in memory, and you will just need to change the pointers.
- Easy deletion of nodes. Similar to insertion, when removing a node from a linked list all you need to do is tell the node before it to point to the node after it. Then none of the nodes will be pointing to the node you wish to delete and it will no longer be a part of the linked list.
- Dynamic size. In some languages, when initializing an array you need to explicitly say how many elements it will be holding and of what type those elements are. You don’t need to do this in JavaScript, however, when an array becomes too large to fit in a contiguous space in memory, every element must be copied over to a new location that has enough space. All of this is going on behind the scenes which makes it easy to not think about. This will never happen with a linked list, so you can continue to add nodes as long as there is enough memory to store their individual data and pointer(s).
Cons
- Each node takes up more memory. Because we must store both the data, and the pointer(s).
- No random access. The only way to find subsequent nodes in a linked list is to follow the pointers.
- Difficulties with reverse traversing. It is very difficult to go backward in a singly linked list, as there is only a pointer to the following node. It is easier in a doubly-linked list but the extra pointer costs more memory.
Coding a Singly Linked List in JavaScript
The first step in coding a linked list is to create a ListNode class.
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
This simple class does just as described above. It holds on to our data (which could be strings, integers, objects, arrays, or even other nodes), and it has a reference to the next node. From here in your terminal, you could try it out. Make a couple of nodes like so:
let node1 = new ListNode(1); let node2 = new ListNode(2); node1.next = node2;
Then if you were to check node1. next, you would see it returns node2. You could continue this process and in fact, could create a linked list just doing this. However, it would be nice to encapsulate that functionality and more in another class.
So that is exactly what we’ll do. Let’s make our LinkedList class.
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
}
Every linked list will need to keep track of its head and its size.
From here on out the rest of the methods are going to be inside of our LinkedList class.
The next thing we need is functionality to add a new node to our LinkedList.
add(data) {
let newNode = new ListNode(data); if (this.head === null) {
this.head = newNode;
} else {
let currentNode = this.head;
while (!!currentNode.next) {
currentNode = currentNode.next;
} currentNode.next = newNode;
}
this.size++;
}
The add method takes in the data of our new node. From there it initializes a new instance of a ListNode. We check if our linked list has a head node, if not, we assign our new node as the head of the linked list. Otherwise, we create a while loop to iterate through our linked list, starting with the head node, until we find a node that doesn’t have the next pointer. Once we find that node, we know we have reached the tail of our singly linked list, so we assign our new node to the next value, adding it to the list (the new node is now the tail of the linked list). After doing all of that we increment the size of our linked list.
Now we can add a node, the next thing we might want to do is retrieve a node.
getNodeAt(index) {
if (index < 0 || index > this.size - 1) {
return undefined;
} else {
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
}
Our linked lists will be 0 indexed. If someone passes in a negative number or a number that is larger than the number of indices in the linked list(one less than our size), we will return undefined. Otherwise, we need to iterate through the linked list until we get to the node at the desired index. Since we are assigning currentNode to the next node in the list, we will stop 1 short of our index. Once we are out of our while loop, we just need to return the currentNode.
Now we can add and retrieve nodes, it’s time to figure out how to remove them. First, let’s remove by index.
removeFrom(index) {
if (index < 0 || index > this.size - 1) {
return undefined;
} else {
let currentNode = this.head; if (index === 0) {
this.head = currentNode.next;
} else {
let previousNode;
for (let i = 0; i < index; i++) {
previousNode = currentNode;
currentNode = currentNode.next;
}
previousNode.next = currentNode.next;
}
this.size--;
return currentNode.data;
}
}
So we perform a similar check at the beginning of our removeFrom method, to make sure the index passed in is valid. After that, we assign the currentNode to the head, if the index is 0, we know we want to remove the head node. We can accomplish this by simply assigning the head of our linked list to the node after it.
Otherwise, we need to start looping through our linked list, keeping track of the previousNode. For each loop through our linked list, we will assign previousNode to the old currentNode and reassign currentNode to the node after it. Once we are at our index, currentNode is the node we want to remove. So, what we need to do is make the previousNode point to the node after currentNode. So, we tell previousNode to point to whatever currentNode is currently pointing to. Now none of the nodes in our linked list point to currentNode! From there we just need to decrement the size.
But what if we don’t know the index of the node we want to remove? Let’s create a method to delete a node based on the data that it’s storing.
removeNode(data) {
let currentNode = this.head;
let previousNode;
while (!!currentNode) {
if (currentNode.data === data) {
if (previousNode) {
previousNode.next = currentNode.next;
} else {
this.head = currentNode.next;
}
this.size--;
return currentNode.data;
}
previousNode = currentNode;
currentNode = currentNode.next;
}
return undefined;
}
Just like before we need to iterate through our linked list, starting with the head. We also still need to store our previous node. Our while loop is checking to make sure currentNode exists, as once we get past tail currentNode will be null. So on each iteration, we check to see if the data stored by currentNode is equal to the data of the node we wish to remove. If it is we check to see if previousNode exists. If so, we do the same thing we did above and cause previousNode to point to the node after currentNode. If previousNode is undefined, then we know that the data is stored at the head node, so we reassign the head to the next node, removing it from our linked list. After that, we decrement the size and return, breaking out of our while loop. If we loop through our entire linked list and don’t find a node holding that data, we will return undefined.
Now we can add, retrieve, and remove elements. We need to make it so we can insert a new node into our linked list, rather than just add it to the end.
insertAt(index, data) {
if (index < 0 || index > this.size - 1) {
return undefined;
} else {
let newNode = new ListNode(data);
if (index === 0) {
newNode.next = this.head;
this.head = newNode;
} else {
let currentNode = this.head;
let previousNode;
for (let i = 0; i < index; i++) {
previousNode = currentNode;
currentNode = currentNode.next;
} previousNode.next = newNode;
newNode.next = currentNode;
} this.size++;
}
}
We check to make sure our index is valid. If it is, we initialize a new node. If the index is 0, we are adding a new head to our list. So, we assign the next pointer of our newNode to the current head, then reassign the head of the linked list to newNode. Otherwise, we need to iterate through our linked list. Similar to how we would when removing nodes. Once we find the node previous to the index we want to insert at, and the node currently residing there we assign the previousNode’s next pointer to our newNode, and then assign our newNode’s pointer to the currentNode(the node that used to be at that index).
Our next method will return the index of a node holding some data.
indexOf(data) {
let currentNode = this.head;
let index = 0;
while (!!currentNode) {
if (currentNode.data === data) {
return index;
} else {
currentNode = currentNode.next;
index++;
}
}
return -1;
}
We just iterate through our linked list, keeping track of the index, if we find the node holding the data, we return that index. If our linked list doesn’t have a node with that data, we will return -1. This replicates the functionality of JavaScript’s built-in indexOf function on strings or arrays.
What if we want to clear our linked list? Well, the process is actually simple.
clear() {
this.head = null;
this.size = 0;
}
Without a reference to the head, our linked list loses references to the rest of the nodes as well, and then we just reset our size to 0.
Those methods will give the basic functionality of a linked list. Of course, there are many more methods you could add, depending on the functionality that you need. We are able to add, insert, remove, and find all of our nodes as well as empty the list entirely.
Full code here.
Happy Coding …
