Symbol Table Representations
Symbol tables can be represented in many ways:
key-indexed array (max # items, restricted key space)
key-sorted array (max # items, using binary search)
linked list (unlimited items, sorted list?)
binary search tree (unlimited items, traversal orders)
Costs (assuming N items):
| Type | Search costs |
| | min | max | avg |
| key-indexed | 1 | 1* | 1 |
| sorted array | 1 | log2N | log2N |
| linked list | 1 | N | N/2 |
| BSTree | 1 | N* | log2N |
|
![[prev]](icon/prev.gif){kind=icon}
![[index]](icon/up.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}