DEV Community

Cover image for Best way to implement linkedList in javascript
Mudacumura Brunoblaise
Mudacumura Brunoblaise

Posted on

Best way to implement linkedList in javascript

Summary: It is important to understand how LinkedList works because they are useful example it is used on the Previous and next page in a web browser

Introduction

Prerequisites

Implementation

Use cases

Introduction

What is a linked list anyway from what Wikipedia says "A linked list is a sequence of nodes that contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list."

well Wikipedia gives a good explanation of LinkedList but what does it look like

Image description

The image has given a sense of what LinkedList visually

Prerequisites

Implementation
Wait...

Image description

Hey before we start I want to wish everyone a nice Friday and weekend

Now it's

Image description

Image description

Let's break it down

class Node {
  constructor(elements, next = null) {
    this.elements = elements;
    this.next = next;
  }
}
Enter fullscreen mode Exit fullscreen mode

we are creating a store where we are going to store our nodes it is doing pretty basic things we are creating a constructor after that it has some parameters we will see their use.

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

}
Enter fullscreen mode Exit fullscreen mode

We are initializing any other class but now we have a null head and size for keeping the length of the linked list now it's time to look at the methods the class uses.

Methods

  • InsertH: inserting the element at the head of the list.

  • add: adding the element at the end of the list.

  • insert: adding any element at the index.

  • deleteL: deleting element at the end.

  • removeFrom: remove any element from the index.

  • indexOf: getting the index of any element.

  • print: we are printing the LinkedList.

insertH(elements) {
    const node = new Node(elements, this.head);

    this.head = node;

    this.size++;
    return node;
  }
Enter fullscreen mode Exit fullscreen mode

This function does basic things first it has a parameter and then in the function we initialize the Node class. Remember the store and now we are changing this.head to the Node of the head stores the node and the left are primary.

add(elements) {
    let node = new Node(elements);

    let current;
    if (this.head === null) {
      this.head = node;
    } else {
      current = this.head;

      while (current.next) {
        current = current.next;
      }

      current.next = node;
    }
    this.size++;
  }
Enter fullscreen mode Exit fullscreen mode

Now we are adding at the last of the list, we are checking if this.head is null if so this.head is set to the node.
if it is not we go and create current= this.head to access the properties of the node after we are looping through the list at the end if we reach there now current.next = node; others are basic.

Allow me to jump and first see the easy to hard.

   indexOf(elements) {
    let current = this.head;
    let it = 0;
    while (current != null) {
      if (current.elements === elements) {
        console.log('elements', current.elements);
        return it;
      }

      it++;
      current = current.next;
    }
    return null;
  }
  print() {
    let current = this.head;

    let str = '';
    while (current) {
      str += current.elements + '-->';

      current = current.next;
    }

    return console.log(str);
  }

  get length() {
    return console.log(this.size);
  }
Enter fullscreen mode Exit fullscreen mode

We are looking that so many methods but they are simply what looks hard is the indexOf which I am going to explain

 indexOf(elements) {
    let current = this.head;
    let it = 0;
    while (current != null) {
      if (current.elements === elements) {
        console.log('elements', current.elements);
        return it;
      }

      it++;
      current = current.next;
    }
    return null;
  }
Enter fullscreen mode Exit fullscreen mode

Here we are treating to get the indexOf any element, now first the current is set to this.head then we create a while loop which first we are checking if the current is not equal to null then outside of the loop we are increasing the it and then set current to current.next then if not the element is not found we return null.

  insert(elements, index) {
    if (index < 0 || index > this.size) return -1;
    else {
      let node = new Node(elements);

      let current, prev, it;

      current = this.head;
      it = 0;
      if (index === 0) {
        this.insertH(elements);
      } else {
        while (it < index) {
          it++;
          prev = current;
          current = current.next;
        }
        node.next = current;
        prev.next = node;
      }
      this.size++;
    }
  }
Enter fullscreen mode Exit fullscreen mode

So the first thing to see is that we create two paraments, the first parameter is getting data and then the second is checking if the index is available then in the function if (index < 0 || index > this.size) return -1; is checking if the index is less than 0 or index is greater than size then we return -1 meaning it is null. In the else statement we initialize the class Node created three variables then set current to this.head, after that we set it because we are going to be using it to insert elements, now we see if the index is zero if so we insert it at the head. if not we loop in the list as long as it is less than index then we set prev to current and then current to current.next then outside the loop

// remove the element
 node.next = current;
 prev.next = node;
