Javascript Data Structures: The Linked List (Single Link)
Published: 2020-08-22 16:35:18

Javascript is confusing at times, especially for new coders. When code starts to center around objects and manipulating them, Javascript can become even more confusing. However, this understanding of objects is fundamental and crucial when talking about data structures.  One of the simplest data structures is a linked list.

#What is a Linked List?

A linked list is a series of values stored in an iterative format.  In essence, each value is a node (in this case each node is a javascript object) that contains a value, and a reference to the next item in the list. If no there is no next item in the list, it points to nothing, or null.

#Linked List Structure

Each node is an object with two properties, a value and a reference. Here is a quick visualization of what any node in the list might look like:

<Insert photo>
![node visualization](https://i.imgur.com/p92z1cL.png)
<insert code example>


We will want to implement a function to handle the creation of nodes for us.


![node creation function](https://i.imgur.com/4YuczgI.png)



We've covered the structure of each node, but how does the linked list know how to keep track of which node to start with and which to end at? The list itself is an object! The list itself does not actually store any of the nodes; the list keeps a reference to the first and last items in the list. This is done by adding a beginning and end property to the list object, and subsequently updating these pointers when modifying the list. If a "next" pointer can not logically point to a node, its value should be null.

At the start, our empty list should look something like this:
<insert code of list>
![example code of our list object](https://i.imgur.com/5UAFQV6.png)
*A list object with 2 properties: head and tail. Both properties have the value of null initially.*

#Manipulating the Linked List

We've covered the structure of each node as well as the structure of our list object. But how can we manipulate the list? How can we add to it? Remove from it? Due to the nature and use case of a list, in most cases you will want to add new values to the end of the list, and remove older values from the front of the list.

####Adding New Nodes to the List

Adding new nodes is simple if all we want to do is add the new node to the tail end of the list.

We can create a function that takes in a value for our new node as a parameter.

Inside this addToList function we create our new Node using our node function from above. Next we check if our list obj has a valid reference to an object in its tail property. If so, we access the current tail object, add a reference our newly created object as its next, and update the tail property of the list to point to the new node.

![Our addToTail function](https://i.imgur.com/7NXe861.png)

####Removing Nodes From the List

As with adding nodes to the end of the list, I'll focus on removing nodes from the front of the list.

Again we create a function to handle this removal process for us. We do not need to assign any parameters as we are only focused on removing the first node. Access the head property of our list.  If its value is pointing to a node, grab the reference to that node and store it in a variable.  Now that we have access to the current head, we can return its value for use in another function and see what the next item in the list is.  So the next order of business is to reassign the head property of list to the next node.  After reassignment, return the oldHead value if needed.
![Our removeFromHead function] (https://i.imgur.com/eEbg435.png)

#Why Use Linked Lists?

Linked lists are iterative in nature. That is to say to find one value, you must have access to the previous.  Going straight to any one value is not easy. That's okay though!  Linked lists are more of a method to create and sustain a queue, or an order of events in which the oldest item (in this case the oldest node) is worked with first. 

Linked lists are great for when there is an indeterminate amount of data to process but it must be processed in a certain order and direct access to the middle of the queue is not needed. These lists can be an important tool for any developer.