DSA LinkedList
1.0.0
Список узел класса
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
Связанный список класса
class LinkedList {
constructor(head = null) {
this.head = head
}
}
Создать связанный список
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}`;
}
В этих тренировках вы будете практиковать создание связанного списка, внедряя его ядро и некоторые дополнительные операции. Вы также будете использовать свой связанный список для решения вопросов интервью. Не забудьте оценить большой O для каждого из этих упражнений. Запустите каждую проблему, указав 1 или более входов и более выборок.
Напишите связанный класс списка и эти основные функции (вставьтефирст, вставьте, удалить, найти) с нуля.
Реализуйте следующие функции, которые работают в вашем классе связанных списков. Обратите внимание, что это должны быть бесплатные функции, а не методы связанного класса списка, поэтому реализуйте их вне связанного списка класса. Проверьте каждую функцию, используя список, созданный в упражнении 1.
Проанализируйте следующую функцию (без запуска ее в IDE), чтобы определить, какую проблему она пытается решить. Какова сложность времени этого алгоритма?
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;
}
}
Напишите алгоритм, чтобы отменить связанный список. Временная сложность вашего алгоритма должна быть линейной (O (n)). Для этого упражнения обратите внимание, что мы не просим вас просто распечатать связанный список в обратном порядке или использовать другой связанный список для хранения значения в обратном порядке. Ваша программа должна изменить направление данного отдельного списка. Другими словами, все указатели должны указывать назад. Бонус: решить эту проблему, используя как рекурсивные, так и итерационные алгоритмы.
Напишите алгоритм, чтобы найти 3 -й элемент из конца связанного списка. Обратите внимание, что у вас может возникнуть соблазн добавить свойство длины в свой класс связанных списков. Свойство длины не является типичным свойством связанного списка, поэтому не вносите никаких изменений в связанный список списков, который вам предоставлен.
Напишите алгоритм, чтобы найти средний элемент связанного списка. Обратите внимание, что у вас может возникнуть соблазн добавить свойство длины в свой класс связанных списков. Свойство длины не является типичным свойством связанного списка, поэтому не вносите никаких изменений в связанный список списков, который вам предоставлен. Кроме того, поиск размера связанного списка с использованием функции Size () и разделения его на половину не найдет правильную середину связанного списка. Так что не используйте ни один из этих подходов.
Напишите алгоритм, чтобы обнаружить, имеет ли связанный список цикл (т.е., есть ли узел в списке свое следующее значение, указывающее на более ранний узел в списке). Для этого упражнения создайте связанный список с именем Cyclelist. Обязательно вставьте узлы в список, чтобы он имел цикл. Затем протестируйте свою программу с помощью функции Cyclelist.
Реализуйте дважды связанный список. Основными функциями вдвойне связанного списка будут вставлены (сначала, последнее, до, после, и в), удалить и найти. Напишите функцию maindll, и внутри нее создайте двойной связанный список DLL и добавьте в нее следующие элементы: Aquaria, Caprica, Gemenon, Picon, Sagitaron.
Учитывая вдвойне связанный список выше, напишите программу, которая меняет дважды связанный список. Чем эта реализация отличается от переворота в одиночном связанном списке?
