DSA LinkedList
1.0.0
Classe de nœud répertorié
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
Classe de liste liée
class LinkedList {
constructor(head = null) {
this.head = head
}
}
Créer une liste liée
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}`;
}
Dans ces exercices, vous vous entraînerez à créer une liste liée, à mettre en œuvre son cœur et à certaines opérations supplémentaires. Vous utiliserez également votre liste liée pour résoudre les questions d'entrevue. N'oubliez pas d'évaluer le Big O pour chacun de ces exercices. Démarrez chaque problème en indiquant 1 ou plus des entrées et des sorties d'échantillons.
Écrivez une classe de liste liée et ces fonctions principales (insertFirst, insertlast, supprimer, trouver) de zéro.
Implémentez les fonctions suivantes qui fonctionnent sur votre classe de liste liée. Notez qu'il doit s'agir de fonctions gratuites au lieu des méthodes de la classe de liste liée, alors implémentez-les en dehors de la classe de liste liée. Testez chaque fonction à l'aide de la liste créée dans l'exercice 1.
Analysez la fonction suivante (sans l'exécuter dans un IDE) pour déterminer quel problème il essaie de résoudre. Quelle est la complexité du temps de cet algorithme?
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;
}
}
Écrivez un algorithme pour inverser une liste liée. La complexité temporelle de votre algorithme doit être linéaire (o (n)). Pour cet exercice, remarquez que nous ne vous demandons pas simplement d'imprimer la liste liée à l'envers ou d'utiliser une autre liste liée pour stocker la valeur dans l'ordre inverse. Votre programme doit inverser la direction d'une liste donnée uniquement liée. En d'autres termes, tous les pointeurs devraient pointer en arrière. Bonus: résolvez ce problème en utilisant à la fois des algorithmes récursifs et itératifs.
Écrivez un algorithme pour trouver le 3ème élément de la fin d'une liste liée. Remarque Vous pouvez être tenté d'ajouter une propriété de longueur à votre classe de liste liée. La propriété Longueur n'est pas une propriété typique de la liste liée, donc ne modifiez aucune modification de la classe Liste liée qui vous est fournie.
Écrivez un algorithme pour trouver l'élément central d'une liste liée. Remarque Vous pouvez être tenté d'ajouter une propriété de longueur à votre classe de liste liée. La propriété Longueur n'est pas une propriété typique de la liste liée, donc ne modifiez aucune modification de la classe Liste liée qui vous est fournie. De plus, trouver la taille de la liste liée à l'aide de la fonction SIZE () et la diviser par moitié ne trouvera pas le bon milieu de la liste liée. Alors, n'utilisez aucune de ces approches.
Écrivez un algorithme pour découvrir si une liste liée a un cycle (c'est-à-dire si un nœud dans la liste a sa prochaine valeur pointant vers un nœud antérieur dans la liste). Pour cet exercice, créez une liste liée au nom Cyclelist. Assurez-vous d'insérer des nœuds dans la liste afin qu'il ait un cycle. Ensuite, testez votre programme avec une fonction cycléliste.
Implémentez une liste doublement liée. Les fonctions principales de la liste doublement liée seraient insérées (d'abord, dernier, avant, après et à), supprimer et trouver. Écrivez une fonction Maindll, et à l'intérieur, créez la DLL de liste doublement liée et ajoutez-y les éléments suivants: Aquaria, Caprica, Gemenon, Picon, Sagittaron.
Compte tenu de la liste doublement liée ci-dessus, écrivez un programme qui inverse la liste doublement liée. En quoi cette implémentation est-elle différente de l'inversion de la liste liée individuellement?
