List<T> wie implementiert?

georgeboy · Beiträge: 214

Hallo zusammen, mich würde mal interessieren, wie bei C# .NET, List<T> realisiert wird. Man hat die Möglichkeit mit der Methode "Add" ein Element hinzuzufügen "Insert" "Remove"... Aber andererseits kann man List<T> wie ein Array verwenden:

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:

List<string> li = new List<string>();
li.Add("123");
li.Add("234");
li.Add("567");
string str = li[0];
li[1] = "MeinString";

Es handelt sich hier um eine Indexer Eigenschaft. List<T> ist eine aber eine dynamische Datenstruktur. Wenn ich "Add" sage, wird dann ein neues Array angelegt ? Womöglich eine grundlegende C# Frage. Die Frage läuft darauf hinaus wie man Indexer dynamisch effizient realisiert.

Th69 · Verfasst: Sa 26.12.20 18:22

Das kannst du direkt in den Reference Source .NET Framework: List<T> anschauen (oder auch mit Offline-Programmen wie Reflector oder ILSpy).

Ja, es wird intern ein Array neu erzeugt und umkopiert, sobald die Kapazität überschritten ist (dabei wird immer die Kapazität verdoppelt, s. private Hilfsmethode EnsureCapacity).

georgeboy · Beiträge: 214

Was ist, wenn ich auf den Indexer verzichten will, einen neuen Knoten nur vorne einfügen will, und die Liste durchlaufen können möchte, was extrem effizient ist, muss ich dann die Liste selber bauen ?

Palladin007 · Verfasst: So 27.12.20 09:36

Vorne hinzufügen ist bei der Liste immer langsam, da er immer (oder meistens) umkopieren muss.
Doch das dürfte für die meisten kaum relevant sein, da es immer noch sehr schnell ist.

Du könntest natürlich auch nur hinten anhängen und dann mit dem Indexer von hinten nach vorne durchlaufen, dann hast Du den Nachteil nicht.

Oder Du verwendest eine verkettete Liste, die KANN performanter sein, da Du hier gar nichts umkopierst, allerdings erstellst Du jedes Mal ein neues Objekt und musst ein bis zwei Referenzen umhängen.
Die verkettete Liste würde ich nur dann wählen, wenn realistische Messungen habe, die ganz eindeutig dafür sprechen, die zusätzliche Komplexität in Kauf zu nehmen.

Th69 · Verfasst: So 27.12.20 09:39

Dann wirst du eine eigene Wrapper-Klasse erstellen müssen, die nur diese spezielle Funktionalität anbietet.
Du kannst aber auch von List<T> ableiten und per Schlüsselwort new eine neue Implementierung erzeugen (und z.B. beim Setter des Indexers eine Exception werfen):

markieren

C#-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

class SpecialList<T> : List<T>
{
  public new T this[int n]
  {
    get { return base[n]; }
    set { throw new NotImplementedException(); }
  }

  // ...
}

Diese Klasse kann dann aber nur direkt benutzt werden, nicht per Polymorphie.

PS: Was mir gerade noch einfällt, für nur vorne einfügen, wäre auch eine Queue<T> geeignet (bzw. Stack, je nachdem wie die Objekte wieder daraus entfernt werden sollen).

Unter Generische limitierte Liste (im anderen C#-Forum) gibt es zurzeit eine ähnliche Anfrage.

Palladin007 · Verfasst: So 27.12.20 10:29

"new" bei einem Member ist meiner Ansicht nach in 99,999% der Fälle keine gute Idee und dann auch nur, wenn der neue Member sich exakt genauso verhält, wie die Basis.
Die Exception wäre außerdem eine Verletzung des Liskov substitution principle.
Einen Vorteil sehe ich eigentlich nur dann, wenn man z.B. für alle Nutzer der Ableitung zusätzlich casten möchte, da man dabei eigentlich nur die Basis aufruft.

Ich würde hier einfach die normale Liste umgekehrt benutzen, oder die Queue ist eine Option.

georgeboy · Beiträge: 214

Danke Euch !!!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme