Symbol Tables can be implemented in many ways and here are some of them.
Unordered Array Implementation
With this method, just maintaining an array is enough. It needs O(n) time for searching, insertion and deletion in the worst case.
Ordered [Sorted] Array Implementation
In this we maintain a sorted array of keys and values.
- Store in sorted order by key
- keys[i] = ith largest key
- values[i] = value associated with ith largest key
Since the elements are sorted and stored in arrays, we can use simple binary search for finding an element. It takes O(log n) time fir searching and O(n) time for insertion and deletion in the worst case.
Unordered Linked List Implementation
Just maintaining a linked list with two data values is enough for this method. It needs O(n) time for searching, insertion and deletion in the worst case.
Ordered Linked List Implementation
In this method, while inserting the keys, maintain the order of keys in the linked list. Even if the list is sorted, in the worst case it needs O(n) time for searching, insertion and deletion.
Some of the other methods are:-
- Binary Search Trees Implementations
- Balanced Binary Search Trees Implementations
- Ternary Search Implementation
- Hashing Implementation
COMPARISON OF SYMBOL TABLE IMPLEMENTATIONS
The following comparison table gives a outlook:-
| Implementation | Search | Insert | Delete |
| Unordered array | n | n | n |
| Ordered Array | log n | n | n |
| Unordered List | n | n | n |
| Ordered List | n | n | n |
| Binary Search Trees (O(log n) on average) | log n | log n | log n |
| Balanced Binary Search Tree | log n | log n | log n |
| Ternary Search | log n | log n | log n |
| Hashing (O(1) on average | 1 | 1 | 1 |
