Implementing a Linked List in JavaScript
A linked list is a data structure consisting of a linear collection of data elements (nodes). Unlike an array, these packets of data are not defined by their placement within memory, but rather in relation to the previous element in the list.
Each node in a linked list contains two pieces of data: the data being held by the node as well as a ‘pointer’ indicating the next node in the list (see diagram). As well as the nodes, a linked list also contains information about its head (first node) and optionally its tail (last element).
One important advantage of this type of data structure is that it can be mutated without having to change other elements within the list. For example: combining two arrays requires changing the index of all elements in the second array. With a linked list this can be achieved without such disruption. On the other hand, the nature of a linked list is that it can only be traversed by going through one element at a time sequentially: this makes it difficult to look up individual items within the list.
Some potential real-world implementations of a linked list may be for the back/forward buttons on a web browser or the undo/redo commands in an application.
In this article I will implement a Linked List class in JavaScript and provide some useful functions for interacting with…