UNIT-1

Introduction to Data Structures

What is Data Structure?
A data structure is a particular way of organizing data in a computer so that it can
be used effectively. The idea is to reduce the space and time complexities of
different tasks.
Need Of Data Structure:
The structure of the data and the synthesis of the algorithm are relative to each
other. Data presentation must be easy to understand so the developer, as well as
the user, can make an efficient implementation of the operation.
Data structures provide an easy way of organizing, retrieving, managing, and
storing data.
Here is a list of the needs for data.
 Data structure modification is easy.
 It requires less time.
 Save storage memory space.
 Data representation is easy.
 Easy access to the large database

Introduction to Data Structure and it's Characteristics

Introduction

Data Structure can be defined as the group of data elements which provides
an efficient way of storing and organising data in the computer so that it can
be used efficiently. Some examples of Data Structures are arrays, Linked List,
Stack, Queue, etc. Data Structures are widely used in almost every aspect of
Computer Science i.e. Operating System, Compiler Design, Artificial
intelligence, Graphics and many more.

Data Structures are the main part of many computer science algorithms as
they enable the programmers to handle the data in an efficient way. It plays
a vitle role in enhancing the performance of a software or a program as the
main function of the software is to store and retrieve the user’s data as fast
as possible

1|Pageskp
Basic Terminology
Data structures are the building blocks of any program or the software.
Choosing the appropriate data structure for a program is the most difficult
task for a programmer. Following terminology is used as far as data
structures are concerned

Data: Data can be defined as an elementary value or the collection of values,

for example, student’s name and its id are the data about the student.

Group Items: Data items which have subordinate data items are called
Group item, for example, name of a student can have first name and the last
name.

Record: Record can be defined as the collection of various data items, for
example, if we talk about the student entity, then its name, address, course
and marks can be grouped together to form the record for the student.

File: A File is a collection of various records of one type of entity, for

example, if there are 60 employees in the class, then there will be 20
records in the related file where each record contains the data about each
employee.

Attribute and Entity: An entity represents the class of certain objects. it

contains various attributes. Each attribute represents the particular property
of that entity.

Field: Field is a single elementary unit of information representing the

attribute of an entity.

2|Pageskp
Need of Data Structures
As applications are getting complexed and amount of data is increasing day
by day, there may arrise the following problems:

Processor speed: To handle very large amout of data, high speed processing
is required, but as the data is growing day by day to the billions of files per
entity, processor may fail to deal with that much amount of data.

Data Search: Consider an inventory size of 106 items in a store, If our

application needs to search for a particular item, it needs to traverse 106
items every time, results in slowing down the search process.

Multiple requests: If thousands of users are searching the data

simultaneously on a web server, then there are the chances that a very large
server can be failed during that process

in order to solve the above problems, data structures are used. Data is
organized to form a data structure in such a way that all items are not
required to be searched and required data can be searched instantly.

Advantages of Data Structures

Efficiency: Efficiency of a program depends upon the choice of data
structures. For example: suppose, we have some data and we need to
perform the search for a perticular record. In that case, if we organize our
data in an array, we will have to search sequentially element by element.
hence, using array may not be very efficient here. There are better data
structures which can make the search process efficient like ordered array,
binary search tree or hash tables.

3|Pageskp
Reusability: Data structures are reusable, i.e. once we have implemented a
particular data structure, we can use it at any other place. Implementation
of data structures can be compiled into libraries which can be used by
different clients.

Abstraction: Data structure is specified by the ADT which provides a level of

abstraction. The client program uses the data structure through interface
only, without getting into the implementation details.

Classification of Data Structures

A Data Structure delivers a structured set of variables related to each other in various ways. It
forms the basis of a programming tool that signifies the relationship between the data
elements and allows programmers to process the data efficiently.

We can classify Data Structures into two categories:

1. Primitive Data Structure

2. Non-Primitive Data Structure

The following figure shows the different classifications of Data Structures.

4|Pageskp
 1. Primitive Data Structures are the data structures consisting of the numbers and the characters
that come in-built into programs.
2. These data structures can be manipulated or operated directly by machine-level instructions.
3. Basic data types like Integer, Float, Character, and Boolean come under the Primitive Data
Structures.
4. These data types are also called Simple data types, as they contain characters that can't be
divided further

Non-Primitive Data Structures

