praktische datenstrukturen

Question 1

Collection:

Answer 1

• Eine Collection verwaltet Objekte (Elemente).
• Interface enthält generelle Methoden (fur alle Collection-Typen).
• Es gibt keine direkte Implementierung dieses Interfaces.

Question 2

Set:

Answer 2

• Eine Collection, die keine duplizierten Elemente enthält.

Question 3

List:

Answer 3

• Eine geordnete Collection (mit duplizierte Elementen).

* Elemente können über einen Index angesprochen werden (nicht immer effizient)

Question 4

Queue/Deque:

Answer 4

• Verwalten von Warteschlangen.
• FIFO, Prioritätswarteschlangen.
• Einfugen und Löschen an beiden Enden bei Deque (“double ended queue”).

Question 5

ArrayList:

Answer 5

• Indexzugriff auf Elemente ist überall gleich schnell (O(1)).
• Einfugen und Löschen ist am Listenende schnell und wird mit wachsender Entfernung vom Listenende langsamer (O(n)).

Question 6

LinkedList:

Answer 6

*Indexzugriff auf Elemente ist an den Enden schnell und wird mit der Entfernung
von den Enden langsamer (O(n)).

*Einfugen und Löschen ohne Indexzugriff ist uberall gleich schnell ( O(1)).

Question 7

PriorityQueue:

Answer 7

• Einfugen eines Elements und Löschen des ersten Elements in einer Queue der Größe n sind in O(log n).
• Löschen eines beliebigen Elements aus einer Queue der Größe n ist in O(n).
• Lesen des ersten Elements in einer Queue ist in konstanter Zeit möglich (O(1)).
• Ist als Min-Heap implementiert

Question 8

TreeSet:

Answer 8

*null-Elemente sind nicht erlaubt.

*Die Laufzeit von Einfugen, Suchen und Löschen eines Elements liegt bei einem Baum mit n Elementen in
O(log n).

• Auf die Elemente eines TreeSets muss eine Ordnung definiert sein (mussen vergleichbar sein, d.h. das Interface Comparable implementieren).
• Implementiert als Rot-Schwarz-Baum.

Question 9

Rot-Schwarz-Baum:

Answer 9

• Variante eines balancierten Suchbaums.
• Kann als Spezialfall eines B-Baums der Ordnung 4 betrachtet werden.

*Einfugen und Löschen ist effizienter als in B-Bäumen solange die Datenmenge
nicht zu groß ist.

Question 10

HashSet:

Answer 10

• null-Elemente sind zulässig.
• Einfugen, Suchen und Löschen sind in konstanter Zeit möglich (abhängig von der Verteilung der Einträge in der Hashtabelle).

Aber: Rehashing kann zu Performance-Problemen fuhren (siehe auch API-Beschreibung).

Hashing mit Verkettung der Uberläufer. Falls die Liste zu lange wird, wird sie in
eine TreeMap umgewandelt.

Question 11

Map

Answer 11

• Maps sind eine Verallgemeinerung von Arrays mit einem beliebigen Indextyp
  (nicht nur int).
• Eine Map ist eine Menge von Schlüssel-Werte Paaren.
• Schlussel müssen innerhalb einer Map eindeutig sein.
• Werte müssen nicht eindeutig sein.

Question 12

Arten von Maps:

Answer 12

Wie bei Sets gibt es grundsätzlich zwei Versionen.

• HashMap: Implementierung wie HashSet.
• TreeMap: Implementierung wie TreeSet.

Question 13

Abstrakte Klassen

Answer 13

*Unterstutzen die Entwicklung neuer Klassen im Framework.
*Implementieren schon einen großen Teil eines Interfaces und lassen bestimmte
Teile noch offen.

Question 14

Sortieren von Collections:

Answer 14

• Zum sortieren von Collections wird TimSort verwendet.
• TimSort ist eine Kombination von Mergesort und Insertionsort.
• TimSort wurde 2002 von Tim Peters fur die Verwendung in Python entwickelt.

*Heute wird TimSort unter anderem in Python, Java, Android und Google Chrome
verwendet.