Home Theory Symbol Table Implementations

# 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] = 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.

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.

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

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More