Home Theory Symbol Table Implementations

Symbol Table Implementations

by nikoo28
0 comment

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
0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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