Container

Container verwalten eine Menge von Datenobjekten.

mögliche Operationen

(v = value)

c.size() ist immer unterstützt

   1 a) v = c.get(i) / b)v = c.get(pos)
   ites Objekt suchen

   2 v.set(i, value)
   ites Element überschreiben

   3 a) v = c.first/last

   4 v = c.largest/smallest

   5 v = c.get(key)
   Verallgemeinerung von 1 für beliebige Schlüssel (nicht nur integer)

   6 c.append(v)
   Objekt am Ende anhängen (mit c.set() verwandt)

   7 c.prepend(v)
   Objekt vorne einfügen

   8 c.insert(i, v)
   Objekt an beliebiger Position einfügen (Werte werden ab i verschoben)

   9 c.insert(key, v)

   10 c.removeFirst/Last()

   11 c.remove(i)

   12 c.remove(key)

   13 c.removeSmallest/Largest()

Facts

• Jede dieser Operationen kann sehr effizient implementiert werden.
• Keine Datenstruktur ist bekannt die alle diese Operationen effizient implementiert.

Beispiele

Je nachdem welche Operation effizient sein soll, wird eine andere Container Datenstruktur ausgewählt

• Array: unterstützt die ersten 3
• dynamischens Array: wie Array, zusätzlich c.append & c.removeLast
• Dictionnary: wie Array ausserdem c.geht(key), c.insert(key,value), c.remove(key)
• verkettete Liste:c.first(), c.insert(pos, value), c.remove(pos), c.get(pos)
• doppelt verkettete Liste:* wie Liste + ...
• Stack(Stapel): LIFO (Last In First Out) c.last(), c.append(), c.removeLast()
• Queue: FIFO (First In First Out) c.first(), c.append(), c.removeFirst()
• Deque: (Double Ended Queue) wie STACK + QUEUE
• MinPriorityQueue: c.smallest(), c.removeSmallest(), c.insert()
• MaxPriorityQueue: c.largest(), c.removeLargest(), c.insert()
• MinMaxPriorityQueue: MinPriorityQueue + MaxPriorityQueue