1. Non-Primitive Data Structures are those data structures derived from Primitive Data Structures.
2. These data structures can't be manipulated or operated directly by machine-level instructions.
3. The focus of these data structures is on forming a set of data elements that is
either homogeneous (same data type) or heterogeneous (different data types).
4. Based on the structure and arrangement of data, we can divide these data structures into two
sub-categories -

a. Linear Data Structures

b. Non-Linear Data Structures

Linear Data Structures: A data structure is called linear if all of its elements
are arranged in the linear order. In linear data structures, the elements are
stored in non-hierarchical way where each element has the successors and
predecessors except the first and last element.

Types of Linear Data Structures are given below:

Arrays: An array is a collection of similar type of data items and each data
item is called an element of the array. The data type of the element may be
any valid data type like char, int, float or double.

The elements of array share the same variable name but each one carries a
different index number known as subscript. The array can be one
dimensional, two dimensional or multidimensional.

The individual elements of the array age are:

5|Pageskp
age[0], age[1], age[2], age[3],……… age[98], age[99].

Linked List: Linked list is a linear data structure which is used to maintain a
list in the memory. It can be seen as the collection of nodes stored at non-
contiguous memory locations. Each node of the list contains a pointer to its
adjacent node.

Stack: Stack is a linear list in which insertion and deletions are allowed only
at one end, called top.

A stack is an abstract data type (ADT), can be implemented in most of the

programming languages. It is named as stack because it behaves like a real-
world stack, for example: – piles of plates or deck of cards etc.

Queue: Queue is a linear list in which elements can be inserted only at one
end called rear and deleted only at the other end called front.

It is an abstract data structure, similar to stack. Queue is opened at both end

therefore it follows First-In-First-Out (FIFO) methodology for storing the data
items.

Non Linear Data Structures: This data structure does not form a sequence
i.e. each item or element is connected with two or more other items in a
non-linear arrangement. The data elements are not arranged in sequential
structure.

Types of Non Linear Data Structures are given below:

Trees: Trees are multilevel data structures with a hierarchical relationship

among its elements known as nodes. The bottommost nodes in the
hierarchy are called leaf node while the topmost node is called root node.
Each node contains pointers to point adjacent nodes.

6|Pageskp
Tree data structure is based on the parent-child relationship among the
nodes. Each node in the tree can have more than one children except the
leaf nodes whereas each node can have atmost one parent except the root
node.

Graphs: Graphs can be defined as the pictorial representation of the set of

elements (represented by vertices) connected by the links known as edges.
A graph is different from tree in the sense that a graph can have cycle while
the tree cannot have the one.

Hash table -A hash table is a data structure that is used to store keys/value
pairs. It uses a hash function to compute an index into an array in which an
element will be inserted or searched.

Operations on data structure

1) Traversing: Every data structure contains the set of data elements.

Traversing the data structure means visiting each element of the data
structure in order to perform some specific operation like searching or
sorting.

Example: If we need to calculate the average of the marks obtained by a

student in 6 different subject, we need to traverse the complete array of
marks and calculate the total sum, then we will devide that sum by the
number of subjects i.e. 6, in order to find the average.

2) Insertion: Insertion can be defined as the process of adding the elements

to the data structure at any location.

If the size of data structure is n then we can only insert n-1 data elements
into it.

7|Pageskp
 3) Deletion: The process of removing an element from the data structure is
called Deletion. We can delete an element from the data structure at any
random location.

If we try to delete an element from an empty data structure

then underflow occurs.

4) Searching: The process of finding the location of an element within the

data structure is called Searching. There are two algorithms to perform
searching, Linear Search and Binary Search.

5) Sorting: The process of arranging the data structure in a specific order is

known as Sorting. There are many algorithms that can be used to perform
sorting, for example, insertion sort, selection sort, bubble sort, etc.

6) Merging: When two lists List A and List B of size M and N respectively, of
similar type of elements, clubbed or joined to produce the third list, List C of
size (M+N), then this process is called merging

Array
Definition
 Arrays are defined as the collection of similar type of data items stored at
contiguous memory locations.
 Arrays are the derived data type in C programming language which can store
the primitive type of data such as int, char, double, float, etc.
 Array is the simplest data structure where each data element can be
randomly accessed by using its index number.

8|Pageskp
 For example, if we want to store the marks of a student in 6 subjects, then
we don’t need to define different variable for the marks in different subject.
instead of that, we can define an array which can store the marks in each
subject at a the contiguous memory locations.

The array marks[10] defines the marks of the student in 10 different

