Data structures: Linked List (01)

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: https://www.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 ✨

Singly 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.

Doubly Linked List

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

Time Complexity ✨

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.
4. When you don't need random access to the elements.
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.head = null;
    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);
    if (!this.head) {
      // check if list is empty?
      this.head = newNode; // new head
      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;
  if (!this.head) {
    return;
  }
  // calculate the second last node.
  let currentNode = this.head;
  let secondLastNode = this.head;
  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.head = null;
    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;
  if (!this.head) return;
  // store the current head in a variable.
  const removedHead = this.head; 
  // store the next node of head to be the current head
  this.head = removedHead.next;
  // decrement the length
  this.length--;
 // if length is 0, then reset the list
  if (this.length === 0) {
    this.tail = null;
    this.head = 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).
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      this.length++;
      return;
    }
    // Otherwise, set the next to of new node to current head
    newNode.next = this.head;
   // set the current head of list to new node
    this.head = newNode;
   // increment the length
    this.length++;
    return newNode;
}

---

That's it, folks! hope the first part was a good read for you. Thank you! ✨

👉 Follow me: Github Twitter LinkedIn Youtube