# Data structures: Linked List (01)

## A simple guide to understanding Linked List ๐

Hello everyone! Hope you are doing good โจ

This is the first part of the Linked List Data structure where we will understand what is a linked list and its four operations. For advance operations, please read second part here

In our second article of the Data Structure 101 series, we learned about Arrays. We learned that whenever we want to store data in an organized form, we can use Arrays. But there are several reasons arrays are not always the best data structure to use for organizing data.

In many programming languages, arrays are fixed in length, so it is hard to add new data when the last element of the array is reached. Also, adding and removing data from an array is difficult because you have to move array elements up or down to reflect either an addition or a deletion.

Therefore, we need a more efficient data structure that can be used to store data in an organized form. Luckily, we have one! ๐

## Definition โจ

A linked list is a collection/list of nodes. Each node is linked to a successor node in the list using a reference.

Every node has two parts:

1. Data.
2. Reference of next node.

Image Credits: programiz.com

## Important Concept โจ

• The linked list can be used in almost every situation where a one-dimensional array is used.

• The first node of the linked list is called `head`.

• The last node of the linked list is called `tail`.
• `tail` has always `null` as the `next` reference because it's the last element.
• The `next` is always pointing to the successor node in the list.

## Types Of Linked List โจ

In Singly Linked List, the node has only one reference to the next node in the list. We are going to cover it in this post.

In Doubly Linked List, the node has two references. One to the next node and one of the previous node.

## Time Complexity โจ

 Operation Time Complexity Insertion `O(1)` Deletion `O(1)` Search `O(n)` Access `O(n)`

Space Complexity of Linked List: `O(n)`

## Applications Of Linked List โจ

1. Linked List is heavily used to create stacks and queues.
2. When you need constant-time insertions/deletions from the list.
3. When the size of the list is unknown. This means you don't know how much your list is going to be scaled, then use Linked List instead of Arrays.
5. Remember Priority Queue? You can use a linked list to insert elements in between the list as we do in a priority queue.

## Coding a Linked List in JavaScript โจ

Let's take a look at how to create a Linked List using my favorite language JavaScript.

Let's create a node class that is going to represent a node in the linked list.

``````class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
``````

We have created a `Node` class and inside the constructor of it, we have initialized two properties.

1. `value` - The value of the node. It's the data that we want to store inside the node.
2. `next` - This will contain the reference of the next node. Initially, it's always `null`.

Now that we have the `Node` class in place, let's create the `LinkedList` class that will contain the operations of our linked list.

``````class LinkedList {
constructor() {
this.tail = null;
this.length = 0;
}
}
``````

We have created a class `LinkedList` and inside the constructor method, we are initializing three things.

1. `head`: The start node or the first node of the linked list.
2. `tail`: The last node of the linked list.
3. `length`: A property to store the length of the linked list.

Let's code some operations of the linked list now! โ

### push

In `push`, we insert a node at the end of the linked list.

Here are the steps which we are going to follow while coding `push`.

1. Create a new method `push` that accepts a `value` as an argument.
2. Create a new node using the `Node` class with the `value` passed in.
3. Check if the list is already empty?
• If the list is empty, then assign the new node to the `head` and `tail`. Because right now, we have only one node that is `head` and `tail` both simultaneously.
4. If the list is not empty then:
• Assign the `next` property of the current `tail` to the new node.
• Assign the new node to the `tail` itself.
• Increment the `length` by 1.
``````push(value) {
// Node Creation
const newNode = new Node(value);
// check if list is empty?
this.tail = newNode; // new tail
this.length++;
return this;
}
// on the `next` of last node, add the reference to new node.
this.tail.next = newNode;
// update the last node by the new node.
this.tail = newNode;
// Increment the length;
this.length++;
return this;
}
``````

### pop

In `pop`, we delete a node from the end of the linked list.

Here are the steps which we are going to follow while coding `pop`.

1. Create a new method `pop` that accepts nothing.
2. Check if the list is already empty?
• If the list is empty, then return (Nothing to be removed).
3. If the list is not empty, then we have to calculate second last element because we will set the `tail` of a linked list to the second last element and remove the last one by setting the next property `null` on the current tail.
4. Decrement the `length` by one.
5. If the `length` of the linked list is 0, that means that we have deleted everything from the linked list. So set the `head` and `tail` to `null`.
``````pop() {
// if the head is null, then return null;
return;
}
// calculate the second last node.
while (currentNode.next) {
secondLastNode = currentNode;
currentNode = currentNode.next;
}
// set the second last node to the new tail of the linked list.
this.tail = secondLastNode;
// set the current tail's next to null;
this.tail.next = null;
// decrement the length
this.length--;
// if the length is `this.length` 0 then reset the linked list
if (this.length === 0) {
this.tail = null;
}
return this;
}
``````

### shift

In `shift`, we remove a node at the start of the linked list.

Here are the steps which we are going to follow while coding `shift`.

1. If the `head` is empty, then return.
2. We will store the current `head` in a variable called `removedHead`.
3. We will set the current `head` to the `next` of `removedHead`.
4. Decrement the `length` by one.
5. If the `length` is 0, then set the tail to `null`
``````shift() {
// check if there is no head then return;
// store the current head in a variable.
// store the next node of head to be the current head
// decrement the length
this.length--;
// if length is 0, then reset the list
if (this.length === 0) {
this.tail = null;
}
return this;
}
``````

### unshift

In `unshift`, we add a node at the start of the linked list.

Here are the steps which we are going to follow while coding `unshift`.

1. Create a method `shift` in the class which is going to accept the `value` of the node as an argument.
2. Create a new node from the `Node` class.
3. If the `head` is empty, then make the `head` and `tail` the new node.
4. Set the `next` property on the new node to the current `head`.
5. Set the new node as the new `head` of the linked list.
6. Increment the `length` by one.
``````unshift(value) {
// create a new node
const newNode = new Node(value);
// if the head is empty, make the new node the head and tail (first node).
this.tail = newNode;
this.length++;
return;
}
// Otherwise, set the next to of new node to current head