DATA STRUCTURE

Introduction to Data structures

Data structure is a Specific way to store and organize data in a computer's memory
so that these data can be used efficiently later. Data may be organized and stored
in many different ways.
The logical or mathematical model for a particular organization of data is termed
as a data structure.
The variety of a particular data model depends on the two factors -
• It must be rich enough in structure to reflect the actual relationships of
the data with the real world object.
• The structure should be simple enough so that anyone can efficiently process
the data structure on demand.

Abstract Data Type (ADT)

An abstract data type (ADT) is a mathematical model for data types where a data
type is defined by its behavior (semantics) from the point of view of a user of
the data, specifically in terms of possible values, possible operations on data
of this type, and the behavior of these operations. When a class is used as a
type, it is an abstract type that refers to a hidden representation.
In this model an ADT is typically implemented as a class, and each instance of
the ADT is usually an object of that class. In ADT all the implementation details
are hidden.
Categories of Data Structure:
The data structure can be sub divided into major types:
• Linear Data Structure
• Non-linear Data Structure

Data Structure|1
Linear Data Structure:
A data structure is said to be linear if its elements combine to form any specific
order. There are basically two techniques of representing such linear structure
within memory.
• First way is to provide the linear relationships among all the elements
represented by means of linear memory location. These linear structures are
termed as arrays.
• The second technique is to provide the linear relationship among all the
elements represented by using the concept of pointers or links. These linear
structures are termed as linked lists.

The common examples of linear data structure are:

Arrays
The simplest type of data structure is a linear or one-dimensional array. A linear
array is a list of a finite number n of similar data elements referenced
respectively by a set of n consecutive numbers, usually 1, 2, 3, .... n. If we
choose the name A for the array, then the elements of A are denoted by any of the
following notation.
Parenthesis notation: A(1), A(2), A(3), ..., A(N)
Bracket notation: A[1], A[2], A[3], ..., A[N]
Regardless of the notation, the number K in A[K] is called a subscript and A[K]
is called a subscripted variable.

Stacks
A stack is a linear data structure where elements are stored in the LIFO (Last
In First Out) principle where the last element inserted would be the first element
to be deleted. A stack is an Abstract Data Type (ADT) that is popularly used in
most programming languages. It is named stack because it has the similar
operations as the real-world stacks, for example − a pack of cards or a pile of
plates, etc.
A stack allows all data operations at one end only. At any given time, we can
only access the top element of a stack. There are two common operations on stack
i.e. PUSH and POP.

Data Structure|2
Queues
A queue is a linear data structure where elements are stored in the FIFO (First
In First Out) principle where the first element inserted would be the first
element to be accessed. Like stack, a queue is also an Abstract Data Type (ADT).
The thing that makes queue different from stack is that a queue is open at both
its ends. The operation Enqueue (data is inserted into the queue) performs through
one end called REAR and Dequeue (deleted from the queue) performs through the
other end called FRONT. Queue is very frequently used in most programming
languages.
A real-world example of queue can be a single-lane one-way road, where the vehicle
enters first, exits first. More real-world examples can be seen as queues at the
ticket windows and bus-stops.

Linked lists
A linked list is a linear data structure which can store a collection of "nodes"
connected together via links i.e. pointers. Linked lists nodes are not stored at
a contiguous location, rather they are linked using pointers to the different
memory locations. A node consists of the data value and a pointer to the address
of the next node within the linked list.
A linked list is a dynamic linear data structure whose memory size can be allocated
or de-allocated at run time based on the operation insertion or deletion, this
helps in using system memory efficiently. Linked lists can be used to implement
various data structures like a stack, queue, graph, etc.

Data Structure|3
Nonlinear Data Structure:
This structure is mostly used for representing data that contains a hierarchical
relationship among various elements.
The common examples of Non-linear data structure are:

Tree:
Data often contain a hierarchical relationship among various elements. The data
structure that reflects this relationship is termed as rooted tree graph or a
tree.

