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

lg

Answer 1

[JavaTheHutt]

Deine "halbvollständigen Codezeilen" sind bescheiden lesbar und es bedarf einer Formatierung. Danach ist es ganz gut.

Du hast natürlich den wichtigsten Teil deines Codes weggelassen - die Klasse, die die Liste darstellt. Ich habe deswegen keine Ahnung und habe meine "eigene Version" davon programmiert. Es sollte allerdings mehr oder weniger ähnlich sein. Also erstmal das Gerüst:

public class MyList<T>
{
   private class Node<T>
   {
      public T Data { get; private set; }
      public Node<T> Next { get; set; }
      public Node(T element)
      {
         Data = element;
      }
   }
   public int Length { get; private set; }
   private Node<T> Head { get; set; }
}

Wir haben also eine Liste aus Knoten, die jeweils gewisse Daten beinhalten und einen Nachfolger haben. Eine Liste besteht im Moment aus einem Anfangselement und der Gesamtlänge.

Falls du jetzt ein Element aus dieser Liste entfernen willst, was musst du dafür tun? Du durchsuchst jedes Element der Liste und falls du das entsprechende gefunden hast, musst du den Nachfolger an der Vorläufer anhängen. Ein paar Spezialfällge müssen dabei berücksichtigt werden, z.B. wenn sofort das erste Element das gesuchte ist.

public void Remove(T element)
{
   Node<T> current, prev = null;
   current = Head;
   while (current != null)
   {
      if (current.Data.Equals(element))
      {
         if (current == Head)
            Head = current.Next;
         else
            prev.Next = current.Next;
         Length--;
         return;
      }
      else
      {
         prev = current;
         current = current.Next;
      }
   }
}

Der "Trick" ist, dass der Vorgänger immer mitgespeichert wird. So kannst du das vorherige Element mit dem Nachfolger des aktuellen verknüpfen und somit das aktuelle Element löschen. Für die Freigabe des Speichers ist dann der Garbage Collector verantwortlich.

Comments

[JavaTheHutt]

Noch eine Anmerkung: Als Rückgabewert bietet sich "void" nicht unbedingt an. Die Funktion sollte eher "bool" zurückgeben. Damit hälst du dich an die exisitierenden Methodensignaturen und kannst leichter das Interface "IList" implementieren.