Doppelt verkettete Liste?

Hi,

ich verstehe nicht, warum das Entfernen eines Elements in einer doppelt verketteten Liste in der Laufzeit O(1) geschehen kann und nicht, wie bei einer einfach verketteten Liste nur in O(n).

Wenn ich bei einer doppelt verketteten Liste das letzte Element entfernen möchte, müsste ich doch auch über alle Vorgänger iterieren. Genau so wie bei einer einfach verketteten Liste, oder nicht?

1 Antwort

Vom Fragesteller als hilfreich ausgezeichnet

iQa1x

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Computer

11.11.2019, 21:01

Hi,

wenn du den Anfang a und das Element x zum Entfernen hast, musst du bei einer einfach verketteten Liste

i = anf; 
while(i.next!=x) i=i.next; //O(n)
i.next = i.next.next;

machen, um das Element zu entfernen. Hast du eine doppelt verkettete Liste, musst du nur

x.prev.next = x.next;
x.next.prev = x.prev;

machen, um das Element zu entfernen, und daher nicht die ganze Liste durchgehen.

Woher ich das weiß:Berufserfahrung – Softwareentwickler & Admin

Aufgabenstellung: "Sie haben eine doppelt verkettete liste, fügen Sie bei der Unterklasse Stapel eine Methode ein, die dafür sorgt, dass das erste Listenelement Ihrer Liste gelöscht wird! Zuvor überprüfen Sie, ob der Stapel (Stack) leer ist, ist der Stapel (Stack) leer, so geben Sie eine Nullreferenz zurück, andernfalls löschen Sie das erste Listenelement Ihrer liste und geben Sie gefolgt das Datenelement des ersten Elements als Ergebnis aus!"

Was ist damit gemeint, dass ich schauen soll ob der Stapel leer ist?

(Ist eine selbst erzeugte doppelt verkettete Liste)

...zur Frage

Doppelt verkettete Liste, Java?

Wir haben in Informatik einfach und doppelt verkettete Listen gemacht. In den Folien gibt es auch ein Implementierungsbeispiel einer einfach verketteten Liste. Ich soll jetzt die gleichen bzw. ähnlichen Methoden für eine doppelt verkettete Liste programmieren.

Mein Problem ist, dass ich nicht verstehe, wie ich das machen soll. Ich habe mir verschiedene Beispiele angeguckt und versucht mich schlau zu lesen, aber die Beispiele schienen mir (jedenfalls bei der Implementierung) furchtbar umständlich.

Überall steht, dass sowohl auf den Nachfolger als auch auf den Vorgänger gezeigt wird. Ok, klingt logisch bei doppelt verkettet.

Aber wie sieht bei der Implementierung aus ?

Ich muss ein Element einfügen, entfernen und suchen.

...zur Frage

Beliebiges Element in einer Liste löschen (Java)?

Die Aufgabe lautet, dass wir ein beliebiges Element in einer Liste löschen können. Ich habe auch schon einen Ansatz. Doch ich komme jetzt leider nicht mehr weiter. Ich kann bisher nur das erste und letzte Element löschen. Doch noch keines in der Liste. Also das Dummy läuft durch die Queue bis zum vorletzten Element. Wenn nun der gesuchte Content mit dummy.getNext() übereinstimmt, dann soll gelöscht werden. Ich habe es auch schon so versucht zu programmieren aber irgendwie krieg ich es nicht ganz so hin, wie ich es mir vorgestellt habe.

Ist etwas in meiner Logik falsch oder etwas wie ich es programmiert habe? Kann mir wer helfen das weiter so zu programmieren? Danke

public void delete(String s) {
        Node dummy = first;
        Node last = getLast();
        Node nach = getNext();
        if(s.equals(first.getContent())) {
        delete();
        }
        else if(getLast().getContent().equals(s)) {
          delete();
        }
        
        while(!(dummy.getNext().getContent().equals(s))) {
            delete();
            dummy=dummy.getNext();
        }
        dummy.setNext(dummy.getNext().getNext());
    }

...zur Frage

Pointer in C?

Hallo zusammen.

Ich habe eine sehr konkrete Frage, weshalb nicht viel Code gebraucht wird. Ich bewege mich im Raum der Sprache C.

Ich habe eine mehrfach verkettete Liste mit Elementen, die jeweils einen Pointer auf ihren Vorgänger und Nachfolger haben. Das Erste hat dann folglich die 0 als Vorgänger und das letzte Element die 0 als Nachfolger.

Sei *ptr ein Pointer auf irgend ein beliebiges Element, sagen wir einfach: ptr zeigt auf das 2. Element in der Verkettung.

