educative.io

How to maintain a tail node in singly linked list?( time complexity of O(1) when inserting a node at tail)

Courses
,
#1

Type your question above this line.

Course: https://www.educative.io/collection/5642554087309312/5663204961157120
Lesson: https://www.educative.io/collection/page/5642554087309312/5663204961157120/5712679226310656

#2

@rishabh_jain, here is the code:

index.js

"use strict";
// importing LinkedList and Node class from the respective files.
const LinkedList = require('./LinkedList.js');
const Node = require('./Node.js');
//Access HeadNode => this.head
//Check if list is empty => this.isEmpty() 
//Node class  { data ; Node nextElement;}

//Inserts a value at the end of the list  
LinkedList.prototype.insertAtTail = function(newData) {
  //Creating a new Node with data as newData
  let node = new Node(newData);

  //check for case when list is empty
  if (this.isEmpty()) {
    //Needs to Insert the new node at Head
    this.head = node;
    this.tail=node;  // added this line
    return this;
  }

//Now we have the tail of our LinkedList.
  
  this.tail.nextElement = node; // added this line
  this.tail=node;  // added this line

  return this;
}
let list = new LinkedList()
for (var i = 0; i < 5; i++) {
  list.insertAtTail(i);
  list.printList();
}

LinkedList.js

"use strict";
const Node = require('./Node.js');

module.exports = class LinkedList {
  constructor() {
    this.head = null;
    this.tail=null; //added this line
  }

  //Insertion At Head  
  insertAtHead(newData) {
    let tempNode = new Node(newData);
    tempNode.nextElement = this.head;
    this.head = tempNode;
    return this; //returning the updated list
  }

  isEmpty() {
    return (this.head == null);
  }

  //function to print the linked list
  printList() {
    if (this.isEmpty()) {
      console.log("Empty List");
      return false;
    } else {
      let temp = this.head;
      while (temp != null) {
        process.stdout.write(String(temp.data));
        process.stdout.write(" -> ");
        temp = temp.nextElement;
      }
      console.log("null");
      return true;
    }
  }

  getHead() {
    return this.head;
  }
  getListStr() {
    if (this.isEmpty()) {
      console.log("Empty List");
      return "null";
    } else {
      let st = "";
      let temp = this.head
      while (temp != null) {
        st += String(temp.data);
        st += " -> ";
        temp = temp.nextElement;
      }
      st += "null";
      return st;
    }
  }

}

No change in Node.js