1.

1 APPLICATIONS ON SINGLE LINKED LIST:

Linked lists can be used to represent polynomials and the different

operations that can be performed on them. In this section, we will see how
polynomials are represented in the memory using linked lists.

1.1.1 Polynomial Expression Representation:

Let us see how a 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.

Figure 1.22 shows the linked representation of the terms of the above
polynomial.

Figure 1.22 Linked representation of a polynomial

1.1.2 Addition and Multiplication:

Addition of Polynomials:

In this approach we will add the coefficients of elements having the

same power in both the polynomial equations.

Example:

Input:
1st polynomial Expression = 5x^2+ 4x^1 +
 2x^0

2nd polynomial Expression = 5x^1 + 5x^0

Output:
5x^2 + 9x^1 + 7x^0

Consider the below Fig 1.23, which adds the two polynomials. The two
polynomials
are represented in linked list. The elements which having the same power
those corresponding coefficients are added.

Figure 1.23 Addition of polynomials

Multiplication of Polynomials:

1. In this approach we will multiply the 2nd polynomial with each

term of 1st polynomial.
2. Store the multiplied value in a new linked list.
3. Then we will add the coefficients of elements having the same power
in resultant polynomial.
Example:
Input: Poly1: 3x^2 + 5x^1 + 6, Poly2: 6x^1 + 8
Output: 18x^3 + 54x^2 + 76x^1 + 48
On multiplying each element of 1st polynomial with elements of 2nd
polynomial, we get 18x^3 + 24x^2 + 30x^2 + 40x^1 + 36x^1 + 48
On adding values with same power of x,
18x^3 + 54x^2 + 76x^1 + 48

Figure 1.24 Multiplication of polynomials

1.1.3 Sparse Matrix Representation using Linked Lists:

Sparse Matrix:
A matrix is a two-dimensional data object made of m rows and n columns,
therefore

having total m x n values. If most of the elements of the matrix have 0 value,
then it is called a sparse matrix.
The sparse matrix shown in Fig. 1.25 can be represented using a linked list
for every row and column. Since a value is in exactly one row and one column,
it will appear in both lists exactly once. A node in the multi-linked will have
four parts. First stores the data, second stores a pointer to the next node in the
row, third stores a pointer to the next node in the column, and the fourth stores
the coordinates or the row and column number in which the data appears in the
matrix. However, as in case of doubly linked lists, we can also have a
corresponding inverse pointer for every pointer in the multi-linked list
representation of a sparse matrix.
Figure 1.25 Sparse matrix

Note:
When a non-zero value in the sparse matrix is set to zero, the corresponding
node in the multi- linked list must be deleted.

Figure 1.26 Multi-linked representation of sparse matrix shown in Fig. 1.25

1.2ADVANTAGES AND DISADVANTAGES OF SINGLE LINKED LIST:

ADVANTAGES:
 Insertions and Deletions can be done easily.
 It does not need movement of elements for insertion and deletion.
 It space is not wasted as we can get space according to our requirements.
 Its size is not fixed.
 It can be extended or reduced according to requirements.
 Elements may or may not be stored in consecutive memory available,
even then we can store the data in computer.
 It is less expensive.
DISADVANTAGES:
 It requires more space as pointers are also stored with information.
 Different amount of time is required to access each element.
 If we have to go to a particular element then we have to go through all
those elements that come before that element.
 We cannot traverse it from last & only from the beginning.
 It is not easy to sort the elements stored in the linear linked list.
1.1 REVERSING SINGLE LINKED LIST:

Algorithm to reverse a Single Linked List:

Input: head node of the linked list
Begin:

If (head != NULL) then

prevNode ← head head
← head.next curNode ←
head
prevNode.next ← NULL
While (head != NULL) do
head ← head.next
curNode.next ← prevNode
prevNode ← curNode
curNode ← head
End while

head ← prevNode

End if End
1) Create two more pointers other than head namely prevNode and curNode that
will hold the reference of previous node and current node respectively. Make
sure that prevNode points to first node i.e. prevNode = head. head should now
point to its next node i.e. the second node head = head->next. curNode
should also points to the second node i.e. curNode = head.

2) Now, disconnect the previous node i.e. the first node from others. We will
make sure that it points to none. As this node is going to be our last node.
Perform operation prevNode-
>next = NULL.

3) Move head node to its next node i.e. head = head->next.

4) Now, re-connect the current node to its previous node i.e. curNode->next =
prevNode;.

5) Point the previous node to current node and current node to head node.
Means they should now point to prevNode = curNode; and curNode = head.
 6) Repeat steps 3-5 till head pointer becomes NULL.