Enter fullscreen mode Exit fullscreen mode
removeFrom(index) {
    if (index < 0 || index >= this.size) return -1;
    else {
      let current, prev, it;
      it = 0;
      current = this.head;
      prev = current;
      if (index === 0) {
        this.head = current.next;
      } else {
        while (it < 0) {
          it++;
          prev = current;
          current = current.next;
        }
        prev.next = current.next;
      }
      this.size--;

      return current.elements;
    }
  }
Enter fullscreen mode Exit fullscreen mode

Removing an element in the list at the index is simple as the code above illustrates. First, we are checking if the index is less than zero or index is greater than zero if yes then we return -1 meaning it is null the code following is simple but after w check, if the index is equal to zero then we remove the head in else statement we loop over as long as it, is less than zero then we increment it after as the below code we set prev to current and then current to current.next after that is pretty the basic self-explanatory

 prev = current;
 current = current.next;
Enter fullscreen mode Exit fullscreen mode
  deleteL(elements) {
    let current = this.head;

    let prev = null;
    while (current != null) {
      if (current.elements === elements) {
        if (prev === null) {
          this.head = current.next;
        } else {
          prev.next = current.next;
        }
        this.size--;
        return current.elements;
      }
      prev = current;
      current = current.next;
    }

    return -1;
  }
Enter fullscreen mode Exit fullscreen mode

Well, Well deleting is pretty easy to do as we are going to see, first, we create a variable called current as we have done in many of our codes. I suppose you have become familiar with it notice that prev is set to null now we loop over the list as long as the is not null then we check if current.next is equal to the elements data we inserted in. Then inside the if statement we have another statement that checks if the prev is equal to null we remove the element and in the else statement is the same we decrement the size and the left is basic.

let node = new LinkedList();

node.insertH(1);
node.add(2);

node.add(4);

node.add(5);
node.insert(47, 0);

node.deleteL(1);
console.log(node.indexOf(47));
node.removeFrom(0);

node.length

node.print();
Enter fullscreen mode Exit fullscreen mode

The terminal output

Image description

The full code.

class Node {
  constructor(elements, next = null) {
    this.elements = elements;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  insertH(elements) {
    const node = new Node(elements, this.head);

    this.head = node;

    this.size++;
    return node;
  }

  add(elements) {
    let node = new Node(elements);

    let current;
    if (this.head === null) {
      this.head = node;
    } else {
      current = this.head;

      while (current.next) {
        current = current.next;
      }

      current.next = node;
    }
    this.size++;
  }
  insert(elements, index) {
    if (index < 0 || index > this.size) return -1;
    else {
      let node = new Node(elements);

      let current, prev, it;

      current = this.head;
      it = 0;
      if (index === 0) {
        this.insertH(elements);
      } else {
        while (it < index) {
          it++;
          prev = current;
          current = current.next;
        }
        node.next = current;
        prev.next = node;
      }
      this.size++;
    }
  }

  removeFrom(index) {
    if (index < 0 || index >= this.size) return -1;
    else {
      let current, prev, it;
      it = 0;
      current = this.head;
      prev = current;
      if (index === 0) {
        this.head = current.next;
      } else {
        while (it < 0) {
          it++;
          prev = current;
          current = current.next;
        }
        prev.next = current.next;
      }
      this.size--;

      return current.elements;
    }
  }

  deleteL(elements) {
    let current = this.head;

    let prev = null;
    while (current != null) {
      if (current.elements === elements) {
        if (prev === null) {
          this.head = current.next;
        } else {
          prev.next = current.next;
        }
        this.size--;
        return current.elements;
      }
      prev = current;
      current = current.next;
    }

    return -1;
  }

  indexOf(elements) {
    let current = this.head;
    let it = 0;
    while (current != null) {
      if (current.elements === elements) {
        console.log('elements', current.elements);
        return it;
      }

      it++;
      current = current.next;
    }
    return null;
  }
  print() {
    let current = this.head;

    let str = '';
    while (current) {
      str += current.elements + '-->';

      current = current.next;
    }

    return console.log(str);
  }

  get length() {
    return console.log(this.size);
  }
}

let node = new LinkedList();

node.insertH(1);
node.add(2);

node.add(4);

node.add(5);
node.insert(47, 0);

node.deleteL(1);
console.log(node.indexOf(47));
node.removeFrom(0);

node.length

node.print();

Enter fullscreen mode Exit fullscreen mode

Top comments (0)