Learning Linked Lists
Tags: beginners, javascript, computerscience, algorithms
Published: 2020-07-04 18:55:55

I'll start by going over the basics. What is a linked list?

A linked list is a form of data structure. In a linked list the data in the structure is connected together in a sequence of objects. Take a look at this diagram from Wikipedia to better understand. 

![Linked List Diagram from Wikipedia](https://dev-to-uploads.s3.amazonaws.com/i/7mxbvnnevi9csbq6bgct.png)

Each segment (or what is commonly referred to as a node) has two parts. The data it stores, and a pointer that references the next element in the chain. 

Fun fact, a node is defined as "a place where a leaf and stem join on a plant." 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/kqqwu984ij5ku500a1xq.jpeg)

This makes sense when thinking about data structures, each node is a new path that originates from the same structure.

Now that all of this makes sense in theory, how does it look when we implement it in code? Well a node could look like this. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/mnq234r2v00iq9inrq3n.png)

Then to create nodes all we would need to do is something like `node1 = new Node(5) node2 = newNode(4)`. Now we have two nodes, one containing the integer 5 and the other containing the integer 4, but they both have no form of connection. To manage our nodes a good solution is to create another class for the list itself.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/y3irsu2rhinenxjvhfvi.png)

Now we have a class for the list but no way to add in any of our nodes. So let's add it a method that utilizes our node class.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/lsawn4e85dxbwtpgw49u.png)

Let's go through what this is doing step by step. We pass in the data that we want to add to our list. We then create a new node containing that data. We see if the linked list has any nodes, if it doesn't we assign that node to be the head (the name for the first node in a linked list). If there is already a head we initialize a current variable that will help us keep track of which node we are looking at and set it to be the head. We then iterate through the list to the end with a while loop. Then we add in our new node to the end of the list.

This is only the bare bone functionality that needs to be in a linked list. What if we wanted to remove an node from the list? Count how many nodes there are in the list? Insert a node in a specific index in the list. Think about how you could implement these methods in the LinkedList class.

Another thing to think about. You probably noticed that because the nodes in a linked list only reference the **next** node, it's impossible to navigate backwards through the list. 

There's actually another structure called a doubly linked list that, you guessed it, contains **two** pointers. One pointing to the next node, and on pointing to the previous node. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/5iidppmgc68j692mp3wp.png)

Think about how you would implement this in the code examples that we went over and what new functionality you could add!

If you want to start with the code from this post, you can get it [here](https://github.com/123JackCole/linked_lists).