Graph:
Data sometimes hold a relationship between the pairs of elements which is not
necessarily following the hierarchical structure. Such data structure is termed
as a Graph.

Data Structure Operations

There are certain operations which are require to process the data appearing in
our data structures. Actually, the particular data structure that one chooses for
a given situation depends largely on the frequency with which specific operations
are performed.
The following are the major operations:
• Traversing: Accessing each record exactly once so that certain items in the
record may be processed. This accessing and processing is sometimes called
"visiting" the record.
• Searching: Finding the location of the record with a given key value, or finding
the locations of all records which satisfy one or more conditions.
• Inserting: Adding a new record to the structure.
• Deleting: Removing a record from the structure.
• Sorting: Arranging the records in some logical order i.e. ascending or
descending order (e.g., alphabetically according to some NAME key, or in
numerical order according to some NUMBER key).
• Merging: Combining the records in two different sorted files into a single
sorted file.
Data Structure|4
Algorithm
An algorithm is a finite set of instructions, those if followed, accomplishes a
particular task. It is not language specific, we can use any language and symbols
to represent instructions.
The criteria of an algorithm
• Input: Zero or more inputs are externally supplied to the algorithm.
• Output: At least one output is produced by an algorithm.
• Definiteness: Each instruction is clear and unambiguous.
• Finiteness: In an algorithm, it will be terminated after a finite number of
steps for all different cases.
• Effectiveness: Each instruction must be very basic, so the purpose of those
instructions must be very clear to us.

Complexity
The complexity of an algorithm is a measure of the computational resources
(primarily time and space, or memory) required to run it, as a function of the
size of its input. It is a fundamental concept in computer science used to
evaluate and compare the efficiency and scalability of different algorithms,
especially for large inputs.
Types of Complexity:
The two main types of algorithmic complexity are:
• Time Complexity: Describes the amount of time an algorithm takes to run in
relation to the size of the input data. It is measured by counting the number
of elementary operations performed (e.g., comparisons, assignments) rather than
the actual execution time, which can vary between different computers and
programming languages.
• Space Complexity: Describes the amount of memory (space) an algorithm requires
to run to completion, also as a function of the input size. This includes space
for input variables and any extra space needed during execution (auxiliary
space).
Common Asymptotic Notations:
To describe complexity, computer scientists use notations that define the growth
rate of an algorithm:
• Big-O (𝑂): Represents the worst-case scenario (upper bound). It ensures the
algorithm will never perform worse than this limit.
• Big-Omega (Ω): Represents the best-case scenario (lower bound).
• Big-Theta (Θ): Represents the average-case scenario or a tight bound where
best and worst cases are the same.

Data Structure|5
Hierarchy of Complexities (Best to Worst)
Algorithms are classified into "orders of growth" based on how they scale:
• 𝑂(1) - Constant Time: The operation time is the same regardless of input size
(e.g., accessing an array element by index).
• (log𝑛) - Logarithmic Time: The search space is halved at each step
(e.g., Binary Search).
• (𝑛) - Linear Time: Time grows directly proportional to the input size
(e.g., Linear Search).
• (𝑛 log 𝑛) - Logarithmic Time: Typical of efficient sorting algorithms like
Merge Sort and Quick Sort.
• (𝑛2) - Quadratic Time: Time grows proportionally to the square of the input
size, often involving nested loops (e.g., Bubble Sort).
• (2𝑛) - Exponential Time: The number of operations doubles with each addition
to the data set; these are generally impractical for large 𝑛.
• 𝑂(𝑛!) - Factorial Time: The most complex category, often found in "brute force"
solutions like the Traveling Salesman Problem.

Arrays
An Array is a finite collection of similar elements stored in adjacent memory
locations. An array containing n number of elements is referenced using an index
that varies from 0 to n - 1. For example, the elements of an array arr[n]
containing n elements are denoted by arr[0], arr[1], arr[2], ..., arr[n-1], where
0 is the lower bound of the array, n – 1 is the upper bound of the array and 0,
1, 2, etc. are indices of the array.

