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) {
[Link] = element;
[Link] = null
}
}
// linkedlist class
class LinkedList {
constructor() {
[Link] = null;
[Link] = 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 ([Link] == null)
[Link] = node;
else {
current = [Link];
// iterate to the end of the
// list
while ([Link]) {
current = [Link];
}
// add node
[Link] = node;
}
[Link]++;
}
// insert element at the position index
// of the list
insertAt(element, index) {
if (index < 0 || index > [Link])
return [Link]("Please enter a valid index.");
else {
// creates a new node
var node = new Node(element);
var curr, prev;
curr = [Link];
// add the element to the
// first index
if (index == 0) {
[Link] = [Link];
[Link] = node;
} else {
curr = [Link];
var it = 0;
// iterate over the list to find
// the position to insert
while (it < index) {
it++;
prev = curr;
curr = [Link];
}
// adding an element
[Link] = curr;
[Link] = node;
}
[Link]++;
}
}
// removes an element from the
// specified location
removeFrom(index) {
if (index < 0 || index >= [Link])
return [Link]("Please Enter a valid index");
else {
var curr, prev, it = 0;
curr = [Link];
prev = curr;
// deleting first element
if (index === 0) {
[Link] = [Link];
} else {
// iterate over the list to the
// position to removce an element
while (it < index) {
it++;
prev = curr;
curr = [Link];
}
// remove the element
[Link] = [Link];
}
[Link]--;
// return the remove element
return [Link];
}
}
// removes a given element from the
// list
removeElement(element) {
var current = [Link];
var prev = null;
// iterate over the list
while (current != null) {
// comparing element with current
// element if found then remove the
// and return true
if ([Link] === element) {
if (prev == null) {
[Link] = [Link];
} else {
[Link] = [Link];
}
[Link]--;
return [Link];
}
prev = current;
current = [Link];
}
return -1;
}
// finds the index of element
indexOf(element) {
var count = 0;
var current = [Link];
// iterate over the list
while (current != null) {
// compare each element of the list
// with given element
if ([Link] === element)
return count;
count++;
current = [Link];
}
// not found
return -1;
}
// checks the list for empty
isEmpty() {
return [Link] == 0;
}
// gives the size of the list
size_of_list() {
[Link]([Link]);
}
// prints the list items
printList() {
var curr = [Link];
var str = "";
while (curr) {
str += [Link] + " ";
curr = [Link];
}
[Link](str);
}
// creating an object for the
// Linkedlist class
var ll = new LinkedList();
// testing isEmpty on an empty list
// returns true
[Link]([Link]());
// adding element to the list
[Link](10);
// prints 10
[Link]();
// returns 1
[Link](ll.size_of_list());
// adding more elements to the list
[Link](20);
[Link](30);
[Link](40);
[Link](50);
// returns 10 20 30 40 50
[Link]();
// prints 50 from the list
[Link]("is element removed ?" + [Link](50));
// prints 10 20 30 40
[Link]();
// returns 3
[Link]("Index of 40 " + [Link](40));
// insert 60 at second position
// ll contains 10 20 60 30 40
[Link](60, 2);
[Link]();
// returns false
[Link]("is List Empty ? " + [Link]());
// remove 3rd element from the list
[Link]([Link](3));
// prints 10 20 60 40
[Link]();
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()
{
[Link] = [];
}
// Functions to be implemented
// push(item)
// push function
push(element)
{
// push element into the items
[Link](element);
}
// pop function
pop()
{
// return top most element in the stack
// and removes it from the stack
// Underflow if stack is empty
if ([Link] == 0)
return "Underflow";
return [Link]();
}
// peek function
peek()
{
// return the top most element from the stack
// but does'nt delete it.
return [Link][[Link] - 1];
}
// isEmpty function
isEmpty()
{
// return true if stack is empty
return [Link] == 0;
}
// printStack function
printStack()
{
var str = "";
for (var i = 0; i < [Link]; i++)
str += [Link][i] + " ";
return str;
}
}
// creating object for stack class
var stack = new Stack();
// testing isEmpty and pop on an empty stack
// returns false
[Link]([Link]());
// returns Underflow
[Link]([Link]());
// Adding element to the stack
[Link](10);
[Link](20);
[Link](30);
// Printing the stack element
// prints [10, 20, 30]
[Link]([Link]());
// returns 30
[Link]([Link]());
// returns 30 and remove it from stack
[Link]([Link]());
// returns [10, 20]
[Link]([Link]());