 |
© Harry Broeders.
Deze pagina is bestemd voor studenten van de THRijswijk groep IH3 SYSO. Op deze pagina vind je de sheets bij les 2 van SYSO1I0T1.
|
 |
| naam | insert | remove | find | applicatiesa | implementaties |
|---|---|---|---|---|---|
| stack | push O(1) |
pull O(1) LIFO |
top O(1) LIFO |
dingen omdraaien is ... gebalanceerd? evaluatie van expressies |
array, statisch + snel linked list, dynamisch + meer overhead in space en time |
| queue | enqueue O(1) |
dequeue O(1) FIFO |
front O(1) FIFO |
printer queue wachtrij |
array, statisch + snel linked list, dynamisch + meer overhead in space en time |
| vector | O(1) | O(n) schuiven |
O(n) op inhoud O(1) op index |
vaste lijst code conversie |
array, static random access via operator[] |
| sorted vector | O(n) zoeken + schuiven |
O(n) | O(log n) op inhoud O(1) op index |
lijst waarin je veel zoekt en weinig muteert | array, static + binary search algorithm |
| linked list | O(1) | O(n) | O(n) | dynamische lijst waarin je weinig zoekt en verwijdert | linked list, dynamic + more space overhead sequential access via iterator |
| sorted list | O(n) | O(n) | O(n) | dynamische lijst die je vaak gesorteerd afdrukt | - |
| tree | O(log n) | O(n) | O(n) | meerdimensionale lijst file systeem expressie boom |
more space overhead + minimal n+1 pointers with value 0 |
| search tree | O(log n) | O(log n) | O(log n) | dynamische lijst waarin je veel muteert en zoekt | sorted binary tree, more space overhead than list |
| hash table | O(1) | O(1) | O(1) | symbol table (compiler) dictionary |
semi-static, reduced performance if overfilled |
| priority queue | O(log n) | O(log n) | O(1) | event driven simulation | binary heap - array, static + little space overhead - binary tree, dynamic + space overh. |
 |
 |
 |
 Sheets
in pdf formaat
 (om af te drukken). |
 |