einfach verkettete liste - in der mitte einfügen/rauslöschen

kann man in einer einfach verketteteten liste auch in der mitte was einfügen oder rauslöschen?

SideWinder

Klar dafür sind sie ja im Gegensatz zu Arrays optimal. Da wir hier im RundUm-Forum sind mal eine allgemeine Lösung:

Der '|' ist ein Pfeil nach unten *g*

Ausgangssituation:

Start
 |
E1 -> E2 -> E3 -> E4 -> NULL

Einfügen zwischen E2 und E3 (neue Position 3), suchen der Position:

Runner = Start (danach Runner 2 (auf Pos1 ist er ja schon) mal weiter setzen Runner=Runner.next)

Situation nun:

Start     Runner
 |          |
E1 -> E2 -> E3 -> E4 -> NULL

Neues Element kreieren und E2 darauf zeigen lassen:

Start     Runner
 |          |
E1 -> E2    E3 -> E4 -> NULL
      |
      ENeu

Danach ENeu auf Runner(=E3) zeigen lassen und fertig.

rauslöschen ist ähnlich, bloß einfach E2 next nicht auf ein neues zeigen lassen sondern auf Runner.next und danach Runner löschen.

MfG SideWinder

THE_FreaK

Hoi!

Hab mich jetzt auch mal mit dem Thema beschäftigt.
Beim rauslöschen allerdings hab ich probleme:
Das element wird zwar aus der liste gelöscht, aber das objekt wird nicht zerstört. Wie kriege ich den speicher denn nun freigegeben, besser wo??

Hat nochmal jemand dafür ne genauere beschreibung parat?

SideWinder

Ich hasse einfach verkettete Listen, mir ist gerade aufgefallen, dass oben ein zweiter Zeiger fehlt der sich E2 merkt.

Genau das gleiche beim Löschen. Ein Zeiger bleibt an der Position VOR (p_vor) dem zu Löschenden Objekt, der zweite ist eins weiter (p_obj). Danach wird p_vor.next auf p_obj.next gesetzt. Damit ist p_obj aus der Liste ausgekettet und kann ohne Probleme mittels delete p_obj gelöscht werden.

MfG SideWinder

THE_FreaK

das ausklinken ist nicht das problem. Aber wenn ich p_obj zerstören will muss ich die Adresse kennen, da aber p_vor.next schon geändert wurde ist die Adresse von p_obj verloren. Und vor dem ausklinken kann ich es nicht löschen.

mach es jetzt so:

Node * InternalNode::Delete(Data * theData)
{
	if (myData->Compare(theData))
	{
		Node * oldNext = myNext;
		myNext = myNext->Delete(theData);
		delete oldNext;
		return myNext;
	}
	else
	{
		myNext = myNext->Delete(theData);
		return this;
	}
}

Gibts da nicht ne bessere möglichkeit?

[EDIT]
Mal abgesehen davon das es nen speicherfehler verursacht, aber das währ mein ansatz. ich weis nicht wo ich das löschen des objektes durchführen soll

SideWinder

Warum Runner zeigt ja noch immer darauf?

// front ist die Wurzel der Liste, id gibt die Position an (beginnend bei 1)
void list_delete(node* front,unsigned long int id)
{
    // Edit:
    if(!id)
        return;

    node* runner = front;

    // runner auf das Objekt vor das zu löschende Objekt setzen
    --id;
    while(--id)
    {
        runner = runner.next;
    }

   // help auf das zu löschende Objekt setzen damit die Adresse nicht verloren geht
    node* help = runner.next;

    // Element ausklinken:
    runner.next = help.next;

    // Ausgeklinktes Element löschen:
    delete help.next;
}

So könnte das ungefair aussehen.

Bei doppelt verketteten Listen ist das natürlich viel elegenater zu lösen:

void list_delete(node* front,unsigned long int id)
{
    // Edit:
    if(!id)
        return;

    node* runner = front;

    // runner auf das Objekt vor das zu löschende Objekt setzen
    --id;
    while(--id)
    {
        runner = runner.next;
    }

    // Element ausklinken:
    runner.last.next = runner.next;
    runner.next.last = runner.last;

    // Ausgeklinktes Element löschen:
    delete runner;
}

MfG SideWinder

SideWinder

Da gehören natürlich noch ein paar Sicherheitsabfragen rein:

- Wurzel auch wirklich okay?
- Genügend Elemente vorhanden?

etc.

MfG SideWinder

THE_FreaK

das hab ich soweit ich das sehe ja ähnlich gemacht.
oldNext nimmt immer die adresse des nächsten knotens auf.
wenn die lösxchbedingung zutrifft wird oldNext angelegt und ihm der inhalt von myNext zugewiesen. nach der änderung von myNext wird dann auf oldNext ein delete ausgeführt.
Allerdings bringt mir das immer nen speicherfehler

über google gibt es soviele informationen über verkettete listen. such dir da einfach eine implementation in c oder c++ raus und du weißt wie es richtig geht.

PAD

Ist das wirklich so schwierig

Verkette Liste: a b c d e
Um element c zu löschen
old_Data= Zeiger b->next
b->next= c->next
c->next=0;
Jetzt habe ich in old_data die Inhalte von C und kann diese genüßlich vernichten.
Interessant ist nur nich der Headnode, da es auf den keine Zeiger gibt aber wir wollten eh nur in der Mitte
löschen

THE_FreaK

so hab ichs auch getan, allerdings hab ich mir halt nen speicherfehler gebaut.
Punkt