Data structures: Applications of Linked List

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.

Multilist

Multilists

An employee can involve in any number of projects and each project can be implemented by any number of employees.

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.