Operations on Arrays
There are a number of operations that can be performed on arrays. These operations
include:
• Traversal: Processing each element in the array
• Search: Finding the location of an element with a given value
• Insertion: Adding a new element to an array
• Deletion: Removing an element from an array
• Sorting: Organizing the array elements in some order
• Merging: Combining two arrays into a single array
• Reversing: Reversing the elements of an array
Traversing:
Traversing an array means accessing each and every element of the array for a
specific purpose. Traversing the data elements of an array A can include printing
every element, counting the total number of elements, or performing any process
on these elements.
Data Structure|6
 TRAVERSE (A, LB, UB)
Consider a linear array A with lower bound LB and upper bound UB is maintained
in memory. This algorithm traverses the array A by applying an operation PROCESS
to each element of A.
Step 1: [INITIALIZATION] SET K = LB
Step 2: Repeat Steps 3 to 4 while K <= UB
Step 3: Apply Process to: A[K]
Step 4: SET K = K + 1
[END OF LOOP]
Step 5: EXIT

Insertion:
Let A be a collection of data elements in the memory of the computer. "Inserting"
refers to the operation of adding another element to the collection A, and
"deleting" refers to the operation of removing one of the elements from A.
Inserting an element at the "end" of a linear array can be easily done provided
the memory space allocated for the array is large enough to accommodate the
additional element.
To insert an element in the middle of the array, on the average, half of the
elements must be moved downward to new locations to accommodate the new element
and keep the order of the other elements.
INSERT (A, N, POS, ITEM)
Consider a linear array A with N elements is maintained in memory and POS is a
positive integer such that POS<=N. This algorithm inserts the given ITEM of
information at the given position POS.
Step 1: [INITIALIZATION] SET K = N
Step 2: Repeat Steps 3 and 4 while K >= POS
Step 3: SET A[K + 1] = A[K]
Step 4: SET K = K – 1
[END OF LOOP]
Step 5: SET N = N + 1
Step 6: SET A[POS] = ITEM
Step 7: EXIT
Deletion:
Deleting an element at the "end" of an array presents no difficulties, but
deleting an element somewhere in the middle of the array would require that each
subsequent element be moved one location upward in order to "fill up" the array.
DELETE (A, N, POS, ITEM)
Consider a linear array A with N elements is maintained in memory and POS is a
positive integer such that POS<=N. This algorithm deletes the element from the
index POS.
Step 1: SET ITEM = A[POS]
Step 2: [INITIALIZATION] SET K = POS
Step 2: Repeat Steps 3 and 4 while K <= N – 1
Step 3: SET A[K] = A[K + 1]
Step 4: SET K = K + 1
[END OF LOOP]
Step 5: SET N = N – 1
Step 6: EXIT

Data Structure|7
Merging Two Arrays
Merging two arrays in a third array means first copying the contents of the first
array into the third array and then copying the contents of the second array into
the third array. Hence, the merged array contains the contents of the first array
followed by the contents of the second array.
If the arrays are unsorted, then merging the arrays is very simple, as one just
needs to copy the contents of one array into another.
But merging is not a trivial task when the two arrays are sorted and the merged
array also needs to be sorted. If we have two sorted arrays and the resultant
merged array also needs to be a sorted one, then the task of merging the arrays
becomes a little difficult.

Search Operation
You can perform a search for an array element based on its value or its index.
There are two types of searching.
Linear Search:
This is also known as sequential search. The given values will be compared with
the elements of the array starting from the beginning or ending index of the
array. This search can be implemented on any array (sorted or unsorted)
LSEARCH(A, N, ITEM, LOC)
Consider A is a linear array with N elements. This algorithm finds the index
LOC of the given value ITEM in the array A using sequential search. If not
found, sets LOC as NULL.
Step 1: Set K = 0
Step 2: Repeat steps 4 and 5 while K < N
Step 3: If A[K] = ITEM THEN:
Step 4: Set LOC = K and Return
Step 5: Set K = K +1
[END OF LOOP]
Step 6: Set LOC = NULL
Step 7: Return

