Data Structures and Algorithms (Polynomials as Link List) - Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

 5x3+4x2+3x+2

POLY->(5,3)->(4,2)->(3,1)->(2,0)->NULL

To understand this concept better let's first brush up all the basic contents that are required.

Linked list is a data structure that stores each element as an object in a node of the list. every note contains two parts data and links to the next node.

Polynomial is a mathematical expression that consists of variables and coefficients. for example x^2 - 4x + 7

In the Polynomial linked list, the coefficients and exponents of the polynomial are defined as the data node of the list.

For adding two polynomials that are stored as a linked list. We need to add the coefficients of variables with the same power. In a linked list node contains 3 members, coefficient value link to the next node.

A linked list that is used to store Polynomial looks like −

Polynomial : 4x⁷ + 12x² + 45

This is how a linked list represented polynomial looks like.

Adding two polynomials that are represented by a linked list. We check values at the exponent value of the node. For the same values of exponent, we will add the coefficients.

Example,

Input :

p1= 13x8 + 7x5 + 32x2 + 54

p2= 3x12 + 17x5 + 3x3 + 98

Output : 3x12 + 13x8 + 24x5 + 3x3 + 32x2 + 152

Explanation −
For all power, we will check for the coefficients of the exponents that have
the same value of exponents and add them. The return the final polynomial.

Algorithm

Input − polynomial p1 and p2 represented as a linked list.

Step 1: loop around all values of linked list and follow step 2& 3.

Step 2: if the value of a node’s exponent. is greater copy this node to 

result node and head towards the next node.

Step 3: if the values of both node’s exponent is same add the coefficients

and then copy the added value with node to the result.

Step 4: Print the resultant node.

Tirthankar Pal
MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview
2 year PGDM (E-Business) from Welingkar, Mumbai
4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology
Google and Hubspot Certification
Brain Bench Certification in C++, VC++, Data Structure and Project Management
10 years of Experience in Software Development out of that 6 years 8 months in Wipro
Selected in Six World Class UK Universities:-
King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds

Data Structure II (Link List 1)- Tirthankar Pal - MBA from IIT Kharagpur, GATE, GMAT, IIT Written Test, Interview were a part of MBA Entrance, B.S. in Computer Science from NIELIT

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations meaning they are not stored in locations like an array. The elements in a linked list are connected via pointers. In simple words, a linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. In a doubly linked list, there is also a reference to the previous pointer of the list.

Formally a link list is like:-

In a linear list implementation, there are always head and tail nodes, and inserting to them is a 

O(1) operation.

In Linked List implementation, it has the following characteristics:

1)Insertion - O(1)

2)Deletion - O(n)

3)Searching - O(n)

Therefore Insertion operation with O(1) stands out. Link List is being trivial data structure but has two key points:-

1) Insertion operation is O(1)

2) The list is dynamically resized.

In a singly link list there is a node and pointer to the next node.

This is a single link list.

Link List Structure:

struct node

{

    int info;

    struct node *next;

};

Types of Linked Lists:

• Simple Linked List – In this type of linked list, one can move or traverse the linked list in only one direction
• Doubly Linked List – In this type of linked list, one can move or traverse the linked list in both directions (Forward and Backward)
• Circular Linked List – In this type of linked list, the last node of the linked list contains the link of the first/head node of the linked list in its next pointer and the first/head node contains the link of the last node of the linked list in its prev pointer

#include <stdio.h>

#include <stdlib.h>

  

struct Node {

    int data;

    struct Node* next;

};

  

// This function prints contents of linked list starting

// from the given node

void printList(struct Node* n)

{

    while (n != NULL) {

        printf(" %d ", n->data);

        n = n->next;

    }

}

  

// Driver's code

int main()

{

    struct Node* head = NULL;

    struct Node* second = NULL;

    struct Node* third = NULL;

  

    // allocate 3 nodes in the heap

    head = (struct Node*)malloc(sizeof(struct Node));

    second = (struct Node*)malloc(sizeof(struct Node));

    third = (struct Node*)malloc(sizeof(struct Node));

  

    head->data = 1; // assign data in first node

    head->next = second; // Link first node with second

  

    second->data = 2; // assign data to second node

    second->next = third;

  

    third->data = 3; // assign data to third node

    third->next = NULL;

  

    // Function call

    printList(head);

  

    return 0;

}

Linked List Applications

• Dynamic memory allocation
• Implemented in stack and queue
• In undo functionality of softwares
• Hash tables, Graphs

Linked List Complexity

Time Complexity

	Worst case	Average Case
Search	O(n)	O(n)
Insert	O(1)	O(1)
Deletion	O(1)	O(1)

Space Complexity: O(n)

Tirthankar Pal

MBA from IIT Kharagpur with GATE, GMAT, IIT Kharagpur Written Test, and Interview

2 year PGDM (E-Business) from Welingkar, Mumbai

4 years of Bachelor of Science (Hons) in Computer Science from the National Institute of Electronics and Information Technology

Google and Hubspot Certification

Brain Bench Certification in C++, VC++, Data Structure and Project Management

10 years of Experience in Software Development out of that 6 years 8 months in Wipro

Selected in Six World Class UK Universities:-

King's College London, Durham University, University of Exeter, University of Sheffield, University of Newcastle, University of Leeds