subjects where each subject marks are located at a particular subscript in
the array i.e. marks[0] denotes the marks in first subject, marks[1] denotes
the marks in 2nd subject and so on.

Properties of the Array

1. Each element is of same data type and carries a same size i.e. int = 4 bytes.
2. Elements of the array are stored at contiguous memory locations where the
first element is stored at the smallest memory location.
3. Elements of the array can be randomly accessed since we can calculate the
address of each element of the array with the given base address and the
size of data element.

for example, in C language, the syntax of declaring an array is like following:

1. int arr[10]; char arr[10]; float arr[5]

Need of using Array

In computer programming, the most of the cases requires to store the large
number of data of similar type. To store such amount of data, we need to
define a large number of variables. It would be very difficult to remember
names of all the variables while writing the programs. Instead of naming all
the variables with a different name, it is better to define an array and store
all the elements into it.

9|Pageskp
 Following example illustrates, how array can be useful in writing code for a
particular problem.

In the following example, we have marks of a student in six different

subjects. The problem intends to calculate the average of all the marks of
the student.

In order to illustrate the importance of array, we have created two

programs, one is without using array and other involves the use of array to
store marks.

Program without array:

1. #include <stdio.h>
2. void main ()
3. {
4. int marks_1 = 56, marks_2 = 78, marks_3 = 88, marks_4 = 76, marks_5 = 5
6, marks_6 = 89;
5. float avg = (marks_1 + marks_2 + marks_3 + marks_4 + marks_5 +marks_6
)/6;
6. printf(avg);
7. }

Program by using array:

1. #include <stdio.h>
2. void main ()
3. {
4. int marks[6] = {56,78,88,76,56,89);
5. int i;
6. float avg;
7. for (i=0; i<6; i++ )
8. {
9. avg = avg + marks[i];

10 | P a g e s k p
10. }
11. printf(avg);
12. }

Advantages of Array
 Array provides the single name for the group of variables of the same type
therefore, it is easy to remember the name of all the elements of an array.
 Traversing an array is a very simple process, we just need to increment the
base address of the array in order to visit each element one by one.
 Any element in the array can be directly accessed by using the index.

Memory Allocation of the array

As we have mentioned, all the data elements of an array are stored at
contiguous locations in the main memory. The name of the array represents
the base address or the address of first element in the main memory. Each
element of the array is represented by a proper indexing.

The indexing of the array can be defined in three ways.

1. 0 (zero – based indexing) : The first element of the array will be arr[0].
2. 1 (one – based indexing) : The first element of the array will be arr[1].
3. n (n – based indexing) : The first element of the array can reside at any
random index number.

In the following image, we have shown the memory allocation of an array

arr of size 5. The array follows 0-based indexing approach. The base address
of the array is 100th byte. This will be the address of arr[0]. Here, the size of
int is 4 bytes therefore each element will take 4 bytes in the memory.

11 | P a g e s k p
 In 0 based indexing, If the size of an array is n then the maximum index
number, an element can have is n-1. However, it will be n if we use 1 based
indexing.

Accessing Elements of an array

To access any random element of an array we need the following
information:

1. Base Address of the array.

2. Size of an element in bytes.
3. Which type of indexing, array follows.

Address of any element of a 1D array can be calculated by using the

following formula:

1. Byte address of element A[i] = base address + size * ( i – first index)

Example :

12 | P a g e s k p
1. In an array, A[-10 ….. +2 ], Base address (BA) = 999, size of an element = 2 by
tes,
2. find the location of A[-1].
3. L(A[-1]) = 999 + [(-1) – (-10)] x 2
4. = 999 + 18
5. = 1017

C program to insert an element in

an array
#include <stdio.h>

