einfach verkettete Liste: Vorgänger löschen?

Hi Leute!

Wie kann man bei einer einfach verketteten Liste in C++ den Vorgänger löschen? Ich versteh das grad nicht ganz, da ich ja in einer einfach verketteten Liste ja immer nur in eine Richtung gehen kann. Aber doch nicht zurück. Könnt ihr mir helfen?

 

Da du nur in eine Richtung kommst, müsstest du also wenn du A,B,C durch hast und bei D bist logischer Weiße den Satz von vorne durchlaufen. Diesmal aber nur bis C anstatt bis D

Alterrnative nimm doppelt verkettete Listen die enthalten einen Zeiger auf den Vorgänger.

 

Für eine doppelt verkettete Liste hab ich das ganze schon gemacht. Ich soll's als Übungszwecken noch für einfach verkettete Listen machen. Ich hab hier mal einen Code, der das jetzt macht wie ich das will. Aufpassen muss man nur, wenn das vorhergehende Element aus der Liste ausgehängt wurde, kommt die selbe Ausgabefunktion zum Einsatz die mir die 4-Knoten-Liste ausgibt, was dann zur Folge hat, dass die entstandene 3-Knoten-Liste eben auch 4x ausgegeben wird. Kann man das jetzt verstehen?

Kannst du vielleicht mal drüber schaun ob das soweit passt? Mir ist natürlich klar, dass das alles jetzt nur für eine 4-Knoten-Liste funktioniert; aber bei einer einfach verkettete Liste eine allgemein deleteAfter-Funktion zu implementieren dürfte doch (wahrscheinlich) ziemlich schwierig werden, oder?

Code:

Code:

#include<iostream>
using namespace std;


struct node
{
	node *next;
	int value;
};



void showList(node *nextElement, node *liste)
{
	int i = 0;

	nextElement = liste;
	while(i != 4)
	{
		cout << nextElement->value << endl;
		nextElement = nextElement->next;

		i = i + 1;
	}
}



void deleteBefore(node *list)
{
	node *nodeToDel = list->next->next->next;
	list->next->next->next = list->next->next->next->next;
	delete nodeToDel;
	
}



int main()
{
	node *liste1, *liste2, *liste3, *liste4;
	node *nextElement = 0;

	liste1 = new node;
	liste2 = new node;
	liste3 = new node;
	liste4 = new node;

	liste1->next = liste2;
	liste1->value = 1;

	liste2->next = liste3;
	liste2->value = 2;

	liste3->next = liste4;
	liste3->value = 3;

	liste4->next = liste1;
	liste4->value = 4;

	showList(nextElement, liste1);
	deleteBefore(liste3);
	cout << endl;
	showList(nextElement, liste1);



return 0;
}

 

Dein Code sieht etwas seltsam aus und scheint mit der verketteten Liste gar nicht dynamisch umzugehen. Ich hätte eigentlich sowas in der Art erwartet:

Code:

struct list {
  list* next;
  int value;
}

int size(list* l) {
  // Anzahl der Elemente in der Liste zurückgeben (also, ab diesem
  //  "Knoten" zählen, bis ein "next"-Zeiger NULL ist
}

void addElement(int elementValue, list* insertHere) {
  list* newList = new list;

  list->value = elementValue;
  list->next   = NULL; // Auf NULL, weil kommt hinten dran

  // Und jetzt noch "newList" in "insertHere" einfügen, also bis zum
  //  Ende durch und an den letzten Knoten als next dranhängen
}

void removeFirst(list* theList) {
  ...
}

void removeLast(list* theList) {
  ...
}

void removeFirstWithElement(int element, list* theList) {
  ...
}

...

Du arbeitest da ja iwie nur mit einer 4-elementigen Liste. Verkettete Listen sind doch aber dynamische Strukturen, sind also dafür ausgelegt, gar keine feste Größe zu haben.

P.S. Is ja n Krampf, sowas in C zu schreiben...

Edit: Ob "node" oder "list" is eigentlich egal, geht nur ums Prinzip... Nich, dass das noch für Verwirrung sorgt