Binary Search:
Binary search is an efficient searching algorithm used to locate a value within
a sorted array. It works by repeatedly dividing the search space in half,
resulting in a time complexity of O(log N), which is significantly faster than
linear search for large datasets.
Key Concepts:
Sorted Data Requirement: The array must be sorted in a specific order (ascending
or descending) before performing a binary search. Applying it to an unsorted
array will yield incorrect results.
Divide and Conquer: The algorithm follows a divide-and-conquer approach,
eliminating half of the remaining elements in each step.
Pointers: The process uses pointers (or indices) for the low (start), high (end),
and mid (middle) of the current search range.

Data Structure|8
TWO-DIMENSIONAL ARRAYS
One-dimensional arrays are organized linearly in only one direction. But at times,
we need to store data in the form of grids or tables.
Here, the concept of single-dimension arrays is extended to incorporate two-
dimensional data structures. A two-dimensional array is specified using two
subscripts where the first subscript denotes the row and the second denotes the
column. The C compiler treats a two-dimensional array as an array of one-
dimensional arrays.

Although we have shown a rectangular picture of a two-dimensional array, in the

memory, these elements actually will be stored sequentially. There are two ways
of storing a two-dimensional array in the memory. The first way is the row major
order and the second is the column major order.
Row major order: The elements of the first row are stored before the elements of
the second and third rows. That is, the elements of the array are stored row by
row where n elements of the first row will occupy the first n locations.

Column major order: The elements of the first column are stored before the
elements of the second and third column. That is, the elements of the array are
stored column by column where m elements of the first column will occupy the
first m locations.

In one-dimensional arrays, we have seen that the computer does not keep track of
the address of every element in the array. It stores only the address of the
first element and calculates the address of other elements from the base address
(address of the first element). Same is the case with a two-dimensional array.
Here also, the computer stores the base address, and the address of the other
elements is calculated using the following formula.

Column major order:

Address(A[I][J]) = Base_Address + w{M ( J – 1) + (I – 1)}
Row major order:
Address(A[I][J]) = Base_Address + w{N ( I – 1) + (J – 1)}

where w is the number of bytes required to store one element, N is the number of
columns, M is the number of rows, and I and J are the subscripts of the array
element.

Data Structure|9
SPARSE MATRICES
Sparse matrix is a matrix that has large number of elements with a zero value.
In order to efficiently utilize the memory, specialized algorithms and data
structures that take advantage of the sparse structure should be used. If we
apply the operations using standard matrix structures and algorithms to sparse
matrices, then the execution will slow down and the matrix will consume large
amount of memory. Sparse data can be easily compressed, which in turn can
significantly reduce memory usage.
There are two types of sparse matrices. In the first type of sparse matrix, all
elements above the main diagonal have a zero value. This type of sparse matrix
is also called a (lower) triangular matrix because if you see it pictorially, all
the elements with a non-zero value appear below the diagonal.
In a lower triangular matrix, A[i,j] = 0 where i < j. An n x n lower-triangular
matrix A has one non-zero element in the first row, two non-zero elements in the
second row and likewise n non-zero elements in the nth row.

Data S t r u c t u r e | 10
To store a lower-triangular matrix efficiently in the memory, we can use a one-
dimensional array which stores only non-zero elements. The mapping between a two-
dimensional matrix and a one-dimensional array can be done in any one of the
following ways:
• Row-wise mapping—Here the contents of array A[] will be
{1, 5,3, 2, 7, –1, 3, 1, 4, 2, –9, 2, –8, 1, 7}
• Column-wise mapping—Here the contents of array A[] will be
{1, 5, 2, 3, –9, 3, 7, 1, 2, –1, 4, –8, 2, 1, 7}
In an upper-triangular matrix, A[i,j] = 0 where i > j. An n x n upper-triangular
matrix A has n non-zero elements in the first row, n–1 non-zero elements in the
second row and likewise one non-zero element in the nth row.

