1.
Linked lists
Operations on Linked List:
Traversal: We can traverse the entire linked list starting from the head node. If there are
n nodes then the time complexity for traversal becomes O(n) as we hop through each and
every node.
Insertion: Insert a key to the linked list. An insertion can be done in 3 different ways;
insert at the beginning of the list, insert at the end of the list and insert in the middle of
the list.
Deletion: Removes an element x from a given linked list. You cannot delete a node by a
single step. A deletion can be done in 3 different ways; delete from the beginning of the
list, delete from the end of the list and delete from the middle of the list.
Search: Find the first element with the key k in the given linked list by a simple linear
search and returns a pointer to this element
class Node {
// constructor
constructor(element) {
this.element = element;
this.next = null
}
}
// linkedlist class
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
// adds an element at the end
// of list
add(element) {
// creates a new node
var node = new Node(element);
// to store current node
var current;
// if list is Empty add the
// element and make it head
if (this.head == null)
this.head = node;
else {
current = this.head;
// iterate to the end of the
// list
while (current.next) {
current = current.next;
}
// add node
current.next = node;
}
this.size++;
}
// insert element at the position index
// of the list
insertAt(element, index) {
if (index < 0 || index > this.size)
return console.log("Please enter a valid index.");
else {
// creates a new node
var node = new Node(element);
var curr, prev;
curr = this.head;
// add the element to the
// first index
if (index == 0) {
node.next = this.head;
this.head = node;
} else {
curr = this.head;
var it = 0;
// iterate over the list to find
// the position to insert
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// adding an element
node.next = curr;
prev.next = node;
}
this.size++;
}
}
// removes an element from the
// specified location
removeFrom(index) {
if (index < 0 || index >= this.size)
return console.log("Please Enter a valid index");
else {
var curr, prev, it = 0;
curr = this.head;
prev = curr;
// deleting first element
if (index === 0) {
this.head = curr.next;
} else {
// iterate over the list to the
// position to removce an element
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
// remove the element
prev.next = curr.next;
}
this.size--;
// return the remove element
return curr.element;
}
}
// removes a given element from the
// list
removeElement(element) {
var current = this.head;
var prev = null;
// iterate over the list
while (current != null) {
// comparing element with current
// element if found then remove the
// and return true
if (current.element === element) {
if (prev == null) {
this.head = current.next;
} else {
prev.next = current.next;
}
this.size--;
return current.element;
}
prev = current;
current = current.next;
}
return -1;
}
// finds the index of element
indexOf(element) {
var count = 0;
var current = this.head;
// iterate over the list
while (current != null) {
// compare each element of the list
// with given element
if (current.element === element)
return count;
count++;
current = current.next;
}
// not found
return -1;
}
// checks the list for empty
isEmpty() {
return this.size == 0;
}
// gives the size of the list
size_of_list() {
console.log(this.size);
}
// prints the list items
printList() {
var curr = this.head;
var str = "";
while (curr) {
str += curr.element + " ";
curr = curr.next;
}
console.log(str);
}
// creating an object for the
// Linkedlist class
var ll = new LinkedList();
// testing isEmpty on an empty list
// returns true
console.log(ll.isEmpty());
// adding element to the list
ll.add(10);
// prints 10
ll.printList();
// returns 1
console.log(ll.size_of_list());
// adding more elements to the list
ll.add(20);
ll.add(30);
ll.add(40);
ll.add(50);
// returns 10 20 30 40 50
ll.printList();
// prints 50 from the list
console.log("is element removed ?" + ll.removeElement(50));
// prints 10 20 30 40
ll.printList();
// returns 3
console.log("Index of 40 " + ll.indexOf(40));
// insert 60 at second position
// ll contains 10 20 60 30 40
ll.insertAt(60, 2);
ll.printList();
// returns false
console.log("is List Empty ? " + ll.isEmpty());
// remove 3rd element from the list
console.log(ll.removeFrom(3));
// prints 10 20 60 40
ll.printList();
2. Stacks
Operations in a Stack:
1. Push: Add an element to the top of a stack
2. Pop: Remove an element from the top of a stack
3. IsEmpty: Check if the stack is empty
4. IsFull: Check if the stack is full
5. top/Peek: Get the value of the top element without removing it
/ Stack class
class Stack {
// Array is used to implement stack
constructor()
{
this.items = [];
}
// Functions to be implemented
// push(item)
// push function
push(element)
{
// push element into the items
this.items.push(element);
}
// pop function
pop()
{
// return top most element in the stack
// and removes it from the stack
// Underflow if stack is empty
if (this.items.length == 0)
return "Underflow";
return this.items.pop();
}
// peek function
peek()
{
// return the top most element from the stack
// but does'nt delete it.
return this.items[this.items.length - 1];
}
// isEmpty function
isEmpty()
{
// return true if stack is empty
return this.items.length == 0;
}
// printStack function
printStack()
{
var str = "";
for (var i = 0; i < this.items.length; i++)
str += this.items[i] + " ";
return str;
}
}
// creating object for stack class
var stack = new Stack();
// testing isEmpty and pop on an empty stack
// returns false
console.log(stack.isEmpty());
// returns Underflow
console.log(stack.pop());
// Adding element to the stack
stack.push(10);
stack.push(20);
stack.push(30);
// Printing the stack element
// prints [10, 20, 30]
console.log(stack.printStack());
// returns 30
console.log(stack.peek());
// returns 30 and remove it from stack
console.log(stack.pop());
// returns [10, 20]
console.log(stack.printStack());