int main()
{
int array[100], position, c, n, value;
printf("Enter number of elements in array\n");
scanf("%d", &n);

printf("Enter %d elements\n", n);

for (c = 0; c < n; c++)

scanf("%d", &array[c]);

printf("Enter the location where you wish to insert an

element\n");
scanf("%d", &position);

printf("Enter the value to insert\n");

scanf("%d", &value);

for (c = n - 1; c >= position - 1; c--)

array[c+1] = array[c];

array[position-1] = value;

printf("Resultant array is\n");

for (c = 0; c <= n; c++)

printf("%d\n", array[c]);

return 0;
}

13 | P a g e s k p
C Program to delete an element from array at given position

#include <stdio.h>

void main()
{
int arr[50], size, pos, i;

printf("Enter number of elements: ");

scanf("%d", &size);

printf("Enter array elements-\n");

for (i = 0; i < size; i++)
scanf("%d", &arr[i]);

printf("\nEnter postion to delete: ");

scanf("%d", &pos);

for(i = pos-1; i < size-1; i++)

arr[i] = arr[i + 1];
size--;

printf("Array after deletion-\n");

for (i = 0; i < size; i++)
printf("%d ", arr[i]);
}

2D Array
2D array can be defined as an array of arrays. The 2D array is organized as
matrices which can be represented as the collection of rows and columns.

However, 2D arrays are created to implement a relational database look

alike data structure. It provides ease of holding bulk of data at once which
can be passed to any number of functions wherever required.

14 | P a g e s k p
 How to declare 2D Array
The syntax of declaring two dimensional array is very much similar to that of
a one dimensional array, given as follows.

1. int arr[max_rows][max_columns];

however, It produces the data structure which looks like following.

Above image shows the two dimensional array, the elements are organized
in the form of rows and columns. First element of the first row is
represented by a[0][0] where the number shown in the first index is the
number of that row while the number shown in the second index is the
number of the column.

15 | P a g e s k p
 How do we access data in a 2D array
Due to the fact that the elements of 2D arrays can be random accessed.
Similar to one dimensional arrays, we can access the individual cells in a 2D
array by using the indices of the cells. There are two indices attached to a
particular cell, one is its row number while the other is its column number.

However, we can store the value stored in any particular cell of a 2D array to
some variable x by using the following syntax.

1. int x = a[i][j];

where i and j is the row and column number of the cell respectively.

We can assign each cell of a 2D array to 0 by using the following code:

1. for ( int i=0; i<n ;i++)

2. {
3. for (int j=0; j<n; j++)
4. {
5. a[i][j] = 0;
6. }
7. }

Initializing 2D Arrays
We know that, when we declare and initialize one dimensional array in C
programming simultaneously, we don’t need to specify the size of the array.
However this will not work with 2D arrays. We will have to define at least
the second dimension of the array.

16 | P a g e s k p
 The syntax to declare and initialize the 2D array is given as follows.

1. int arr[2][2] = {0,1,2,3};

The number of elements that can be present in a 2D array will always be

equal to (number of rows * number of columns).

Example : Storing User’s data into a 2D array and printing it.

C Example :

1. #include <stdio.h>
2. void main ()
3. {
4. int arr[3][3],i,j;
5. for (i=0;i<3;i++)
6. {
7. for (j=0;j<3;j++)
8. {
9. printf(“Enter a[%d][%d]: “,i,j);
10. scanf(“%d”,&arr[i][j]);
11. }
12. }
13. printf(“\n printing the elements ….\n”);
14. for(i=0;i<3;i++)
15. {
16. printf(“\n”);
17. for (j=0;j<3;j++)
18. {
19. printf(“%d\t”,arr[i][j]);
20. }
21. }
22. }

17 | P a g e s k p
 Sparse matrix
A sparse matrix is a one in which the majority of the values are zero. The
proportion of zero elements to non-zero elements is referred to as
the sparsity of the matrix. The opposite of a sparse matrix, in which the
majority of its values are non-zero, is called a dense matrix.

Sparse matrix example

Here is an example of a 4 x 4 matrix containing 12 zero values and 4 non-
zero values, giving it a sparsity of 3:
[[5, 0, 0, 0],
[0, 11, 0, 0],
[0, 0, 25, 0],
[0, 0, 0, 7]]
Representing a sparse matrix by a 2D array leads to wastage of lots of
memory as zeroes in the matrix are of no use in most of the cases. So,
instead of storing zeroes with non-zero elements, we only store non-zero
elements. This means storing non-zero elements with triples- (Row,
Column, value).
Sparse Matrix Representations can be done in many ways following are two
common representations:

1. Array representation
2. Linked list representation
Method 1: Using Arrays
2D array is used to represent a sparse matrix in which there are three rows
named as

 Row: Index of row, where non-zero element is located

 Column: Index of column, where non-zero element is located
 Value: Value of the non-zero element located at index – (row, column)

18 | P a g e s k p
 Method 2: Using Linked Lists
In linked list, each node has four fields. These four fields are defined as:

 Row: Index of row, where non-zero element is located

 Column: Index of column, where non-zero element is located
 Value: Value of the non-zero element located at index – (row, column)
 Next node: Address of the next node

• Upper and Lower Triangular Matrices:

– Definition: An upper triangular matrix is a square matrix in which all
entries below the main diagonal are zero (only nonzero entries are found
above the main diagonal – in the upper triangle).

A lower triangular matrix is a square matrix in which all entries above the
main diagonal are zero (only nonzero entries are found below the main
diagonal – in the lower triangle).
– Notation: An upper triangular matrix is typically denoted with U and a
19 | P a g e s k p
lower triangular matrix is typically denoted with L.

Triangular Matrix
A matrix is defined as a rectangular array of numbers that are arranged in rows
and columns. The size of a matrix can be determined by the number of rows and
columns in it. A matrix is said to be an “m by n” matrix when it has “m” rows and
“n” columns and is written as an “m × n” matrix. For example, a matrix of order
“5 × 6” has five rows and six columns. We have different types of matrices, such
as rectangular, square, triangular, symmetric, singular, etc.
What is a Triangular Matrix?
A triangular matrix is a special case of a square matrix, where all elements above
or below the principal diagonal are zeros. An upper triangular matrix is a square
matrix, whose all elements below the principal diagonal are zeros. A lower
triangular matrix is a square matrix, whose all elements above the principal
diagonal are zeros. The matrices in the image given below are upper triangular
and lower triangular matrices of order “4 × 4.”

Types of Triangular Matrices

There are different types of matrices which are discussed below in this article:
 Upper Triangular Matrix: An upper triangular matrix is a square matrix, whose
all elements below the principal diagonal are zeros.

20 | P a g e s k p
 Lower Triangular Matrix: A lower triangular matrix is a square matrix, whose all
elements above the principal diagonal are zeros.

Properties of a Triangular Matrix

Various properties of the Triangular Matrix are discussed below in this article:
 The transpose of an upper triangular matrix is a lower triangular matrix, i.e.,
UT = L, and the transpose of a lower triangular matrix is an upper triangular
matrix, i.e., LT = U.
 The determinant of a triangular matrix of any order is equal to the product of
the principal diagonal elements.
 The inverse of a triangular matrix will also be a triangular matrix.
 A triangular matrix is invertible if and only if all elements of the principal
diagonal are non-zero.
 When two triangular matrices are multiplied, the resultant matrix is also
triangular.
 When two upper (lower) triangular matrices are multiplied, the resultant matrix
is also an upper (lower) triangular matrix.
 When two upper (lower) triangular matrices are added, the resultant matrix is
also an upper (lower) triangular matrix.

Mapping 2D array to 1D array

When it comes to map a 2 dimensional array, most of us might think that why this
mapping is required. However, 2 D arrays exists from the user point of view. 2D
arrays are created to implement a relational database table lookalike data
structure, in computer memory, the storage technique for 2D array is similar to
that of an one dimensional array.
The size of a two dimensional array is equal to the multiplication of number of
rows and the number of columns present in the array. We do need to map two

21 | P a g e s k p
dimensional array to the one dimensional array in order to store them in the
memory.
A 3 X 3 two dimensional array is shown in the following image. However, this
array needs to be mapped to a one dimensional array in order to store it into the
memory.

There are two main techniques of storing 2D array elements into memory
1. Row Major ordering
In row major ordering, all the rows of the 2D array are stored into the memory
contiguously. Considering the array shown in the above image, its memory
allocation according to row major order is shown as follows.

first, the 1st row of the array is stored into the memory completely, then the
2nd row of the array is stored into the memory completely and so on till the last
row.

22 | P a g e s k p
2. Column Major ordering
According to the column major ordering, all the columns of the 2D array are
stored into the memory contiguously. The memory allocation of the array which is
shown in in the above image is given as follows.

first, the 1st column of the array is stored into the memory completely, then the
2nd column of the array is stored into the memory completely and so on till the
last column of the array.

Calculate the address of any element in the 2-D array:

The 2-dimensional array can be defined as an array of arrays. The 2-Dimensional
arrays are organized as matrices which can be represented as the collection of

23 | P a g e s k p
rows and columns as array[M][N] where M is the number of rows and N is the
number of columns.
Example:

2-D array

To find the address of any element in a 2-Dimensional array there are the
following two ways-
1. Row Major Order
2. Column Major Order
1. Row Major Order:
Row major ordering assigns successive elements, moving across the rows and
then down the next row, to successive memory locations. In simple language, the
elements of an array are stored in a Row-Wise fashion.
To find the address of the element using row-major order uses the following
formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in an array(in byte),
LR = Lower Limit of row/start row index of the matrix(If not given assume it as
zero),
LC = Lower Limit of column/start column index of the matrix(If not given assume it
as zero),
N = Number of column given in the matrix.

24 | P a g e s k p
Example: Given an array, arr[1………10][1………15] with base value 100 and the
size of each element is 1 Byte in memory. Find the address of arr[8][6] with the
help of row-major order.
Solution:
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of column given in the matrix N = Upper Bound – Lower Bound + 1
= 15 – 1 + 1
= 15
Formula:
Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))
Solution:
Address of A[8][6] = 100 + 1 * ((8 – 1) * 15 + (6 – 1))
= 100 + 1 * ((7) * 15 + (5))
= 100 + 1 * (110)
Address of A[I][J] = 210
2. Column Major Order:
If elements of an array are stored in a column-major fashion means moving across
the column and then to the next column then it’s in column-major order. To find
the address of the element using column-major order use the following formula:
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LR = Lower Limit of row/start row index of matrix(If not given assume it as zero),
LC = Lower Limit of column/start column index of matrix(If not given assume it as
zero),
M = Number of rows given in the matrix.
Example: Given an array arr[1………10][1………15] with a base value of 100 and the
size of each element is 1 Byte in memory find the address of arr[8][6] with the
help of column-major order.