There is another variant of a sparse matrix, in which elements with a non-zero

value can appear only on the diagonal or immediately above or below the diagonal.
This type of matrix is also called a tri-diagonal matrix.
Hence in a tridiagonal matrix, A[i,j] = 0, where |i – j| > 1. In a tridiagonal
matrix, if elements are present on
a) the main diagonal, it contains non-zero elements for i=j. In all, there will
be n elements.
b) below the main diagonal, it contains non-zero elements for i=j+1. In all,
there will be n–1 elements.
c) above the main diagonal, it contains non-zero elements for i=j–1. In all,
there will be n–1 elements.

To store a tri-diagonal matrix efficiently in the memory, we can use a one-

dimensional array that stores only non-zero elements. The mapping between a
two-dimensional matrix and a one-dimensional array can be done in any one of the
following ways:
• Row-wise mapping—Here the contents of array A[] will be
{4, 1, 5, 1, 2, 9, 3, 1, 4, 2, 2, 5, 1, 9, 8, 7}
• Column-wise mapping—Here the contents of array A[] will be
{4, 5, 1, 1, 9, 2, 3, 4, 1, 2, 5, 2, 1, 8, 9, 7}
• Diagonal-wise mapping—Here the contents of array A[] will be
{5, 9, 4, 5, 8, 4, 1, 3, 2, 1, 7, 1, 2, 1, 2, 9}
Data S t r u c t u r e | 11
Linked Lists
A linked list is a linear collection of data elements called nodes. Linked list
is a data structure which in turn can be used to implement other data structures.
Thus, it acts as a building block to implement data structures such as stacks,
queues, and their variations.

linked list is a collection of nodes in which every node contains two parts, an
information and a pointer to the next node. The left part of the node which
contains data may include a simple data type, an array, or a structure. The right
part of the node contains a pointer to the next node. The last node will store a
special value called NULL. Hence, a NULL pointer denotes the end of the list.
Since in a linked list, every node contains a pointer to another node which is
of the same type, it is also called a self-referential data type.
Linked lists contain a pointer variable START that stores the address of the
first node in the list. We can traverse the entire list using START which contains
the address of the first node; the next part of the first node in turn stores the
address of its succeeding node. If START = NULL, then the linked list is empty
and contains no nodes.
In C, we can implement a linked list using the following code:
struct node
{
int data;
struct node *next;
};

Memory Representation:
A linked list is represented in memory as a collection of self-
referential nodes that are linked together by pointers (or references). Unlike
arrays, the nodes are not stored in contiguous memory locations; instead, each
node contains the address of the next node, allowing them to be scattered across
different parts of the memory heap.
In order to form a linked list, we need a structure called node which has two
fields, DATA and NEXT. DATA will store the information part and NEXT will store
the address of the next node in sequence. The variable START is used to store the
address of the first node.

Data S t r u c t u r e | 12
Linked Lists versus Arrays:
Both arrays and linked lists are a linear collection of data elements. But unlike
an array, a linked list does not store its nodes in consecutive memory locations.
Another point of difference between an array and a linked list is that a linked
list does not allow random access of data. Nodes in a linked list can be accessed
only in a sequential manner. But like an array, insertions and deletions can be
done at any point in the list in a constant time.
Another advantage of a linked list over an array is that we can add any number
of elements in the list. This is not possible in case of an array.
For example, if we declare an array as int data[20], then the array can store a
maximum of 20 data elements only. There is no such restriction in case of a linked
list.

Memory Allocation and De-allocation for a Linked List:

If we want to add a node to an already existing linked list in the memory, we
first find free space in the memory and then use it to store the information.
We have seen that every linked list has a pointer variable START which stores the
address of the first node of the list. Likewise, for the free pool (which is a
linked list of all free memory cells), we have a pointer variable AVAIL which
stores the address of the first free space.

