LinkedListe doppelte Einträge löschen

[Martin66119]

Hallo an alle die meine Frage lesen.

Ich habe da ein kleines Problem!

In einer LinkedList habe ich Daten abgespeichert.

Liste(0) = a
Liste(1)= b
Liste(2) = a
Liste(3) = a
Liste(4) = c
usw.

Ich möchte in der LinkedList alle mehrfachen Eintäge löschen. Wie mache ich das!

Danke schonmal.

[Froggerprogger]

Hi Martin,
Folgender Code liefert das gewünschte. Wenn er nicht schnell genug ist, könnte man da auch anders herangehen (mit ggf. mehr Overhead, aber insgesamt schneller)

Code: Alles auswählen

NewList A.l()
AddElement(A()) : A() = 2
AddElement(A()) : A() = 5
AddElement(A()) : A() = 1
AddElement(A()) : A() = 29
AddElement(A()) : A() = 2
AddElement(A()) : A() = 37
AddElement(A()) : A() = 2
AddElement(A()) : A() = 29
AddElement(A()) : A() = 2
AddElement(A()) : A() = 37

ForEach A()
  Debug A()
Next

count = 0
While count < CountList(A()) - 1
  SelectElement(A(), count)
  val.l = A()
  While NextElement(A())
    If A() = val
      DeleteElement(A())
    EndIf
  Wend
  count + 1
Wend

Debug "..........."
ForEach A()
  Debug A()
Next

[DrShrek]

An Moderator:
Bitte in Tipps und Tricks moven.

An alle,
Wer weiss einen besseren Algorithmus?

[NicTheQuick]

Wie wäre es mit einem einmaligen Sortieren der Liste und dann einem einmaligen Durchlaufen mit dem Löschen aller gleichen aufeinanderfolgenden Elemente?

Ich kann dazu allerdings gerade kein Beispiel machen, weil ich nicht zu hause bin. Ich habe zwar auf diesem Rechner in Informatik standardmäßig schon PureBasic installiert, aber ich muss ja wenigstens manchmal noch aufpassen.

Außerdem sind Frequenzanalysen verbunden mit Elektrotechnik interessant.

[DrShrek]

Wie wäre es mit einem einmaligen Sortieren der Liste und dann einem einmaligen Durchlaufen mit dem Löschen aller gleichen aufeinanderfolgenden Elemente?

Sortieren? Das würde aber die Reihenfolge verändern und das ist nicht die Aufgabenstellung

[Froggerprogger]

... falls aber die Reihenfolge verändert werden darf, wäre das sicherlich besser, da schneller.

Die jetzige Version vergleicht jedes Element mit allen folgenden. Dadurch werden schlimmstenfalls 1/2 * n^2 Vergleiche benötigt.
Laufzeit ist somit O(n^2).

Nics Variante würde fixer gehen, da vergleichsbasiertes Sortieren in n*log(n) geht, das anschließende rausschmeißen der doppelten Elemente geht durch einmaliges Durchlaufen der Liste, also in linearer Zeit. Laufzeit also n*log(n) + n, also O(n*log(n))

Schneller ginge es noch unter Zuhilfenahme eines Hashtables.
Da die Maximalanzahl der Elemente bekannt ist, lässt sich der Table optimal anpassen, somit erreicht man Insert/Search - Zeiten von O(1), also konstanter Zeit.
Man muss nur ein einziges Mal die Liste durchgehen, dabei jedesmal nachschauen, ob das Element bereits im Hashtable ist, wenn ja, dann aus der Liste rausschmeißen, wenn nein, dann in den Hashtable reinschreiben.
Gesamtlaufzeit n * 1 * 1, also O(n).
Schneller als O(n) geht nicht, da jedes Element zumindest einmal betrachtet werden muss. Letzte Variante wäre also eine optimale, die nur noch durch Senken der Konstanten noch besser werden könnte.

[NicTheQuick]

Wenn die Inhalte der LinkedList bspw. nur in dem Bereich 1 bis 1000 liegen würden, wäre die einfachste Hashtable ein Array mit dem Index 0 bis 999. Jetzt geht man die Liste durch, streicht jede vorkommende Zahl im Array ab und wenn sie schonmal vorgekommen ist, wird das aktuelle Elemente gelöscht.

[Froggerprogger]

Infomanie:
Nic beschreibt damit die 'direkte Adressierung'.
Hashen ist davon die Erweiterung auf beliebig große Datenbereiche.
Man hasht mit einer Hashfunktion (z.B. einfach Modulo) ein Element auf einen Speicherplatz, z.B. die Zahl x aus 0-2000000000 durch x % 1000 auf einen der Plätze 0...999
Problem: Mehrere Elemente können nun auf denselben Wert gehasht werden.
Für diese 'Kollisionen' gibt es verschiedene Strategien mit verschiedenen Eigenschaften.
Z.B. Anstelle eines Array-Feldes wird nun eine von 1000 Listen angesprochen, an die die Elemente einfach vorne angefügt werden.
D.h. wir suchen z.B. nach der Zahl 18442375, rechnen daher 18442375 % 1000 = 375, springen daher zur Liste 375 und suchen darin nach der Zahl 18442375.
Unter gewissen Annahmen (loadfactor) geht das sauschnell.
Alternative:
nun wieder mit einem echten Array ohne 1000 Listen. Wenn man feststellt, dass der Arrayplatz bereits durch einen anderen Wert belegt ist, liefert eine zweite Hashfunktion einen offset, den wir nun mit dem bisherigen verrechnen, und dort nachschauen (wiederum modulo 1000). Das machen wir solange, bis wir einen freien Platz finden. Nachteil: Höchstzahl von Elementen im Hashtable ist Arraygröße minus 1. Vorteil bei guten Hashfunktionen und ausreichender Arraygröße schneller als die andere Variante.