Wenn ich nun durch Umlenken der Vor-und Nach-Pointer der Elemente das 2. und das 3. Element tausche (das Tauschen funktioniert einwandfrei) dann zeigt ptr auf das 3. Element. Die Frage ist warum?

Meine Überlegung:

ptr zeigt auf die Adresse (z.b. 0x2 für 2.Element) und greift durch den komponentenzugriffsoperator -> auf die einzelnen vor-und nach-pointer zu. ptr greift durch die Adresse zum Element, das heißt, man tauscht nicht die Elemente in den Speicherzellen. Man koordiniert lediglich die Pointer so um, dass das vorher 2.Element an 0x2 nun das 3. wird.

Ich merke, dass ich durch das Selbsterklären gerade zur Lösung gekommen bin, logisch. Heißt das im Umkehrschluss: Egal wie viele Pointer ich auf Stelle 0x2 zeigen lasse, werden ausnahmslos alle "hochgezählt" in der Kette.

Kann mir dennoch ein C-Veteran diesen Gedankengang validieren?

Danke im Voraus.

...zur Frage

Wie wird eine Remove-Methode in c# bei einer EINFACH verketteten Liste implementiert?

Folgende Aufgabe:

Ich habe eine List aus.. ähm.. sagen wir mal DVDs.. Die Listenelemente.. also die einzelnen DVDs haben einen Namen.. sind also so implementiert:

class LElem DVD { LElem next; string titel; }

so . jetz durchsuche ich meine Liste nach einem Titel

public LElem Suche (string eingegebenerTitel) LElem lfd = anf;
while (lfd!= null) { if (lfd.titel == eingegebenerTitel) return lfd; lfd=lfd.next; } //Ende meiner while schleife

Müsste so passen oder ?

aber wie kann ich diese DVD jetzt aus meiner liste entfernen? ich müsste ja praktische das Element vor meiner gefundenen DVD auf das "lfd.next" (nächstes nach aktuellem Element) zeigen lassen. das einzige, was mir einfällt, ist ein Zwischenspeicher, in dem ich immer das vorherige speichere.. kommt mir aber umständlich vor.. kann mir da wer helfen?

ich hoffe, meine halbvollständigen codezeilen sind lesbar :D

...zur Frage

Wie lösche ich doppelt verkettete Liste in C++ rekursiv?

Hey. Ich möchte ein Funktion void clear_rek() implementieren, aber leider funktioniert es noch nicht. Beim dem rekursiven Aufruf clear_rek(head->next) kommt eine Fehlermeldung. Eigentlich müsste das doch gehen, weil Head ein Attribut der Klasse ist oder? Kann mir vielleicht jemand sagen, wie ich das umsetze?

...zur Frage

Soll eine verkettete Liste durchgehen und alle die mit einem bestimmten Buchstaben anfangen in eine Liste packen, in was für ene Liste kann ich die tun(java)?

Hi, ich habe eine verkettete Liste, diese gehe ich durch und überprüfe den ersten Buchstaben eines Strings. Das bekomme ich auch hin, danach muss ich jedoch jedes Element, dass mit dem Buchstaben beginnt in eine Liste packen, das geht nicht mit einem Array oder? Weil ich weiß vorher nicht, wie viel Namen mit dem Buchstaben anfangen und kann die Länge nicht ausmachen.

Wie würde ich das mit einer verketteten Liste machen? Wie würde das aussehen?

...zur Frage

Wie bei Python mit "If" überprüfen ob Variable mit bestimmten Wert in Liste enthalten ist?

Ich muss für die Schule ein Spiel in Python programmieren. Problem dabei: Uns wurde noch nicht wirklich viel beigebracht und daher verstehe ich nicht, wie ich gewisse Sachen programmieren soll.

Folgendes Szenario bereitet mir nun Schwierigkeiten:

Das Programmierte ist kein Ausschnitt aus meinem Spiel, sondern einfach das gleiche Schema, wie die eine Stelle in meinem Spiel (sonst wäre es zu kompliziert zum verstehen). x hat z.B nicht immer den Wert 5, dieser ändert sich im Verlaufe des Programms.

Ich möchte überprüfen, ob eine der Variable in der Liste einen Wert zwischen 0 und 10 hat. Ist es möglich, dies mit einem "if" Befehl zu lösen? Was müsste bei "Bedingung_erfüllendes_Element" stattdessen stehen? Ich kann da ja nicht ">=0 and <=10" hinschreiben. Das einzige, was ich überprüfen kann, ist ob eine bestimmte Variable in der Liste ist. (z.B if x in liste), aber das möchte ich ja nicht, ich möchte auf den WERT der vorhandenen Variablen überprüfen.

