Data Structures: Linked List (02)

Welcome to the second part of the Linked List data structure 🙌

You can find the first part here 👻

In the previous part, we covered the introduction, types, applications, and some of the operations of the Linked List.

In this part, we are going to cover the remaining operations of Linked List.

We are using Singly Linked List for now.

Here is the list of remaining operations which we are going to cover in this post.

1. get()
2. set()
3. insert()
4. remove()
5. reverse()

Let's jump in! 🥷🏻

Get

The get method is used to fetch the value of a node at a particular index. Note that a Linked List does not have an indexing system. Instead, it has a pointing system. For fetching the items from particular locations, we can write our own indexing mechanism for it.

Here are the steps which we are going to take for writing the get method.

1. Create a method named get that is going to accept an index argument of type number.
2. Check if the index is valid or not. If the index is not valid then return.
3. Create a variable currentIndex which will start from 0.
4. Create a variable result which will start from the head. We will rewrite it when we will found the requested element.
5. Write a while loop, that will update the result variable to next of result if the index is not equal. This is our searching criteria.
6. Return the result.

get(index) {
    // Check if the index is valid or not.
    if (index < 0 || index >= this.length) {
      return;
    }
    // start the index from 0
    let currentIndex = 0;
    let result = this.head;
    // Loop over the list till the index is not matched and 
    // update the result variable accordingly. 
    while (currentIndex !== index) {
      currentIndex++;
      result = result.next;
    }
    // return the result
    return result;
 }

Set

The set method is used to update the value of a node using the index. In simple words, as the name of the method describes, it sets the value of a node 😉

Here are the steps which we are going to take for writing the set method.

1. Create a method named set that is going to accept two arguments

   • index of type number.
   • value of any type.

2. We will use the get method which we have defined to get the node using index.

3. If we have found the node, then we will update the value.

set(index, value) { 
    // Find the node using get method
    let node = this.get(index);
    if (node) { 
      // If the node is found, update the value
      node.value = value;
    }
}

Insert

The insert method is used to insert a node in a Linked List at the provided location. The location is provided by index.

Here are the steps which we are going to take for writing the insert method.

1. Create a method insert that is going to accept two arguments.
   • index of type number.
   • value of any type.
2. Check if the index is valid or not. If the index is not valid, return.
3. Check if the index is equal to the length of the Linked List. If it is equal then we have to add the element at the end of the list. For this purpose, we can use the push method and return immediately.
4. Check if the index is equal to the 0, then we have to add the element at the start of the list. For this purpose, we can use the unshift method and return immediately.
5. If the location is not first or last, then use the get method to find the previous node to the location provided by index.
6. Create a new node using the Node class (covered in the previous post).
7. Set the newNode.next to the previousNode.next because the next of previousNode will always contain the next node reference and we are adding a node in between them.
8. Set the previousNode.next to the newNode.
9. Increment the length by one.

 insert(index, value) {
    // check if the index is valid or not.
    if (index < 0 || index > this.length) return;
   // if last node, use push
    if (index === this.length) {
      this.push(value);
      return this;
    }
    // if first node, use unshift.
    if (index === 0) {
      this.unshift(value);
      return this;
    }
    // get the previous node
    const previousNode = this.get(index - 1);
   // create a new node
    const newNode = new Node(value);
   // set the newNode.next to previousNode.next
    newNode.next = previousNode.next;
   // set the previousNode.next  to the newNode
    previousNode.next = newNode;
    // increment the length
    this.length++;
    return this;
}

Remove

The remove method is used to remove a node in a Linked List at the provided location. The location is provided by index.

Here are the steps which we are going to take for writing the remove method.

1. Create a method remove that is going to accept one argument i.e index of type number.
2. Check if the index is valid or not. If the index is not valid, return.
3. Check if the index is equal to the length of the Linked List. If it is equal then we have to remove the element at the end of the list. For this purpose, we can use the pop method and return immediately.
4. Check if the index is equal to the 0, then we have to remove the element at the start of the list. For this purpose, we can use the shift method and return immediately.
5. If the location is not first or last, then use the get method to find the previous node to the location provided by index.
6. Get the previousNode by using index-1 as location in get method.
7. Now, the previousNode.next will hold the reference to the node that is going to be deleted. Store it in a variable called deletedNode.
8. Set the previousNode.next to the deletedNode.next.
9. Decrement the length by one.

  remove(index) {
    // Check if the index is valid or not.
    if (index < 0 || index > this.length) return;
    // If last node, use pop
    if (index === this.length) {
      this.pop();
      return;
    }
     // If last node, use shift
    if (index === 0) {
      this.shift();
      return;
    }
    // get the previous node
    const previousNode = this.get(index - 1);
    // store the .next of previous node in deleted node.
    const deletedNode = previousNode.next;
   // set the previousNode.next to deletedNode.next.
    previousNode.next = deletedNode.next;
    // decrement the length
    this.length--;
    return this;
}

Reverse

The reverse method is used to reverse a Linked List. We will reverse the list by inverting the references to the next.

Here are the steps which we are going to take for writing the reverse method.

1. Create a variable previous that will store the reference of the previous node. At the start, it will be null.
2. Create a variable called currentNode and store this.head as first node.
3. Loop over the list:
   • Store the nextof node in a variable called currentNode.
   • Set the currentNode.next to previous. Here we are inverting the references.
   • Set the previous to currentNode.
   • Set the currentNode to next

reverse() { 
  // initially, previous will be null;
  let previous = null; 
  // head as first node. We are creating the clone of head for breaking the reference. 
  // JSON.parse(JSON.stringify(this.head)) will return a new object that will be pointing to a new location in memory. 
  let currentNode = JSON.parse(JSON.stringify(this.head));
  // loop over the list
  while(currentNode !== null) { 
     // store the next of current node into next
     let next = currentNode.next; 
    // invert the reference 
     currentNode.next = previous;
    // set new previous
     previous = currentNode
    //  set new currentNode
     currentNode = next;
  }
  return previous;
};

---

Please find the complete code of the Linked List below 👇

---

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

👉 Follow me: Github Twitter LinkedIn Youtube