Clearing Some of the Mists Surrounding Linked Lists
Concerning Javascript though most of this information is language agnostic.
Linked lists are like most topics in computer programming and most topics in general life; a little intimidating when first learning about them but once we get the hang of how to work with them linked lists are just another way to organize and process data.
We can not address every use case or issue that we might come across concerning linked lists in this post but by providing a few ground rules to work from we can set ourselves up for finding the correct answers.
In this post we are going to be talking about singly linked lists, as opposed to doubly linked lists. Meaning that the nodes in the list have a reference to the next node but not the previous node.
Linked Lists vs Arrays
To first get a feel for linked lists it is helpful to compare them to arrays. Mostly because arrays are also lists and if we are trying to decide between using a linked list vs another data structure to manipulate/store information then the most likely contender is the array.
It bears mentioning that most developers will move through an entire career and never use a linked list. The majority of the time arrays will be enough but the more familiar with all our tools the more able we are to write efficient code and efficient, readable code is our tradecraft.
Memory: Items in arrays are stored contiguously in memory or side by side. Linked lists are not stored contiguously. Instead each item in a linked list contains the item/data itself as well as a pointer(or reference) to the next item, that is stored in another place in the machines memory.
Navigation: The only way to find an item in a linked list is to start at the beginning of a list and iterate through the list. For this reason linked list are typically less efficient than arrays.
Dynamic Data: Where linked lists shine is the flexibility they offer. Although Arrays in javascript are dynamic, but because of the array needing contiguous storage if we are working with very large sets of dynamic data it is more likely that we would run into memory restrictions with an array as opposed to a linked list.
Overall Storage: Arrays are limited in size and when an array is instantiated memory is given for the maximum size that an array could possibly be whether or not the array contains a max number of elements or not.
Handling Changes(not the same as space allocation at runtime): Because linked lists are noncontiguous inserting a new item in the list is not an expensive task. On the other hand when an item is inserted into an array all the items coming after that item must be shifted, and of course the same is true for removing an item from an array.
Working With Linked Lists
To start let’s look at the setup of a linked list.
class LinkedListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}We can see that we start with our constructor and two properties; data and next. data is of course the data contained in this node and next is our pointer to the next node. next is initially set to null because null will always mark the end of a linked list. This will become more clear in a few moments.
Here is one, quite verbose, way we can build a list.
// create the first node
const head = new LinkedListNode(1);
// add a second node
head.next = new LinkedListNode(2);
// add a third node
head.next.next = new LinkedListNode(3);It is standard practice to call the first node the head. When then set the nodes following the head by chaining next calls.
Of course we probably would want to chain endless next calls in this way, we would use recursion. By using recursion we can find the end of the linked list with three lines of code and then call next. The most common style is to use a while loop like below.
let current = head;
while (current.next !== null) {
current = current.next;
}current.next = newData;
Or if we wanted to modify each node in our linked list we might write something like the code below.
let current = head;
while (current !== null) {
// perform some function
current = current.next;
}In both examples we are checking for null to find the end of the list. Keeping that in mind should help us work through any work we need to do on linked lists.
In Conclusion
Linked lists are not all too difficult to work with once we understand how to approach them. Of course there are many ways to manipulate linked lists but as long as we remember that each node must point to the next node then we can find what we are looking for or perform whatever work we need to do.
