Introduction
In Computer Science, one of the most basic and fundamental data structures is the linked list, which functions similarly to an array. The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation of any other elements.
In some programming languages, the size of an array is a concern and one of the ways to overcome that problem and allow dynamically allocated data is using linked lists.
Luckily in JavaScript, arrays aren’t limited to a certain size, and both insertion and deletion can be done trivially at any index using the appropriate built in array method, so you don’t have to think about overcoming those limitations.
So if array size, array insertion and array deletion are not limitations in JavaScript, are linked lists really necessary? The short answer to that is no; however, it’s the simplest of the dynamic data structures and it will give you a solid foundation, so you can understand more complex data structures like graphs and binary trees with more ease.
Structure of a linked list
A linked list is a linear collection of data elements called nodes that “point” to the next node by means of a pointer.
Each node holds a single element of data and a link or pointer to the next node in the list.
A head node is the first node in the list, a tail node is the last node in the list. Below is a basic representation of a linked list:
[ NODE(head) ] -> [ NODE ] -> [ NODE(tail) ] -> null
For a more thorough explanation, use these resources:
Assignment
If you wish to use multiple ES6 modules, remember that Node uses CommonJS modules by default and so you must tell Node to use ES6 modules instead.
You will need two classes or factories:
LinkedListclass / factory, which will represent the full list.Nodeclass / factory, containing avalueproperty and a link to thenextNode, set both asnullby default.
Build the following functions in your linked list class / factory:
append(value)adds a new node containingvalueto the end of the listprepend(value)adds a new node containingvalueto the start of the listsizereturns the total number of nodes in the listheadreturns the first node in the listtailreturns the last node in the listat(index)returns the node at the givenindexpopremoves the last element from the listcontains(value)returns true if the passed in value is in the list and otherwise returns false.find(value)returns the index of the node containing value, or null if not found.toStringrepresents your LinkedList objects as strings, so you can print them out and preview them in the console. The format should be:( value ) -> ( value ) -> ( value ) -> null
Extra credit
insertAt(value, index)that inserts a new node with the providedvalueat the givenindex.removeAt(index)that removes the node at the givenindex.
Extra Credit Tip: When you insert or remove a node, consider how it will affect the existing nodes. Some of the nodes will need their nextNode link updated.