7) Now, after all nodes has been re-connected in the reverse order. Make the last
node as the first node. Means the head pointer should point to prevNode
pointer. Perform head = prevNode;. Finally you end up with a reversed linked
list of its original.
QUEUE USING ARRAYS

OPERATIONS PERFORMD ON QUEUE

ENQUEUE

INSERTING AN ELEMENT FROM REAR IS CALLED EN QUEUE

Algorithm

 Step 1: IF REAR = MAX – 1

Write OVERFLOW
Go to step
[END OF IF]
 Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
 Step 3: Set QUEUE[REAR] = NUM
 Step 4: EXIT

1. void insert (int queue[], int max, int front, int rear, int item)
2. {
3. if (rear + 1 == max)
4. {
5. printf("overflow");
6. }
7. else
8. {
9. if(front == -1 && rear == -1)
10. {
11. front = 0;
12. rear = 0;
13. }
14. else
15. {
16. rear = rear + 1;
17. }
18. queue[rear]=item;
19. }
20. }
Algorithm

 Step 1: IF FRONT = -1 or FRONT > REAR

Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
 Step 2: EXIT

1. int delete (int queue[], int max, int front, int rear)
2. {
3. int y;
4. if (front == -1 || front > rear)
5.
6. {
7. printf("underflow");
8. }
9. else
10. {
11. y = queue[front];
12. if(front == rear)
13. {
14. front = rear = -1;
15. else
16. front = front + 1;
17.
18. }
19. return y;
20. }
21. }
22. #include<stdio.h>
23. #include<stdlib.h>
24. #define maxsize 5
25. void insert();
26. void delete();
27. void display();
28. int front = -1, rear = -1;
29. int queue[maxsize];
30. void main ()
31. {
32. int choice;
33. printf("\nEnter your choice ?");
34. scanf("%d",&choice);
35. while(choice != 4)
36. {
37. printf("\n*************************Main Menu*************
****************\n");
38. printf("\
n=======================================================
==========\n");
39. printf("\n1.insert an element\n2.Delete an element\n3.Display the qu
eue\n4.Exit\n");
40. printf("\nEnter your choice ?");
41. scanf("%d",&choice);
42. switch(choice)
43. {
44. case 1:
45. insert();
46. break;
47. case 2:
48. delete();
49. break;
50. case 3:
51. display();
52. break;
53. case 4:
54. exit(0);
55. break;
56. default:
57. printf("\nEnter valid choice??\n");
58. }
59. }
60. }
61. void insert()
62. {
63. int item;
64. printf("\nEnter the element\n");
65. scanf("%d",&item);
66. if(rear == maxsize-1)
67. {
68. printf("\nOVERFLOW\n");
69. return;
70. }
71. if(front == -1 && rear == -1)
72. {
73. front = 0;
74. rear = 0;
75. }
76. else
77. {
78. rear = rear+1;
79. }
80. queue[rear] = item;
81. printf("\nValue inserted ");
82.
83. }
84. void delete()
85. {
86. int item;
87. if (front == -1 || front > rear)
88. {
89. printf("\nUNDERFLOW\n");
90. return;
91.
92. }
93. else
94. {
95. item = queue[front];
96. if(front == rear)
97. {
98. front = -1;
99. rear = -1 ;
100. }
101. else
102. {
103. front = front + 1;
104. }
105. printf("\nvalue deleted is %d",item);
 106. }
107.
108.
109. }
110.
111. void display()
112. {
113. int i;
114. if(rear == -1)
115. {
116. printf("\nEmpty queue\n");
117. }
118. else
119. { printf("\nprinting values .....\n");
120. for(i=front;i<=rear;i++)
121. {
122. printf("\n%d\n",queue[i]);
123. }
124. }
125. }

Output:

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element

123

Value inserted

*************Main Menu**************
==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element

90

Value inserted

*************Main Menu**************

===================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?2

value deleted

*************Main Menu**************
==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

printing values .....

90
*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?4

Using Linked List:
 In a linked queue, each node of the queue consists of two parts i.e.
data part and the next part. Each element of the queue points to its
immediate next element in the memory.
 In the linked queue, there are two pointers
maintained in the memory i.e. front
pointer and rear
pointer. The front pointer
contains the address of the
starting element of the queue
while the rear pointer contains
the address of the last element
of the queue.
 
 Insertion and deletions are performed at rear and
front end respectively. If front and rear both are
NULL, it indicates that the queue is empty. Initially

struct node *front = NULL,

*rear = NULL;
Operation on Linked Queue: There are two basic operations
which can be implemented on the linked queues. The
operations are Enqueue and Dequeue.

Enqueue function: Enqueue function will add the element at

the end of the linked list.

1. Declare a new node and allocate memory for it.

2. If
front == NULL, make both front and rear points //to
the new node.
 Otherwise, add the new node in rear->next as
newnode (end of the list) i.e

rear->next=newnode.

and make the new node as the rear node. i.e.

rear = new node

Dequeue function: Dequeue function will remove the first

element from the queue.

1. Check whether the queue is empty or not

2. If it is the empty queue (front == NULL),

We can't dequeue the element. 3.Otherwise,

Make the front node points to the next node.

i.e front = front->next;

if front pointer becomes NULL, set

the rear pointer also NULL. Free

the front node's memory.

Example: Enqueue()

Dequeue()

TYPES OF QUEUES:
A queue data structure can be classified into the following
types:
1. Circular Queue 2. Deque 3. Priority Queue 4. Multiple Queue
 1.CIRCULAR QUEUE:
In a Linear queue, once the queue is completely full, it's not possible
to insert any more elements. When we dequeue any element to
remove it from the queue, we are actually moving the front of the
queue forward, but rear is still pointing to the last element of the
queue, we cannot insert new elements.
Circular Queue is also a linear data structure, which follows the
principle of FIFO (First In First Out), but instead of ending the
queue at the last position, it again starts from the first position
after the last, hence making the queue behave like a circular

data structure.

Operations on Circular Queue: The following are the

operations that can be performed
o enQueue(value): This function is used to insert
the new value in the Queue. The new element is
always inserted from the rear end.
o deQueue(): This function deletes an element from
the Queue. The deletion in a Queue always takes
place from the front end.
DEQUE:
Deque or
Double Ended
Queue is a
type of queue
 in which
insertion and
removal of
elements can
be performed
from either
from the front
or rear. Thus,
it does not
follow FIFO
rule (First In
First Out).

Types of Deque:
1. Input Restricted Deque: In this deque, input is
restricted at a single end but allows deletion at both the
ends.
2. Output Restricted Deque: In this deque, output is

restricted at a single end but allows insertion at both

the ends.

3. Priority Queue:-
 A priority queue is a data structure in which each
 element is assigned a priority. The priority of the
element will be used to determine the order in
which the elements will be processed.
 The general rules of processing the elements of a
priority queue are
o An element with higher priority is processed before an
element with a lower priority.
o Two elements with the same priority are
processed on a first-come-first-served (FCFS)
basis.

We are given with the data and the priority as an integer value and the
task is to

create a linked list as per the priority given and display the result.

Queue is a FIFO data structure in which the element which is inserted

first is the first one to get removed. A Priority Queue is a type of
queue in which elements can be inserted or deleted depending upon
the priority. It can be implemented using queue, stack or linked list
data structure. Priority queue is implemented by following these rules
−

 Data or element with the highest priority will get executed

before the data or element with the lowest priority.
 If two elements have the same priority than they will be
executed in the sequence they are added in the list.

A node of a linked list for implementing priority queue will contain

three parts −

 Data − It will store the integer value.

  Address − It will store the address of a next node
 Priority −It will store the priority which is an integer value. It
can range from 0-10 where 0 represents the highest priority and
10 represents the lowest priority.

Example

Input

Output

#include <stdio.h>
#include <stdlib.h>
// priority Node
typedef struct node {
int data;
int priority;
struct node* next;
} Node;
Node* newNode(int d, int p) {

Node* temp = (Node*)malloc(sizeof(Node));

temp->data = d;
temp->priority = p;
temp->next = NULL;
return temp;
}
int peek(Node** head) {
return (*head)->data;
}
void pop(Node** head) {
Node* temp = *head;
(*head) = (*head)->next;
free(temp);
}
void push(Node** head, int d, int p) {
Node* start = (*head);
Node* temp = newNode(d, p);
if ((*head)->priority > p) {
temp->next = *head;
(*head) = temp;
} else {
while (start->next != NULL &&
start->next->priority < p) {
start = start->next;
}
// Either at the ends of the list
// or at required position
temp->next = start->next;
start->next = temp;
}
}
// Function to check the queue is empty
int isEmpty(Node** head) {
return (*head) == NULL;
}
// main function
int main() {
Node* pq = newNode(7, 1);
push(&pq, 1, 2);
push(&pq, 3, 3);
push(&pq, 2, 0);
while (!isEmpty(&pq)) {
 printf("%d ", peek(&pq));
pop(&pq);
}
return 0;
}

Output

2713

Arrays:

 Finding the point of insertion/deletion O(1)

 Performing the insertion/deletion O(n)

Linked Lists:

 Finding the point of insertion/deletion O(n)

 Performing the insertion/deletion O(1)

I think the only time you wouldn't have to find the position is if you
kept some sort of pointer to it (as with the head and the tail in some
cases). So we can't flatly say that linked lists always beat arrays for
insert/delete options