DSA LinkedList
1.0.0
List Node Class
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
Linked List Class
class LinkedList {
constructor(head = null) {
this.head = head
}
}
Create Linked List
let node1 = new ListNode(2)
let node2 = new ListNode(5)
node1.next = node2
let list = new LinkedList(node1)
console.log(list.head.next.data) //returns 5
size() {
let count = 0;
let node = this.head;
while (node) {
count++;
node = node.next
}
return count;
}
const ListFunctions = {
display: (linkedList) => {
items = [];
if (linkedList.head === null) {
return "The list is empty";
} else {
let currNode = linkedList.head;
while (currNode.next !== null) {
items.push(currNode.data);
currNode = currNode.next;
}
items.push(currNode.data);
}
return `Linked List Items: ${items.join("->")}`;
}
isEmpty: (linkedList) => {
if (linkedList.head === null) {
return `This list is empty`;
}
return `There are items in this list`;
}
find(item) {
let currNode = this.head;
if (!this.head) {
return null;
}
while (currNode.data !== item) {
if (currNode.next === null) {
return null;
} else {
currNode = currNode.next;
}
}
return currNode;
}
}
clear() {
this.head = null;
}
remove(item) {
if (!this.head) {
return null;
}
if (this.head.data === item) {
this.head = this.head.next;
return;
}
let currNode = this.head;
let previousNode = this.head;
while (currNode !== null && currNode.data !== item) {
previousNode = currNode;
currNode = currNode.next;
}
if (currNode === null) {
return;
}
previousNode.next = currNode.next;
}
insertFirst(item) {
this.head = new _Node(item, this.head);
}
insertLast(item) {
if (this.head === null) {
this.insertFirst(item);
} else {
let tempNode = this.head;
while (tempNode.next !== null) {
tempNode = tempNode.next;
}
tempNode.next = new _Node(item, null);
}
}
insertBefore(item, key) {
if (!this.head) {
return;
}
if (this.head.data === key) {
this.insertFirst(item);
return;
}
let currNode = this.head;
let previousNode = this.head;
while (currNode !== null && currNode.data !== key) {
previousNode = currNode;
currNode = currNode.next;
}
if (currNode === null) {
console.log(`key value not found`);
return;
}
previousNode.next = new _Node(item, currNode);
}
insertAfter(item, key) {
if (!this.head) {
return;
}
if (this.head.data === key) {
this.insertFirst(item);
return;
}
let currNode = this.head;
let nextNode = this.head;
while (currNode !== null && currNode.data !== key) {
currNode = nextNode;
nextNode = nextNode.next;
}
if (currNode === null) {
console.log(`key value not found`);
return;
}
currNode.next = new _Node(item, nextNode);
}
getLast() {
let lastNode = this.head;
if (lastNode) {
while (lastNode.next) {
lastNode = lastNode.next
}
}
return lastNode
}
getFirst() {
return this.head;
}
findPrevious: (linkedList, key) => {
if (linkedList.head === null) {
return null;
}
let prevNode;
let currNode = linkedList.head;
while (currNode.data !== key) {
prevNode = currNode;
currNode = currNode.next;
}
return `The previous node is ${prevNode.data}`;
}
In these drills, you'll practice creating a linked list, implementing its core, and some supplemental operations. You will also use your linked list to solve interview questions. Don't forget to assess the big O for each of these exercises. Start each problem by stating 1 or more sample inputs and outputs.
Write a linked list class and these core functions (insertFirst, insertLast, remove, find) from scratch.
Implement the following functions that operate on your linked list class. Note that these should be free functions instead of methods of the linked list class, so implement them outside the linked list class. Test each function using the list created in exercise 1.
Analyze the following function (without running it in an IDE) to determine what problem it is trying to solve. What is the time complexity of this algorithm?
function WhatDoesThisProgramDo(lst) {
let current = lst.head;
while (current !== null) {
let newNode = current;
while (newNode.next !== null) {
if (newNode.next.value === current.value) {
newNode.next = newNode.next.next;
}
else {
newNode = newNode.next;
}
}
current = current.next;
}
}
Write an algorithm to reverse a linked list. The time complexity of your algorithm should be linear (O(n)). For this exercise, notice we are not asking you just to print the linked list in reverse or use another linked list to store the value in reverse order. Your program should reverse the direction of a given singly linked list. In other words, all pointers should point backward. BONUS: Solve this problem using both recursive and iterative algorithms.
Write an algorithm to find the 3rd element from the end of a linked list. Note You may be tempted to add a length property to your linked list class. The length property is not a typical property of linked list, therefore don't make any modification to the linked list class that is provided to you.
Write an algorithm to find the middle element of a linked list. Note You may be tempted to add a length property to your linked list class. The length property is not a typical property of linked list, therefore don't make any modification to the linked list class that is provided to you. Also, finding the size of the linked list using the size() function and dividing it by half will not find the correct middle of the linked list. So, don't use either of these approaches.
Write an algorithm to find whether a linked list has a cycle (i.e., whether a node in the list has its next value pointing to an earlier node in the list). For this exercise, create a linked list with the name CycleList. Be sure to insert nodes in the list so that it has a cycle. Then test your program with a cycleList function.
Implement a doubly linked list. The primary functions of the doubly linked list would be insert (First, Last, Before, After, and At), remove, and find. Write a function mainDLL, and within it create the doubly linked list DLL and add the following items to it: Aquaria, Caprica, Gemenon, Picon, Sagittaron.
Given the doubly linked list above, write a program that reverses the doubly linked list. How is this implementation different than reversing the singly linked list?
