a) How the Polynomial function 4x^3+ 10x^2 + 3 represented using a linked list?
b) Compare and contrast between an array and a single linked list.
a) A Polynomial has mainly two fields. exponent and coefficient.
Node of a Polynomial:
For example 4x^3+ 10x^2 + 3 will represent as follows.
In each node the exponent field will store the corresponding exponent and the coefficient field will store the corresponding coefficient. Link field points to the next item in the polynomial.
1. Access : Random / Sequential
Array elements can be randomly Accessed using Subscript Variable
e.g a,a,a can be randomly accessed
While In Linked List We have to Traverse Through the Linked List for Accessing Element. So O(n) Time required for Accessing Element .
Generally In linked List Elements are accessed Sequentially.
2 . Memory Structure
Array is stored in contiguous Memory Locations , i.e Suppose first element is Stored at 2000 then Second Integer element will be stored at 2002 .
But It is not necessary to store next element at the Consecutive memory Location .
Element is stored at any available Location , but the Pointer to that memory location is stored in Previous Node.
3 . Insertion / Deletion
As the Array elements are stored in Consecutive memory Locations , so While Inserting elements ,we have to create space for Insertion.
So More time required for Creating space and Inserting Element
Similarly We have to Delete the Element from given Location and then Shift All successive elements up by 1 position
In Linked List we have to Just Change the Pointer address field (Pointer),So Insertion and Deletion Operations are quite easy to implemen
4 . Memory Allocation
Memory Should be allocated at Compile-Time in Array . i.e at the time when Programmer is Writing Program
In Linked list memory can be allocated at Run-Time , i.e After executing Program
Stack uses Static Memory Allocation and Linked List Uses Dynamic Memory Allocation( malloc,calloc,delete etc…)
What is a Judy array?
What are the difference between linear and non-linear data structure?
What is a self referential structure? What is difference between Union & Structure?
Define the ADT for stack. Show the implementation of the stack data structure using linked list.