Site icon Study Algorithms

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.

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:-

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
Exit mobile version