SINGLY LINKED LIST:

A singly linked list is the simplest type of linked list in which every node
contains some data and a pointer to the next node of the same data type. By saying
that the node contains a pointer to the next node, we mean that the node stores
the address of the next node in sequence. A singly linked list allows traversal
of data only in one way.

Data S t r u c t u r e | 13
Traversing a Linked List
Traversing a linked list means accessing the nodes of the list in order to perform
some processing on them. Remember a linked list always contains a pointer variable
START which stores the address of the first node of the list. End of the list is
marked by storing NULL or –1 in the NEXT field of the last node. For traversing
the linked list, we also make use of another pointer variable PTR which points
to the node that is currently being accessed.
• Traversing a linked list
Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != NULL
Step 3: Apply Process to PTR -> INFO
Step 4: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 5: EXIT
• Print the number of nodes in a linked list
Step 1: [INITIALIZE] SET COUNT = 0, PTR = START
Step 2: Repeat Steps 4 and 5 while PTR != NULL
Step 3: SET COUNT = COUNT + 1
Step 4: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 5: Write: COUNT
Step 6: EXIT

Algorithms:
• Inserting a Node at the Beginning of a Linked List
INSERT_BEG(START, INFO, NEXT, AVAIL, VAL)
Step 1: IF AVAIL = NULL THEN:
Write OVERFLOW and EXIT
[END OF IF]
Step 2: SET NEW_NODE = AVAIL, AVAIL = AVAIL -> NEXT
Step 3: SET NEW_NODE -> INFO = VAL
Step 4: SET NEW_NODE -> NEXT = START, START = NEW_NODE
Step 5: EXIT
• Inserting a Node at the End of a Linked List
INSERT_END(START, INFO, NEXT, AVAIL, VAL)
Step 1: IF AVAIL = NULL THEN:
Write OVERFLOW and EXIT
[END OF IF]
Step 2: SET NEW_NODE = AVAIL, AVAIL = AVAIL -> NEXT
Step 3: SET NEW_NODE -> INFO = VAL, NEW_NODE -> NEXT = NULL
Step 4: SET PTR = START
Step 5: Repeat Step 8 while PTR -> NEXT != NULL
Step 6: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 7: SET PTR -> NEXT = NEW_NODE
Step 8: EXIT
Inserting a Node After a Given Node in a Linked List
Inserting a Node Before a Given Node in a Linked List
Deleting the First Node from a Linked List
Deleting the Last Node from a Linked List
Deleting the Node containing the given data in a Linked List
Etc.

Data S t r u c t u r e | 14
CIRCULAR LINKED LIST
In a circular linked list, the last node contains a pointer to the first node of
the list. Thus, a circular linked list has no beginning and no ending.
We can traverse the list until we find the NEXT entry that contains the address
of the first node of the list. This denotes the end of the linked list, that is,
the node that contains the address of the first node is actually the last node
of the list.

Traversing a Linked List

Algorithm for traversing a circular linked list

Step 1: [INITIALIZE] SET PTR = START
Step 2: Repeat Steps 3 and 4 while PTR != START
Step 3: Apply Process to PTR -> INFO
Step 4: SET PTR = PTR -> NEXT
[END OF LOOP]
Step 5: EXIT

Algorithms:
Inserting a Node at the Beginning
Inserting a Node at the End
Inserting a Node After a Given Node
Inserting a Node Before a Given Node
Deleting the First Node
Deleting the Last Node
Deleting the Node containing the given data
Etc.

DOUBLY LINKED LISTS

A doubly linked list or a two-way linked list is a more complex type of linked
list which contains a pointer to the next as well as the previous node in the
sequence. Therefore, it consists of three parts—data, a pointer to the next
node, and a pointer to the previous node

Data S t r u c t u r e | 15
In C, the structure of a doubly linked list can be given as,
struct node
{
struct node *prev;
int data;
struct node *next;
};

