Symbol Table Implementations

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] = i^th largest key
• values[i] = value associated with i^th 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:-