# Completed JavaScript Data Structure Course, and Here is What I Learned About Linked List.

### Maiko M ・6 min read

It took a month to complete JavaScript Algorithms and Data Structures course on Udemy, and it was absolutely stimulating. Before taking the course, I created a Chrome Extension but I was only able to implement arrays and simple objects. I didn’t even know that data can be inefficient if we use inappropriate data structures.

The Chrome Extension I created is for language learners, and users can create their own vocabulary list and save them at the corner of their browser.

Basically I was only using simple arrays and objects to store three types of data in chrome local storage, and using the built-in **unshift** method to store the main vocabulary data -- which took **O(n)** time complexity.

The main data looked like this:

```
//result of console.log(vocabulary-data)
0: {category: "cat1", id: "4", meaning: "information of the vocabulary.", tag: ["tag1", "tag2"], word: "Example Vocab 1"}
1: {category: "cat3", id: "3", meaning: "Hello World", tag: ["tag1", "tag4"], word: "Example Vocab 2"}
2: {category: "cat2", id: "2", meaning: "This is new vocabulary.", tag: ["tag4"], word: "Example"}
3: {category: "cat4", id: "1", meaning: "You can write anything.", tag: ["tag2", "tag4", "tag5"], word: "Sample"}
```

I also wanted to implement features to remove/edit each vocabulary efficiently. But as long as it's this structure, **removing/editing** a single element also takes **O(n)** time complexity because it involves re-indexing the whole data.

I realized that it shouldn't be the smartest way, but then, what is?

Well, at that time, I didn't have a clue. That's because I had just started the course, and each data structure has its advantage, so I couldn't decide until I compare all the data structures that I'll be learning during the course.

What I learned first on the course were linked lists. So in this article, I'm going to investigate whether the linked list is suitable for the data or not. And then, I am going through other data structures in future articles.

#
**Is Singly Linked List a Good Choice?**

Singly linked list looks like this visually:

Each box is called a node, and they don’t have indexes. Instead, you need to define what is the starting node(**head**) and the end(**tail**), and **each node contains an arrow to point out which the next node is**.

### Define Node and Singly linked list

To define Node and Singly linked list in JavaScript, it will look like this:

```
// define Node
class Node{
constructor(val) {
// store value in val
this.val = val;
// define next node in next
this.next = null;
}
}
// define singly linked list
class SinglyLinkedList{
constructor() {
// define what node is head and tail
this.head = null;
this.tail = null;
// define how many node in the list
this.length = 0;
}
}
```

### Add node at the end of the list (push)

To add a node at the end of the list, you just need to (1)**point out the current tail’s next arrow to the new node**, and (2)**define the new node as the new tail**.

```
push(val) {
// create a node with the value
let newEl = new Node(val);
if (!this.head) {
// if nothing in the list, the node will be both the head and tail
this.head = newEl;
this.tail = newEl;
} else {
// otherwise, the node will be placed as the tail
this.tail.next = newEl;
this.tail = newEl;
}
// increment the length of the list
this.length += 1;
return this;
}
```

Pushing takes **O(1)** complexity because it doesn't affect the other data. However, inserting an element in the middle of the list is a different story.

### Inserting node in the middle of the list

Firstly, create a method called **get** to find the location where to insert the node. There is no index to the each node, so that we can only find location by counting from the beginning of the list.

Here is the example of how to find a node:

```
// define a number (num) where to find the node
get(num) {
if(num < 0 || num >= this.length) return null;
// initialize the head as item
let item = this.head;
for (let i = 0; i < this.length; i++) {
// if the item is at the location that you are looking for, return the item
if(i === num) return item;
// else move on to the next node
item = item.next;
}
}
```

And then, we can insert a node by using **get**.

```
insert(index, value) {
if (index < 0 || index > this.length) return false;
// if the location we want to insert is the end/the beginning of the list, we just use push/unshift.
if (index === this.length) return !!this.push(value);
if (index === 0) return !!this.unshift(value);
// create new node with the value
let newNode = new Node(value);
// define which will be prev and next when inserting the new node
let prev = this.get(index-1);
let next = this.get(index);
// point out next arrow of previous node to the new node
prev.next = newNode;
// point out next arrow of new node to the next node
newNode.next = next;
// increment the length of the list
this.length++;
return true;
}
```

It is not the most efficient data structure if you are **editing/deleting** node often, because finding a node takes O(n) complexity.

###
**Is singly linked list useless?**

In the beginning, I thought singly linked list is useless, but it’s actually useful **if the node already exists somewhere else**, and also **if it doesn’t require removing/editing nodes often**. For example, music streaming services might be using it when it comes to shuffling random music. Some of the services, we can’t go back to previous music if we are using the free version, and in that case, singly linked list contains functions only what it needs.

#
**How About Doubly Linked List?**

Doubly linked list is almost the same as singly linked list, but each node contains **another arrow to point out the previous node** as well as the next node. It looks like this visually:

In this case, if you implement it to the music streaming example that I mentioned earlier, you can forward the playlist and also go back to previous music. As well as singly linked list, it doesn’t require to crone each node and you just need to connect previous/next music with arrows. So I think general playlists on music streaming service can be a good example of doubly linked list.

To implement it in JavaScript, simply add **this.prev** property.

It will look like this:

```
class Node {
constructor(val) {
// store value in val
this.val = val;
// define next node in next
this.next = null;
// define previous node in prev
this.prev = null;
}
}
class DoublyLinkedList {
constructor() {
// same as singly linked list
// define what node is head and tail
this.head = null;
this.tail = null;
// define how many node in the list
this.length = 0;
}
}
```

To add a node at the end of the list, you just need to (1)**point out the current tail’s next arrow to the new node**, and (2)**define the new node as the new tail**. Also, don’t forget to (3)**point out the new tail’s prev to the old tail**.

```
push(val) {
// create new node with value
let newNode = new Node(val);
if(!this.head) {
// if nothing in the list, the new node is both head and tail
this.head = newNode;
this.tail = this.head;
} else {
// otherwise, define current tail as currentTail
let currentTail = this.tail
// point out next arrow of currentTail to new node
currentTail.next = newNode;
// point out prev arrow of new node to currentTail
newNode.prev = currentTail;
// define new node as tail
this.tail = newNode;
}
this.length += 1;
return this;
}
```

# Conclusion

Both of the linked lists are not suitable for my chrome extension project because removing/editing elements are required regularly. These data structures work well if you are going to display each element one by one, but if you want to display all the data/selected data on a single page, then there’s no point using a linked list.

In the next article, I'm going to write about stacks and queues.

Thanks for reading, please leave a comment if you find any information useful or wrong in this article. I would much appreciate!

I found it very good explanation and actually using a real world sample help me out. Easy to follow even if I dont know javascript.

Keep the images!

Thank you so much for your words! I'm glad it helped! :)