DSA LinkedList
1.0.0
Listen Sie die Knotenklasse auf
class ListNode {
constructor(data) {
this.data = data
this.next = null
}
}
Verknüpfte Listenklasse
class LinkedList {
constructor(head = null) {
this.head = head
}
}
Erstellen Sie verknüpfte Liste
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 diesen Übungen üben Sie, eine verknüpfte Liste zu erstellen, um ihren Kern zu implementieren, und einige zusätzliche Operationen. Sie werden auch Ihre verknüpfte Liste verwenden, um Interviewfragen zu lösen. Vergessen Sie nicht, das große O für jede dieser Übungen zu beurteilen. Starten Sie jedes Problem, indem Sie 1 oder mehr Probeneingänge und Ausgänge angeben.
Schreiben Sie eine verknüpfte Listenklasse und diese Kernfunktionen (InsertFirst, InsertLast, entfernen, finden) von Grund auf neu.
Implementieren Sie die folgenden Funktionen, die in Ihrer verknüpften Listenklasse funktionieren. Beachten Sie, dass dies kostenlose Funktionen anstelle von Methoden der verknüpften Listenklasse sein sollten. Implementieren Sie sie daher außerhalb der verknüpften Listenklasse. Testen Sie jede Funktion mit der in Übung 1 erstellten Liste.
Analysieren Sie die folgende Funktion (ohne sie in einer IDE auszuführen), um zu bestimmen, welches Problem sie lösen versucht. Was ist die Zeitkomplexität dieses Algorithmus?
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;
}
}
Schreiben Sie einen Algorithmus, um eine verknüpfte Liste umzukehren. Die zeitliche Komplexität Ihres Algorithmus sollte linear sein (o (n)). Beachten Sie bei dieser Übung, dass wir Sie nicht nur fragen, die verknüpfte Liste in umgekehrt zu drucken oder eine andere verknüpfte Liste zu verwenden, um den Wert in umgekehrter Reihenfolge zu speichern. Ihr Programm sollte die Richtung einer bestimmten einzig verknüpften Liste umkehren. Mit anderen Worten, alle Zeiger sollten rückwärts zeigen. Bonus: Lösen Sie dieses Problem mit rekursiven und iterativen Algorithmen.
Schreiben Sie einen Algorithmus, um das dritte Element am Ende einer verknüpften Liste zu finden. Beachten Sie, dass Sie möglicherweise versucht sind, Ihrer verknüpften Listenklasse eine Länge -Eigenschaft hinzuzufügen. Die Länge Eigenschaft ist keine typische Eigenschaft der verknüpften Liste. Nehmen Sie daher keine Änderung der Ihnen bereitgestellten Listenklasse vor, die Ihnen zur Verfügung gestellt wird.
Schreiben Sie einen Algorithmus, um das mittlere Element einer verknüpften Liste zu finden. Beachten Sie, dass Sie möglicherweise versucht sind, Ihrer verknüpften Listenklasse eine Länge -Eigenschaft hinzuzufügen. Die Länge Eigenschaft ist keine typische Eigenschaft der verknüpften Liste. Nehmen Sie daher keine Änderung der Ihnen bereitgestellten Listenklasse vor, die Ihnen zur Verfügung gestellt wird. Wenn Sie die Größe der verknüpften Liste mit der Funktion der Größe () und der Hälfte durch die Hälfte finden, finden Sie auch nicht die richtige Mitte der verknüpften Liste. Verwenden Sie also keinen dieser Ansätze.
Schreiben Sie einen Algorithmus, um festzustellen, ob eine verknüpfte Liste einen Zyklus hat (dh, ob ein Knoten in der Liste den nächsten Wert hat, der auf einen früheren Knoten in der Liste zeigt). Erstellen Sie für diese Übung eine verknüpfte Liste mit dem Namen Cyclelist. Stellen Sie sicher, dass Sie Knoten in die Liste einfügen, damit es einen Zyklus hat. Testen Sie dann Ihr Programm mit einer Cyclelist -Funktion.
Implementieren Sie eine doppelt verknüpfte Liste. Die primären Funktionen der doppelt verknüpften Liste würden einfügen (zuerst, vor, nach und bei), entfernen und finden. Schreiben Sie eine Funktion MainDll und erstellen Sie die doppelt verknüpfte Liste DLL und fügen Sie die folgenden Elemente hinzu: Aquaria, Caprica, Gemenon, Picon, Sagittaron.
Schreiben Sie angesichts der doppelt verknüpften Liste oben ein Programm, das die doppelt verknüpfte Liste umkehrt. Wie unterscheidet sich diese Implementierung von der Umkehrung der einzig verknüpften Liste?
