DSA LinkedList
1.0.0
Listar classe do nó
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
Classe de lista vinculada
class LinkedList {
constructor(head = null) {
this.head = head
}
}
Crie uma lista vinculada
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}`;
}
Nesses exercícios, você praticará a criação de uma lista vinculada, implementando seu núcleo e algumas operações suplementares. Você também usará sua lista vinculada para resolver perguntas da entrevista. Não se esqueça de avaliar o grande O para cada um desses exercícios. Inicie cada problema declarando 1 ou mais entradas e saídas de amostra.
Escreva uma classe de lista vinculada e essas funções principais (insertfirst, insertlast, remover, encontrar) do zero.
Implemente as seguintes funções que operam na sua classe de lista vinculada. Observe que essas devem ser funções gratuitas em vez de métodos da classe List List, então implemente -os fora da classe List List. Teste cada função usando a lista criada no Exercício 1.
Analise a seguinte função (sem executá -la em um IDE) para determinar que problema está tentando resolver. Qual é a complexidade do tempo desse algoritmo?
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;
}
}
Escreva um algoritmo para reverter uma lista vinculada. A complexidade do tempo do seu algoritmo deve ser linear (O (n)). Para este exercício, observe que não estamos pedindo apenas para imprimir a lista vinculada ao contrário ou use outra lista vinculada para armazenar o valor na ordem inversa. Seu programa deve reverter a direção de uma determinada lista de vinculação individual. Em outras palavras, todos os ponteiros devem apontar para trás. Bônus: resolva esse problema usando algoritmos recursivos e iterativos.
Escreva um algoritmo para encontrar o terceiro elemento no final de uma lista vinculada. Nota Você pode ser tentado a adicionar uma propriedade de comprimento à sua classe de lista vinculada. A propriedade Length não é uma propriedade típica da lista vinculada; portanto, não faça nenhuma modificação na classe de lista vinculada fornecida a você.
Escreva um algoritmo para encontrar o elemento intermediário de uma lista vinculada. Nota Você pode ser tentado a adicionar uma propriedade de comprimento à sua classe de lista vinculada. A propriedade Length não é uma propriedade típica da lista vinculada; portanto, não faça nenhuma modificação na classe de lista vinculada fornecida a você. Além disso, encontrar o tamanho da lista vinculada usando a função Size () e dividi -la pela metade não encontrará o meio correto da lista vinculada. Portanto, não use nenhuma dessas abordagens.
Escreva um algoritmo para descobrir se uma lista vinculada possui um ciclo (ou seja, se um nó na lista tem seu próximo valor apontando para um nó anterior na lista). Para este exercício, crie uma lista vinculada com o nome CycleList. Certifique -se de inserir nós na lista para que ela tenha um ciclo. Em seguida, teste seu programa com uma função ciclelista.
Implementar uma lista duplamente vinculada. As funções primárias da lista duplamente vinculada seriam inseridas (primeiro, por último, antes, depois e at), remover e encontrar. Escreva uma função Maindll e, dentro dela, crie a DLL da lista duplamente vinculada e adicione os seguintes itens a ela: Aquaria, Caprica, Gemenon, Picon, Sagittaron.
Dada a lista duplamente vinculada acima, escreva um programa que reverte a lista duplamente vinculada. Como essa implementação é diferente de reverter a lista ligada individual?
