Entfernen des k-ten Index aus der verknüpften Liste in einem Durchgang  Willkommen zurück, ich habe ein weiteres Problem zu lösen! Heute befassen wir uns mit verknüpften Listen und der Entfernung ihrer Elemente. Wir besprechen ein wenig darüber, was verknüpfte Listen sind, erstellen eine und sehen, wie man Elemente daraus entfernt.  Bevor Sie beginnen, die üblichen Haftungsausschlüsse:  Diese Probleme liefert der wunderbare Newsletter Daily Coding Problem, den Sie abonnieren können  . Probieren Sie es aus und versuchen Sie auch, Ihre Herausforderungen zu lösen!   Hier  Ich bin kein erfahrener Programmierer: Nur ein Typ, der seine Aufnahmen gerne teilt! Wenn Sie zufällig eine bessere oder schnellere Lösung für einen Algorithmus haben, teilen Sie diese bitte in den Kommentaren mit! Ich würde gerne mehr darüber erfahren!  Genug Lärm; Kommen wir zum Problem!  Entfernen Sie     den k-ten Knoten vom Ende der Liste und geben Sie den Kopf der Liste zurück. bei einer verknüpften Liste und einer Ganzzahl k    ist garantiert kleiner als die Länge der Liste. k   Tun Sie dies in einem Durchgang.  Also gut, lassen Sie uns ein wenig erklären, was hier passiert: Wir erhalten eine verknüpfte Liste und ein Indexelement   , das aus der Liste entfernt werden soll. Danach sollten wir den Kopf der verknüpften Liste zurückgeben. k  Schließlich müssen wir dies alles in nur einem Durchgang erledigen, was bedeutet, dass wir die Liste nicht mehr als einmal durchlaufen können.  Außerdem wird garantiert, dass der Index   in der Liste   ist, sodass wir nicht prüfen müssen, ob er über die tatsächliche Länge der Liste hinausgeht. k enthalten  Wir werden heute Go verwenden, um den Algorithmus zu erstellen, da seine Syntax für diese Art von Aufgabe großartig ist und gleichzeitig ziemlich einfach zu verstehen bleibt.  Beginnen wir von vorne: Erstellen einer einfachen verknüpften Liste.  Die verknüpfte Liste  Das Konzept hinter der verknüpften Liste ist ziemlich einfach: Es handelt sich um eine Liste aus Objekten (normalerweise als   bezeichnet), und jeder Knoten muss mindestens zwei Eigenschaften haben: einen   (etwas, das tatsächlich im Knoten enthalten ist) und einen   zum nächsten Knoten. Knoten Wert Link  Normalerweise wird ein   als Link verwendet, um von einem Knoten zum anderen zu springen. Zeiger  Außerdem wird der erste Knoten der Liste normalerweise als   der Liste bezeichnet. Dies ist auch der Knoten, den wir aufgrund des Problems zurückgeben müssen. Kopf  Hier ist ein grafisches Beispiel:   Der erste Knoten auf der linken Seite ist der Kopf der Liste, der seinen Wert v₀ und einen Speicherzeiger   enthält, der die Liste zum nächsten Knoten   Der folgende Knoten   enthält seinen Wert und einen Zeiger   auf den nächsten Knoten und so weiter. P(n₁) n₁ umleitet. n₁ P(n₂)  Der letzte Knoten hat natürlich nichts, worauf er zeigen kann, daher ist der Wert seines Zeigers   . null  Sehen wir uns den Code an, um einen zu erstellen!   https://gist.github.com/NicolaM94/03bd49c6f65054a3440e8c9eef3c560c?embedable=true  Der Code ist ziemlich einfach: Wir erstellen zwei Strukturen, eine für den inneren Knoten und eine für die verknüpfte Liste.  Wie wir gerade gesehen haben, verfügt der Knoten über zwei Eigenschaften, nämlich die Eigenschaft   und die Eigenschaft   , die einen   Typ als Zeiger auf den nächsten Knoten enthält. Value Next *Node  Die verknüpfte Liste, eine Struktur zum „Initialisieren“ der verknüpften Liste, die nur eine Eigenschaft hat, den   der Liste. Head  Danach initialisieren wir einfach die Liste in der Hauptfunktion und geben ihrem Kopf einen Knoten mit einem Zufallswert von 10.  Der Schlüssel zum Verständnis der verknüpften Liste besteht darin, dass         ist, von Natur aus über eine       , die den nächsten Knoten enthält. Dieser letzte Knoten verfügt dann über seine   Eigenschaft, um zum nächsten Knoten zu springen, und so weiter. der Head Knoten nun, da er vom Typ Node Next Eigenschaft verfügt Next  Alles wird klarer, wenn wir der Liste einige Knoten hinzufügen, also machen wir es! Wir haben zwei Möglichkeiten: Entweder wir machen es manuell, was eine   mühsame Aufgabe ist, oder wir schreiben eine Methode für die verknüpfte Listenklasse, um einige weitere Knoten hinzuzufügen. Schauen wir es uns an! wirklich  Knoten hinzufügen: Veränderbare Liste in Verkleidung  Selbst wenn Sie über wenig Programmiererfahrung verfügen, ist in fast jeder Programmiersprache eines der ersten Konzepte, von denen Sie gehört haben sollten, der Unterschied zwischen   und   Listen. veränderlichen unveränderlichen  Wie der Name schon sagt,   . Unveränderliche Elemente haben stattdessen eine   . Aber warum ist das so? handelt es sich bei veränderlichen Listen um Listen, die Sie bearbeiten und zu denen Sie Elemente hinzufügen können feste Größe und können nicht mit neuen Elementen angehängt werden  Unveränderliche Listen sind   , was bedeutet, dass ihre Elemente   werden: Wenn bei einer Liste mit 3 Elementen das erste Element bei 0x00 gespeichert wird, befindet sich das zweite bei 0x01 und das letzte bei 0x02. im Speicher zusammenhängend nacheinander im Speicher gespeichert  Aus diesem Grund ist es in Python so schnell, über ein festes Array, eine unveränderliche Liste oder ein Tupel zu iterieren, da die CPU die Speicherindizes einfach einzeln abruft.  Andererseits sind veränderliche Listen im Speicher nur dann zusammenhängend, wenn sie zum ersten Mal initialisiert werden: Wenn zu diesem Zeitpunkt Elemente hinzugefügt werden, sind sie nicht mehr sequentiell. Wie können wir sie also überbrücken?    , was uns das angehängte to-Element bringt, und so weiter.  Nun, weil das letzte Element der ersten Initiierung einen Zeiger haben wird, den das Element danach hinzugefügt hat Also ja, veränderbare Listen sind oft getarnte verknüpfte Listen!  Sehen wir uns nun den Code an:   https://gist.github.com/NicolaM94/9f587f4cd675dbbdb098327b22628284?embedable=true  Wir haben die Methode   zu den Methoden unserer verknüpften Liste hinzugefügt. Der Vorgang zum Hinzufügen eines Knotens läuft folgendermaßen ab: AddNode  Zuerst speichern wir den   Wert in einer Variablen namens  Head current  Als nächstes durchlaufen wir die verknüpfte Liste und aktualisieren jedes Mal die   Variable mit dem nächsten Knoten, bis der nächste Knoten null ist.  current Sobald der Knoten, auf dem wir uns gerade befinden, einen Nullzeiger hat, wissen wir, dass wir uns auf dem letzten Knoten der Liste befinden.  Zuletzt aktualisieren wir diesen letzten Knoten mit einem neuen Knoten und einem neuen Wert (der   Zeiger dieses neuen Knotens wird auf Null gesetzt, wenn wir ihn leer lassen). Next  Grafisch sieht dieser Vorgang etwa so aus:   Wir können die korrekte Funktionsweise dieser Methode in der Hauptfunktion überprüfen, indem wir die Werte der Knoten in der verknüpften Liste ausdrucken.  Entfernen des Knotens  Nun zum letzten Teil und zur Lösung unseres Problems: Entfernen eines Knotens mit dem richtigen Index. Was bedeutet es zunächst, einen Knoten aus einer verknüpften Liste zu entfernen? Wenn wir darüber nachdenken,   , oder? existiert ein Knoten in einer verknüpften Liste nur, wenn er mit dem vorherigen verbunden ist  Wenn wir beispielsweise n-1ᵗʰ einen   Wert von null geben, können wir den nᵗʰ-Wert von der Liste trennen.  Next  Was ist, wenn das Element, das wir entfernen möchten, nicht das letzte ist? Nun, wir können   !  die Verknüpfung des Elements aufheben, indem wir das vorherige mit dem nächsten verbinden  Um das kᵗʰ-Element zu entfernen, müssen wir das k-1ᵗʰ-Element finden und es mit dem k+1ᵗʰ-Knoten verknüpfen. Wir müssen den   speichern. vorherigen Knoten (k-1ᵗʰ)  Offensichtlich   : Wenn Sie etwas wie   versuchen, wird nur ein Fehler angezeigt. Vor diesem Hintergrund können wir jedoch den Kopf der Liste als Index 0 betrachten und ihren nächsten Knoten als Index 1 usw., und wir können auch die Knoten durchlaufen, wie wir es zuvor getan haben. können wir die Liste nicht direkt indizieren linkedlist[n]  Was wir dann tun können, ist, einen   zu implementieren, um den Knoten zu verfolgen, auf dem wir uns befinden! Zähler  Dann kodieren wir es.   https://gist.github.com/NicolaM94/e08509c42ede81834ac65ff7aa65828b?embedable=true  Schauen wir uns die   Funktion an, die ein   akzeptiert. Danach initialisieren wir drei Variablen: RemoveNode index    , der den vorherigen Knoten enthält previousNode    , der den Knoten enthält, auf dem wir uns während der Schleife befinden current    , zunächst gleich 0, was unsere Position auf der Liste hält counter  Überspringen wir zunächst den ersten if-Block und konzentrieren uns stattdessen auf die for-Schleife. Wir beginnen mit der Schleife, bis unsere   deutlich kleiner als unser   ist: Jede Schleife  counter index aktualisiert dann den vorherigen Knoten mit dem aktuellen und fährt mit der Aktualisierung des aktuellen Knotens und des Zählers fort.    bedeutet das, dass           sein  Wenn die Schleife unterbrochen wird, wir uns gerade auf dem Knoten vor unserem gewünschten Index befinden: Wir müssen nur den Zeiger des vorherigen Knotens, prev.Next , mit dem nächsten Knoten in der Liste aktualisieren, von dem aus wir uns befinden wird current.Next . Schließlich geben wir den Kopf der verknüpften Liste zurück.  Was passiert nun, wenn der zu entfernende Index der Kopf ist, der einen Index von 0 hat? Die Schleife würde niemals starten, da sie mit   und   beginnt und die Bedingung sofort falsch wäre. Wir können diesen ersten Fall mit dem if-Block oben verwalten. counter = 0 index = 0  Wenn der Index 0 ist, können wir grundsätzlich den Kopf der verknüpften Liste direkt mit dem Knoten daneben aktualisieren und ihn zurückgeben. Ich möchte Ihre Aufmerksamkeit insbesondere auf Zeile 31 lenken: Go übergibt, wie in vielen anderen Sprachen,   , was bedeutet, dass die Funktion eine   des übergebenen Objekts behält,   . die Attribute an die Funktionen nach Wert Kopie nicht das tatsächliche Objekt, das Sie übergeben  Dieses Konzept wird in diesem Beispiel deutlich:   package main import "fmt" func printMemoryAddress(value int) { fmt.Println(&value) } func main() { a := 10 fmt.Println(&a) printMemoryAddress(a) } // 0xc00010a000 // 0xc00010a008 // Program exited.  Wir erstellen eine Funktion zum Drucken der Speicheradresse des als Attribut übergebenen Werts. Dann erstellen wir in der Hauptfunktion eine Variable a und geben ihre Speicheradresse aus. Dann übergeben wir dieselbe Variable an die Funktion und geben ihre Speicheradresse aus.  Wie Sie sehen, werden die Ergebnisse unterschiedlich ausfallen, wenn Sie es versuchen: Das liegt daran, dass Attribute als Wert an die Funktionen übergeben werden, was bedeutet, dass eine Kopie von   erstellt wird, nur um sie an die Funktion zu übergeben. a  Zurück zu unserer verlinkten Liste: Wir müssen Zeiger verwenden, um den wahren Kopf für das gleiche oben stehende Problem zu ermitteln.     zu gelangen     merken     weiter verschieben  Um zum „echten“ ll.Node , müssen wir uns dessen Zeiger *ll.Node und ihn mit *ll.Node = *ll.Node.Next .  In der Hauptfunktion fügen wir die Aufrufe zur Methode hinzu, z. B. den Aufruf von   und   , und können das Ergebnis überprüfen, wenn Knoten 0 und Knoten 2 fehlen. ll.RemoveNode(0) ll.RemoveNode(2)  Abschluss  Wir haben es bis zum Ende geschafft!  Wenn Sie bis hierher gelesen haben, gilt Ihnen mein ganzer Dank. Wenn Sie bereit sind, ein oder zwei Likes zu hinterlassen und den Artikel zu teilen, wird es mir den Tag versüßen und mir helfen, diese Artikel weiter zu schreiben!  Wir sehen uns im nächsten Artikel und wie immer vielen Dank fürs Lesen.   Nicola

Read My Stories

Dieses Audio ist in der Originalsprache der Geschichte produziert!

Tägliches Codierungsproblem: Entfernen Sie den k-ten Index in einem Durchgang aus der verknüpften Liste

About Author

KOMMENTARE

Hängeetiketten

DIESER ARTIKEL WURDE VORGESTELLT IN

Related Stories

Starting 2025 with New Features: Settings Dashboard, HackerNoon Decoded, Updated Search UI, and More

HackerNoon Decoded 2024: Celebrating Our AI Community!

HackerNoon Decoded 2024: Celebrating Our Cybersecurity Community!

HackerNoon Decoded 2024: Wir feiern unsere Produktmanagement-Community!

Starting 2025 with New Features: Settings Dashboard, HackerNoon Decoded, Updated Search UI, and More

HackerNoon Decoded 2024: Celebrating Our AI Community!

HackerNoon Decoded 2024: Celebrating Our Cybersecurity Community!

HackerNoon Decoded 2024: Wir feiern unsere Produktmanagement-Community!

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps