Linked List & Tree Structure Organizations
- Linear list organization is the simplest and easiest way to implement the symbol tables.
- It can be constructed using a single array or equivalently several arrays that store names and their associated information.
- During insertion of a new name, we must scan the list to ensure whether it is a new entry or not.
- Moreover, If an entry is found during the scan, it may update the associated information but no new entries are made.
- If the symbol table has ‘n’ names, the insertion of new name will take effort proportional to ‘n’ and to insert ‘n’ names with ‘m’ information, the total effort is ‘n (n+m)’, where ‘c’ is a constant representing the time necessary for a few machine operations.
- The advantage of using list is that it takes minimum possible space. On the other hand, it may suffer from performance for larger values of ‘n’ and ‘m’.
- Searching in symbol table takes most of the time during symbol table management process.
- The pointer field called ‘LINK’ added to each record, and the search controlled by the order indicated by the ‘LINK’.
- A pointer called ‘FIRST’ can use to designate the position of the first record on the linked list. And each ‘LINK’ field indicates the next record on the list.
- A self-organizing list is advantageous over simple list implementation in the sense that frequently referenced name variables will likely to be at the top of the list.
- If the access is random, the self-organizing list will cost time and space.
- Symbol tables can also organize as binary tree organization with two pointer fields, namely, ‘LEFT’ and ‘RIGHT’ in each record that points to the left and right subtrees respectively.
- The left subtree of the record contains only records with names less than the current records name. The right subtree of the node will contain only records with name variables greater than the current name.
- The advantage of using search tree organization that it proves efficient in search operations, which the most performed operations over the symbol tables.
- A binary search tree gives both performances compared to list organization at some difficulty in implementation.