25 | P a g e s k p
Solution:
Given:
Base address B = 100
Storage size of one element store in any array W = 1 Bytes
Row Subset of an element whose address to be found I = 8
Column Subset of an element whose address to be found J = 6
Lower Limit of row/start row index of matrix LR = 1
Lower Limit of column/start column index of matrix = 1
Number of Rows given in the matrix M = Upper Bound – Lower Bound + 1
= 10 – 1 + 1
= 10
Formula: used
Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))
Address of A[8][6] = 100 + 1 * ((6 – 1) * 10 + (8 – 1))
= 100 + 1 * ((5) * 10 + (7))
= 100 + 1 * (57)
Address of A[I][J] = 157

Tri-diagonal matrices
In linear algebra, a tridiagonal matrix is a band matrix that has nonzero elements
only on the main diagonal, the subdiagonal/lower diagonal (the first diagonal
below this), and the supradiagonal/upper diagonal (the first diagonal above the
main diagonal). For example, the following matrix is tridiagonal:

OR
What Is a Tridiagonal Matrix?
A tridiagonal matrix is a square matrix whose elements are zero away from the
main diagonal, the subdiagonal, and the superdiagonal. In other words, it is a
banded matrix with upper and lower bandwidths both equal to . It has the form

26 | P a g e s k p
An important example is the matrix that arises in discretizating the Poisson
partial differential equation by a standard five-point operator, illustrated for
by