The PREV field of the first node and the NEXT field of the last node will contain
NULL. The PREV field is used to store the address of the preceding node, which
enables us to traverse the list in the backward direction.

Algorithms:
Traversing using next pointer
Traversing using prev pointer
Inserting a Node at the Beginning
Inserting a Node at the End
Inserting a Node After a Given Node
Inserting a Node Before a Given Node
Deleting the First Node
Deleting the Last Node
Deleting the Node containing the given data

CIRCULAR DOUBLY LINKED LIST

A circular doubly linked list or a circular two-way linked list is a more
complex type of linked list which contains a pointer to the next as well as the
previous node in the sequence. The difference between a doubly linked and a
circular doubly linked list is same as that exists between a singly linked list
and a circular linked list. The circular doubly linked list does not contain
NULL in the previous field of the first node and the next field of the last
node. Rather, the next field of the last node stores the address of the first
node of the list, i.e., START. Similarly, the previous field of the first field
stores the address of the last node.

Data S t r u c t u r e | 16
Algorithms:
Traversing using next pointer
Traversing using prev pointer
Inserting a Node at the Beginning
Inserting a Node at the End
Inserting a Node After a Given Node
Inserting a Node Before a Given Node
Deleting the First Node
Deleting the Last Node
Deleting the Node containing the given data

Header Linked List

A header linked list is a special type of linked list which contains a header
node at the beginning of the list. So, in a header linked list, START will not
point to the first node of the list but START will contain the address of the
header node.
The following are the two variants of a header linked list:

• Grounded header linked list: It stores NULL in the next field of the last
node.
• Circular header linked list: It stores the address of the header node in
the next field of the last node. Here, the header node will denote the end
of the list.

Data S t r u c t u r e | 17
Memory representation of a circular header linked list:

Algorithms:
Traversing using next pointer
Traversing using prev pointer
Inserting a Node at the Beginning
Inserting a Node at the End
Inserting a Node After a Given Node
Inserting a Node Before a Given Node
Deleting the First Node
Deleting the Last Node
Deleting the Node containing the given data

Polynomial Representation
Linked lists can be used to represent polynomials and the different operations
that can be performed on them.
Polynomial is represented in the memory using a linked list.

Consider a polynomial 6x3 + 9x2 + 7x + 1.

Every individual term in a polynomial consists of two parts, a coefficient and a
power. Here, 6, 9, 7, and 1 are the coefficients of the terms that have 3, 2, 1,
and 0 as their powers respectively.
Every term of a polynomial can be represented as a node of the linked list.

Data S t r u c t u r e | 18
Write a program to store a polynomial using linked list. Also, perform addition
and subtraction on two polynomials.

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
int num;
int coeff;
struct node *next;
};

struct node *start1 = NULL;

struct node *start2 = NULL;
struct node *start3 = NULL;
struct node *start4 = NULL;
struct node *last3 = NULL;
struct node *create_poly(struct node *);
struct node *display_poly(struct node *);
struct node *add_poly(struct node *, struct node *, struct node *);
struct node *sub_poly(struct node *, struct node *, struct node *);
struct node *add_node(struct node *, int, int);

