Linked List applications: Advantages and disadvantages, clear-cut explanations about “Applications of Linked List” in Data structures.
APLLICATIONS OF LINKED LIST
- Radix sort
- Multilist
- Polynomial ADT
Radix sort:
Radix sort is the generalized form of bucket sort. It can be performed by using buckets 0 to 9. In first pass, all the elements are sorted according to the last significant list.
In second pass, the numbers are arranged according to the next; least significant list and so on. This process is repeated until it reaches the most significant bit of all the numbers, the number of passes in a radix sort depends upon the number of digits in the numbers given.
Radix sort Advantages:
- Extremely fast O(n) if keys short.
- Space efficient if data in linked list or for a massive dataset using files for storage.
Disadvantages:
- Not useful if keys long
- Needs O(n) extra storage if in array in memory.
SEE: Engineering Mini Projects free download
- An example for bucket sorting.
- Sort the numbers: 25,256,80,10,8,15,174,187
First pass:
Input: Input :80,10,174,25,15,256,187,8
Consider the last significant bit.
| 10 | 15 | ||||||||
| 80 | 174 | 25 | 256 | 187 | 8 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Output:
80,10,174,25,15,256,187,8
Second pass:
Consider the second significant bit.
Input : 80,10,174,25,15,256,187,8
| 15 | 187 | ||||||||
| 08 | 10 | 25 | 256 | 174 | 80 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Output:
8,10,15,25,256,174,80,187
Third pass:
Consider the first significant bit.
Input :Input :80,10,174,25,15,256,187,8
| 15 | |||||||||
| 10 | 187 | ||||||||
| 08 | 174 | 256 | |||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Output :
8,10,15,25,80,174,187,256
MULTILIST:
More complicated application of linked list is multilist. It is Useful to maintain student registration, employee involved in different projects multilists saves, but takes more time to implement.
Multilists
An employee can involve in any number of projects and each project can be implemented by any number of employees.
- [SEE: C Program Tutorials] & [IT Companies Details]
In this fig ,employee E1 is working on project p1. E2 is working on project p2. E3 is working on project p1. The project p1 is implemented by the employees E1,E3.project p2 is implemented by the employee E2.
Thus it performs the most complicated work of linked list.