It is symmetric positive definite, diagonally dominant, a Toeplitz matrix, and an

-matrix.
Tridiagonal matrices have many special properties and various algorithms exist
that exploit their structure.
Tri-diagonal matrices are commonly used in numerical analysis, linear
algebra, and data structures because they:

1. Reduce memory usage by storing only non-zero elements

2. Speed up computations, such as matrix-vector multiplication and solving
systems of linear equations
3. Are often used in algorithms like Gaussian elimination, LU decomposition, and
eigenvalue decomposition

27 | P a g e s k p
A tri-diagonal matrix can be represented as a vector of three
arrays:

The vector representation of a tri-diagonal matrix can be stored in a single vector

v of length 3n-2, where n is the number of rows (or columns) in the matrix. The
elements of the vector are stored in the following order:

v = [d1, a1, b1, d2, a2, b2, ..., dn, an, bn]

Where:

- di represents the i-th element of the main diagonal

- ai represents the i-th element of the sub-diagonal (below the main diagonal)
- bi represents the i-th element of the super-diagonal (above the main diagonal)

For example, consider the following 4x4 tri-diagonal matrix:

[1, 2, 0, 0]
[3, 4, 5, 0]
[0, 6, 7, 8]
[0, 0, 9, 10]

The vector representation would be:

v = [1, 3, 2, 4, 6, 5, 7, 9, 8, 10]

This representation allows for efficient storage and computation, especially when
working with large sparse matrices.
This representation is useful for:

28 | P a g e s k p
- Efficient storage (only non-zero elements are stored)
- Faster computations (e.g., matrix-vector multiplication)
- Simplified implementation of algorithms (e.g., Thomas algorithm for solving
tridiagonal systems)

29 | P a g e s k p