Ich habe es auch schon mit einer For-Schleife probiert, aber da ist da Problem, dass wenn zwei Elemente, welche die Bedingung erfüllen, vorkommen, dass die folgenden Befehle doppelt ausgeführt werden. Es soll aber, für jedes Element, welches die Bedingung erfüllt, ein anderer Text geprintet werden.

Ich brauche wirklich nur diesen einen, eigentlich simplen Befehl, der überprüft, ob es in der Liste mindestens ein Element hat, welches einen bestimmten Wert hat.

...zur Frage

Java verkettet Listen?

Ich habe eine Frage zu verketteten Listen in jave.

Ich habe eine Klasse Node erstellt, die bestimmte Informationen erhält und das Objekt: Mode nextElem;

Nun habe ich noch eine andere Klasse namens Liste erstellt und dort folgende Methode implementiert

Mit der Methode getLastElem bekomme ich immer das aktuell letzte Element der Liste. Da dieses lastElement noch kein next Element besitzt, setze ich mit der Methode setNextElem ein weiteres Element in die Liste.

Meine Frage nun:

Es fängt an mit dem Objekt firstElem in der Liste. Dieses Objekt besitzt, weil es vom Typ Node ist, ein Objekt nextElem, welches aber noch nicht belegt wurde(siehe erstes Bild). Wenn ich jetzt aber mit der setNextElem Methode dieses Objekt mit einem Wert belege, exestiert dieses. Das heißt ja, dass mein 2.Objekt in der Liste die Referenzvariable nextElem hat.

Jetzt kommt mein Problem:

Müsste nextElem nicht überschrieben werden, wenn ich das noch mal die Methode addElem benutze. Denn das 2.Objekt in der Liste heißt ja auch nextElem. Da nextElem vom Typ Node ist, besitzt es auch das Objekt nextElem. Wenn das unbelegte Objekt nextElem von nextElem belegt wird, müsste doch rein theoretisch das erste nextElem überschrieben werden. Damit würde die Datenstruktur Liste nicht mehr funktionieren. Dies ist aber in Wirklichkeit nicht so.Warum?

Derjenige der mir hier drauf antwortet, ist der größte Ehrenmann/Frau

...zur Frage

Python 3 Verkettete Listen mit Queue und Stack?

Hallo,

ich benötige Hilfe bei folgender Aufgabe:

Implementiere einen Stack unter Verwendung einer einfach verketteten Liste durch folgende Funktionen: StackInit, IsEmpty, IsFull, Push, Pop, Top, und PopTop. und Implementiere eine Queue unter Verwendung einer einfach verketteten Liste durch folgende Funktionen: QueueInit, IsEmpty, IsFull, Put, Get, und Front.

Wie kann ich hier vorgehen? Danke

...zur Frage

Wie lösche ich ein Element in einer einer einfach verketteten Liste?

...zur Frage

C++ / CPP ->Einfach verkettete Liste aufbauen und bearbeiten, wie?

Ich muss verstehen, wie ich einfach verkettete Listen und später noch doppelt verkettete Listen aufbaue, um später Stacks und Queues zu realisieren.

Diese Klasse erzeugt mir ja ein einzelnes Objekt. Ich möchte nun mit der Methode "append" nach und nach eine Liste aufbauen, um dann mit weiteren Methoden mit dieser Liste arbeiten zu können.

Die Methoden, mit denen ich die Liste aufbauen, modifizieren, etc. kann müssen also noch Teil einer neuen weiteren Klasse sein?

Heißt das ich muss über eine Klasse und dessen Methoden auf die Klasse ListElement zugreifen, um dann eine Liste aufzubauen?

Ich bin mit den verschiedenen Klassen und Pointer echt verwirrt, kann mir da jemand helfen? Wie genau muss ich das aufbauen? Sollten die Klassen in einer eigenen Header-Datei liegen oder kann ich auch alles in einer .cpp Datei aufbauen?

...zur Frage

Gibts in Python dafür n schöne Funktion?

wenn ich eine liste von strings habe und es dopplete oder dreifache einträge gibt, kann ich da irgendwie die elemente rauslöschen die doppelt sind sodass nur jeweils ein element übrig bleibt ohne eine extra funktion dafür zu schreiben?

...zur Frage

Quicksort mit median pivotisierung?

Hey, ich habe den Quicksort Algorithmus folgendermaßen beschrieben bekommen:

Nun habe ich eine Methode lowerMedian(), die den Median einer Liste bestimmt. Wie genau muss ich diese Methode nun im Quicksort algorithmus einsetzen, damit dieser als Pivot Element immer den Median nimmt, die Laufzeit also O(log(n)) ist?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen