Question:
Published on: 6 June, 2023

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.

Ans. b)

1. Access : Random / Sequential

• Array elements can be randomly Accessed using Subscript Variable

• e.g a[0],a[1],a[3] 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…)

Random questions