int main()
{
int option;
clrscr();
do
{
printf("\n******* MAIN MENU *******");
printf("\n 1. Enter the first polynomial");
printf("\n 2. Display the first polynomial");
printf("\n 3. Enter the second polynomial");
printf("\n 4. Display the second polynomial");
printf("\n 5. Add the polynomials");
printf("\n 6. Display the result");
printf("\n 7. Subtract the polynomials");
printf("\n 8. Display the result");
printf("\n 9. EXIT");
printf("\n\n Enter your option : ");
scanf("%d", &option);
switch(option)
{
case 1: start1 = create_poly(start1);
break;
case 2: start1 = display_poly(start1);
break;
case 3: start2 = create_poly(start2);
break;
case 4: start2 = display_poly(start2);
break;
case 5: start3 = add_poly(start1, start2, start3);
break;
case 6: start3 = display_poly(start3);
break;
case 7: start4 = sub_poly(start1, start2, start4);
break;
Data S t r u c t u r e | 19
 case 8: start4 = display_poly(start4);
break;
}
} while(option!=9);
getch();
return 0;
}
struct node *create_poly(struct node *start)
{
struct node *new_node, *ptr;
int n, c;
printf("\n Enter the number : ");
scanf("%d", &n);
printf("\t Enter its coefficient : ");
scanf("%d", &c);
while(n != –1)
{
if(start==NULL)
{
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> num = n;
new_node -> coeff = c;
new_node -> next = NULL;
start = new_node;
}
else
{
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> num = n;
new_node -> coeff = c;
new_node -> next = NULL;
ptr -> next = new_node;
}
printf("\n Enter the number : ");
scanf("%d", &n);
if(n == –1)
break;
printf("\t Enter its coefficient : ");
scanf("%d", &c);
}
return start;
}
struct node *display_poly(struct node *start)
{
struct node *ptr;
ptr = start;
while(ptr != NULL)
{
printf("\n%d x %d\t", ptr -> num, ptr -> coeff);
ptr = ptr -> next;
}
return start;
}

Data S t r u c t u r e | 20
struct node *add_poly(struct node *start1, struct node *start2, struct node
*start3)
{
struct node *ptr1, *ptr2;
int sum_num, c;
ptr1 = start1, ptr2 = start2;
while(ptr1 != NULL && ptr2 != NULL)
{
if(ptr1 -> coeff == ptr2 -> coeff)
{
sum_num = ptr1 -> num + ptr2 -> num;
start3 = add_node(start3, sum_num, ptr1 -> coeff);
ptr1 = ptr1 -> next;
ptr2 = ptr2 -> next;
}
else if(ptr1 -> coeff > ptr2 -> coeff)
{
start3 = add_node(start3, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> next;
}
else if(ptr1 -> coeff < ptr2 -> coeff)
{
start3 = add_node(start3, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> next;
}
}
if(ptr1 == NULL)
{
while(ptr2 != NULL)
{
start3 = add_node(start3, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> next;
}
}
if(ptr2 == NULL)
{
while(ptr1 != NULL)
{
start3 = add_node(start3, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> next;
}
}
return start3;
}
struct node *sub_poly(struct node *start1, struct node *start2, struct node
*start4)
{
struct node *ptr1, *ptr2;
int sub_num, c;
ptr1 = start1, ptr2 = start2;
do
{
if(ptr1 -> coeff == ptr2 -> coeff)
{
sub_num = ptr1 -> num – ptr2 -> num;
start4 = add_node(start4, sub_num, ptr1 -> coeff);
ptr1 = ptr1 -> next;

Data S t r u c t u r e | 21
 ptr2 = ptr2 -> next;
}
else if(ptr1 -> coeff > ptr2 -> coeff)
{
start4 = add_node(start4, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> next;
}
else if(ptr1 -> coeff < ptr2 -> coeff)
{
start4 = add_node(start4, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> next;
}
}while(ptr1 != NULL || ptr2 != NULL);
if(ptr1 == NULL)
{
while(ptr2 != NULL)
{
start4 = add_node(start4, ptr2 -> num, ptr2 -> coeff);
ptr2 = ptr2 -> next;
}
}
if(ptr2 == NULL)
{
while(ptr1 != NULL)
{
start4 = add_node(start4, ptr1 -> num, ptr1 -> coeff);
ptr1 = ptr1 -> next;
}
}
return start4;
}
struct node *add_node(struct node *start, int n, int c)
{
struct node *ptr, *new_node;
if(start == NULL)
{
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> num = n;
new_node -> coeff = c;
new_node -> next = NULL;
start = new_node;
}
else
{
ptr = start;
while(ptr -> next != NULL)
ptr = ptr -> next;
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> num = n;
new_node -> coeff = c;
new_node -> next = NULL;
ptr -> next = new_node;
}
return start;
}

Data S t r u c t u r e | 22