DS - Application of List

Linked list appliaction

1. Application of linked list Polynomial ADT Radix ADT Multilist

2. Polynomial ADT: We can perform the polynomial manipulations such as addition, subtraction and differentiation etc ,. Declaration: struct poly { int coeff ; int power; struct poly *next; }*list1,*list2,*list3;

3. Creation of the polynomial: p oly create(poly *head1,poly *newnode1) { poly * ptr ; i f(head1==NULL) { head1=newnode1; }

4. else { ptr =head1; while( ptr ->next!=NULL) ptr = ptr ->next; ptr ->next=newnode1; } return(head1); }

5. Linked list based polynomial addition void add() { poly *ptr1,*ptr2, * newnode ; ptr1=list1; ptr2=list2; while(ptr1!=NULL && ptr2!=NULL) { newnode = malloc ( sizeof ( struct poly));

6. if(ptr1-> power == ptr2-> power) { newnode -> coeff =ptr1-> coeff + ptr2-> coeff ; newnode -> power = ptr1-> power; newnode -> next =NULL; list 3= create(list3, newnode ) ptr1 = ptr1-> next; ptr2 = ptr2 -> next; }

7. else { if(ptr1-> power > ptr2--> power) { newnode -> coeff =ptr1-> coeff ; newnode -> power = ptr1-> power; newnode -> next =NULL; list 3= create(list3, newnode ) ptr1 = ptr1-> next; }

8. else { newnode -> coeff =ptr2-> coeff ; newnode -> power = ptr2-> power; newnode -> next =NULL; list 3= create(list3, newnode ) ptr2 = ptr2-> next; } } }

9. Example Input: 1st number = 5x^2 + 4x^1 + 2x^0 2nd number = 5x^1 + 5x^0 Output: 5x^2 + 9x^1 + 7x^0 Input: 1st number = 5x^3 + 4x^2 + 2x^0 2nd number = 5x^1 + 5x^0 Output: 5x^3 + 4x^2 + 5x^1 + 7x^0

10. Linked list based polynomial Subtraction void sub() { poly *ptr1,*ptr2, * newnode ; ptr1=list1; ptr2=list2; while(ptr1!=NULL && ptr2!=NULL) { newnode = malloc ( sizeof ( struct poly));

11. if(ptr1-> power == ptr2-> power) { newnode -> coeff =ptr1-> coeff - ptr2-> coeff ; newnode -> power = ptr1-> power; newnode -> next =NULL; list 3= create(list3, newnode ) ptr1 = ptr1-> next; ptr2 = ptr2 -> next; }

12. else { if(ptr1-> power > ptr2-> power) { newnode -> coeff =ptr1-> coeff ; newnode -> power = ptr1-> power; newnode -> next =NULL; list 3= create(list3, newnode ) ptr1 = ptr1-> next; }

13. else { newnode -> coeff =ptr2-> coeff ; newnode -> power = ptr2-> power; newnode -> next =NULL; list 3= create(list3, newnode ) ptr2 = ptr2-> next; } } }

14. Poly * multiply() {     Node *ptr1, *ptr2,* Newnode ;     ptr1 = list1;     ptr2 = list2;     while (ptr1 != NULL) {      while (ptr2 != NULL) {      Newnode - > coeff = ptr1-> coeff * ptr2-> coeff ;   

15. Newnode ->power = ptr1->power + ptr2->power; list2=create(list3,Newnode ); ptr2 = ptr2->next; }     ptr2 = list2;  ptr1 = ptr1->next; } }

16. Radix Sort: Radix sort is one of the sorting algorithms used to sort a list of integer numbers in order. In radix sort algorithm, a list of integer numbers will be sorted based on the digits of individual numbers. Radix sort algorithm requires the number of passes which are equal to the number of digits present in the largest number among the list of numbers. For example, if the largest number is a 3 digit number then that list is sorted with 3 passes.

17. Multi-Linked Lists A multilinked list is a more general linked list with multiple links from nodes. In a general multi-linked list each node can have any number of pointers to other nodes, Multi-lists are essentially the technique of embedding multiple lists into a single data structure. A multi-list has more than one next pointer, like a doubly linked list , but the pointers create separate lists