Linked List

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

The initial state of a linked list will be empty. It has no nodes and the start points to a null.

Now we can start adding data. There are two ways to add data: 1) Append it to the end of the list. 2) Add it on a given position.

Let's first append two numbers (10 and 20) to the list

Here's the code for append operation:

append(item) {
  if(this.start === null){
    this.start = new LinkedListNode(item, null);
    this.end = this.start;
  }
  else{
    let tempNode = this.start;
    while (tempNode.next !== null) {
      tempNode = tempNode.next;
    }
    tempNode.next = new LinkedListNode(item, null);  
    this.end = tempNode.next;
  }
}

Now our list has two numbers in the order: 10, 20. Now let's add number 30 on index: 1 (remember in computer science order starts from 0).

Here's the code for insertAtIndex operation:

insert(item, index) {
  const length = this.length();
  if (length <= index) {
    this.append(item);
  } else {
    let currentNode = this.start;
    let i = 0;
    if(index===0){
      currentNode = new LinkedListNode(item, this.start);
      this.start = currentNode;
    } else{
      let prevNode;
      while (i !== index) {
        i++;
        prevNode = currentNode;
        currentNode = currentNode.next;
      }
      prevNode.next = new LinkedListNode(item, currentNode);  
    }
  }
}

Now our list has three numbers in the order: 10, 30, 20. We can add a function to delete a node from our list. Let's delete the first occurrence of the number 20.

Here's the code for delete operation:

deleteItem(item) {
  let currentNode = this.start;
  let prevNode = this.start;
  while (currentNode !== null) {
    if (currentNode.item === item) {
      if(currentNode === this.start){
        this.start = this.start.next;
      } else {
        prevNode.next = currentNode.next;
      }
      break;
    }
    prevNode = currentNode;
    currentNode = currentNode.next;
  }
}

We can also implement an operation to delete at a given index:

deleteItemAtIndex(index){
  const listLength = this.length();
  if (listLength < index) {
    return null;
  } else {
    let currentNode = this.start;
    let prevNode;
    let i = 0;
    while (i !== index) {
      i++;
      prevNode = currentNode;
      currentNode = currentNode.next;
    }
    const item = currentNode.item;
    if(i===0){
      this.start = this.start.next;
      return item;
    } else {
      prevNode.next = currentNode.next;
      if(i===listLength-1){
        this.end = prevNode;
      }
      return item;  
    }
  }
}

Similarly we can add more functions like search and reversal of the list.

Check out this link for implementation of this data structure using JavaScript.

Follow me on Twitter, Linkedin

Check out my portfolio at https://tejender-singh.github.io/