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

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 Hier . Probieren Sie es aus und versuchen Sie auch, Ihre Herausforderungen zu lösen!

• 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 bei einer verknüpften Liste und einer Ganzzahl k den k-ten Knoten vom Ende der Liste und geben Sie den Kopf der Liste zurück.

k ist garantiert kleiner als die Länge der Liste.

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 k , das aus der Liste entfernt werden soll. Danach sollten wir den Kopf der verknüpften Liste zurückgeben.

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 k in der Liste enthalten ist, sodass wir nicht prüfen müssen, ob er über die tatsächliche Länge der Liste hinausgeht.

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 Knoten bezeichnet), und jeder Knoten muss mindestens zwei Eigenschaften haben: einen Wert (etwas, das tatsächlich im Knoten enthalten ist) und einen Link zum nächsten Knoten.

Normalerweise wird ein Zeiger als Link verwendet, um von einem Knoten zum anderen zu springen.

Außerdem wird der erste Knoten der Liste normalerweise als Kopf der Liste bezeichnet. Dies ist auch der Knoten, den wir aufgrund des Problems zurückgeben müssen.

Hier ist ein grafisches Beispiel:

Der erste Knoten auf der linken Seite ist der Kopf der Liste, der seinen Wert v₀ und einen Speicherzeiger P(n₁) enthält, der die Liste zum nächsten Knoten n₁ umleitet. Der folgende Knoten n₁ enthält seinen Wert und einen Zeiger P(n₂) auf den nächsten Knoten und so weiter.

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!

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 Value und die Eigenschaft Next , die einen *Node Typ als Zeiger auf den nächsten Knoten enthält.

• Die verknüpfte Liste, eine Struktur zum „Initialisieren“ der verknüpften Liste, die nur eine Eigenschaft hat, den Head der Liste.

  
  

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 der Head Knoten nun, da er vom Typ Node ist, von Natur aus über eine Next Eigenschaft verfügt , die den nächsten Knoten enthält. Dieser letzte Knoten verfügt dann über seine Next Eigenschaft, um zum nächsten Knoten zu springen, und so weiter.

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 wirklich 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!

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 veränderlichen und unveränderlichen Listen.

Wie der Name schon sagt, handelt es sich bei veränderlichen Listen um Listen, die Sie bearbeiten und zu denen Sie Elemente hinzufügen können . Unveränderliche Elemente haben stattdessen eine feste Größe und können nicht mit neuen Elementen angehängt werden . Aber warum ist das so?

Unveränderliche Listen sind im Speicher zusammenhängend , was bedeutet, dass ihre Elemente nacheinander im Speicher gespeichert 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.

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?

Nun, weil das letzte Element der ersten Initiierung einen Zeiger haben wird, den das Element danach hinzugefügt hat , was uns das angehängte to-Element bringt, und so weiter. Also ja, veränderbare Listen sind oft getarnte verknüpfte Listen!

Sehen wir uns nun den Code an:

Wir haben die Methode AddNode zu den Methoden unserer verknüpften Liste hinzugefügt. Der Vorgang zum Hinzufügen eines Knotens läuft folgendermaßen ab:

• Zuerst speichern wir den Head Wert in einer Variablen namens current

• Als nächstes durchlaufen wir die verknüpfte Liste und aktualisieren jedes Mal die current Variable mit dem nächsten Knoten, bis der nächste Knoten null ist. 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 Next Zeiger dieses neuen Knotens wird auf Null gesetzt, wenn wir ihn leer lassen).

  
  

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, existiert ein Knoten in einer verknüpften Liste nur, wenn er mit dem vorherigen verbunden ist , oder?

Wenn wir beispielsweise n-1ᵗʰ einen Next Wert von null geben, können wir den nᵗʰ-Wert von der Liste trennen.

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 vorherigen Knoten (k-1ᵗʰ) speichern.

Offensichtlich können wir die Liste nicht direkt indizieren : Wenn Sie etwas wie linkedlist[n] 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.

Was wir dann tun können, ist, einen Zähler zu implementieren, um den Knoten zu verfolgen, auf dem wir uns befinden!

Dann kodieren wir es.

Schauen wir uns die RemoveNode Funktion an, die ein index akzeptiert. Danach initialisieren wir drei Variablen:

• previousNode , der den vorherigen Knoten enthält

• current , der den Knoten enthält, auf dem wir uns während der Schleife befinden

• counter , zunächst gleich 0, was unsere Position auf der Liste hält

  
  

Überspringen wir zunächst den ersten if-Block und konzentrieren uns stattdessen auf die for-Schleife. Wir beginnen mit der Schleife, bis unsere counter deutlich kleiner als unser index ist: Jede Schleife aktualisiert dann den vorherigen Knoten mit dem aktuellen und fährt mit der Aktualisierung des aktuellen Knotens und des Zählers fort.

Wenn die Schleife unterbrochen wird, bedeutet das, dass 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 sein . 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 counter = 0 und index = 0 beginnt und die Bedingung sofort falsch wäre. Wir können diesen ersten Fall mit dem if-Block oben verwalten.

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, die Attribute an die Funktionen nach Wert , was bedeutet, dass die Funktion eine Kopie des übergebenen Objekts behält, 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 a erstellt wird, nur um sie an die Funktion zu übergeben.

Zurück zu unserer verlinkten Liste: Wir müssen Zeiger verwenden, um den wahren Kopf für das gleiche oben stehende Problem zu ermitteln. Um zum „echten“ ll.Node zu gelangen , müssen wir uns dessen Zeiger *ll.Node merken und ihn mit *ll.Node = *ll.Node.Next weiter verschieben .

In der Hauptfunktion fügen wir die Aufrufe zur Methode hinzu, z. B. den Aufruf von ll.RemoveNode(0) und ll.RemoveNode(2) , und können das Ergebnis überprüfen, wenn Knoten 0 und Knoten 2 fehlen.

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