Data Structure is a way to store and organize data so that it can be used efficiently.

Our Data Structure tutorial includes all topics of Data Structure such as Array, Pointer,
Structure, Linked List, Stack, Queue, Graph, Searching, Sorting, Programs, etc.

What is Data Structure?

The data structure name indicates itself that organizing the data in memory. There are many
ways of organizing the data in the memory as we have already seen one of the data structures,
i.e., array in C language. Array is a collection of memory elements in which data is stored
sequentially, i.e., one after another. In other words, we can say that array stores the elements
in a continuous manner. This organization of data is done with the help of an array of data
structures. There are also other ways to organize the data in memory. Let's see the different
types of data structures.

The data structure is not any programming language like C, C++, java, etc. It is a set of
algorithms that we can use in any programming language to structure the data in the memory.

To structure the data in memory, 'n' number of algorithms were proposed, and all these
algorithms are known as Abstract data types. These abstract data types are the set of rules.

Types of Data Structures

There are two types of data structures:

o Primitive data structure

o Non-primitive data structure

Primitive Data structure

The primitive data structures are primitive data types. The int, char, float, double, and pointer
are the primitive data structures that can hold a single value.

Non-Primitive Data structure

The non-primitive data structure is divided into two types:

o Linear data structure

o Non-linear data structure

Linear Data Structure

The arrangement of data in a sequential manner is known as a linear data structure. The data
structures used for this purpose are Arrays, Linked list, Stacks, and Queues. In these data
structures, one element is connected to only one another element in a linear form.

When one element is connected to the 'n' number of elements known as a non-linear
data structure. The best example is trees and graphs. In this case, the elements are
arranged in a random manner.

We will discuss the above data structures in brief in the coming topics. Now, we will see the
common operations that we can perform on these data structures.

Data structures can also be classified as:

o Static data structure: It is a type of data structure where the size is allocated at the
compile time. Therefore, the maximum size is fixed.
o Dynamic data structure: It is a type of data structure where the size is allocated at
the run time. Therefore, the maximum size is flexible.

Major Operations

The major or the common operations that can be performed on the data structures are:

o Searching: We can search for any element in a data structure.

o Sorting: We can sort the elements of a data structure either in an ascending or
descending order.
o Insertion: We can also insert the new element in a data structure.
o Updation: We can also update the element, i.e., we can replace the element with
another element.
o Deletion: We can also perform the delete operation to remove the element from the
data structure.

Which Data Structure?

A data structure is a way of organizing the data so that it can be used efficiently. Here, we
have used the word efficiently, which in terms of both the space and time. For example, a
stack is an ADT (Abstract data type) which uses either arrays or linked list data structure for
the implementation. Therefore, we conclude that we require some data structure to implement
a particular ADT.

An ADT tells what is to be done and data structure tells how it is to be done. In other words,
we can say that ADT gives us the blueprint while data structure provides the implementation
part. Now the question arises: how can one get to know which data structure to be used for a
particular ADT?.

As the different data structures can be implemented in a particular ADT, but the different
implementations are compared for time and space. For example, the Stack ADT can be
implemented by both Arrays and linked list. Suppose the array is providing time efficiency
while the linked list is providing space efficiency, so the one which is the best suited for the
current user's requirements will be selected.
Advantages of Data structures

The following are the advantages of a data structure:

o Efficiency: If the choice of a data structure for implementing a particular ADT is

proper, it makes the program very efficient in terms of time and space.
o Reusability: The data structure provides reusability means that multiple client
programs can use the data structure.
o Abstraction: The data structure specified by an ADT also provides the level of
abstraction. The client cannot see the internal working of the data structure, so it does
not have to worry about the implementation part. The client can only see the interface.

Linear Data Structures- Linear data structures are organized in a particular order, and it is
done so because the elements are ordered in a particular pattern; they are simple to
implement. Nevertheless, linear data structures might not be the best choice for sophisticated
systems because of their operational complexity.

Characteristics of Linear Data Structure:

 Sequential Organization: In linear data structures, data elements are arranged
sequentially, one after the other. Each element has a unique predecessor (except for the
first element) and a unique successor (except for the last element)
 Order Preservation: The order in which elements are added to the data structure is
preserved. This means that the first element added will be the first one to be accessed or
removed, and the last element added will be the last one to be accessed or removed.
 Fixed or Dynamic Size: Linear data structures can have either fixed or dynamic sizes.
Arrays typically have a fixed size when they are created, while other structures like
linked lists, stacks, and queues can dynamically grow or shrink as elements are added or
removed.
 Efficient Access: Accessing elements within a linear data structure is typically
efficient. For example, arrays offer constant-time access to elements using their index.
Linear data structures are commonly used for organising and manipulating data in a
sequential fashion. Some of the most common linear data structures include:
 Arrays: A collection of elements stored in contiguous memory locations.
 Linked Lists: A collection of nodes, each containing an element and a reference to the
next node.
 Stacks: A collection of elements with Last-In-First-Out (LIFO) order.
 Queues: A collection of elements with First-In-First-Out (FIFO) order.

1. Array
An array is a collection of items of same data type stored at contiguous memory locations.
Arrays in data structures help solve some high-level problems like the "longest consecutive
subsequence" program or some easy tasks like arranging the same things in ascending
order. The concept is to collect many objects of the same kind.

Array

Why Do You Need an Array in Data Structures?

Let's suppose a class consists of ten students, and the class has to publish their results. If
you had declared all ten variables individually, it would be challenging to manipulate and
maintain the data.

If more students were to join, it would become more difficult to declare all the variables
and keep track of it. To overcome this problem, arrays came into the picture.

Characteristics of Array Data Structure:

 Homogeneous Elements: All elements within an array must be of the same data type.
 Contiguous Memory Allocation: In most programming languages, elements in an
array are stored in contiguous (adjacent) memory locations.
 Zero-Based Indexing: In many programming languages, arrays use zero-based
indexing, which means that the first element is accessed with an index of 0, the second
with an index of 1, and so on.
 Random Access: Arrays provide constant-time (O(1)) access to elements. This means
that regardless of the size of the array, it takes the same amount of time to access any
element based on its index.
Types of arrays:
 One-Dimensional Array: This is the simplest form of an array, which consists of a
single row of elements, all of the same data type. Elements in a 1D array are accessed
using a single index.

One-Dimensional Array

 Two-Dimensional Array: A two-dimensional array, often referred to as a matrix or 2D

array, is an array of arrays. It consists of rows and columns, forming a grid-like
structure. Elements in a 2D array are accessed using two indices, one for the row and
one for the column.

Two-Dimensional Array:

 Multi-Dimensional Array: Arrays can have more than two dimensions, leading to
multi-dimensional arrays. These are used when data needs to be organized in a multi-
dimensional grid.
 Multi-Dimensional Array

Types of Array operations:

 Accessing Elements: Accessing a specific element in an array by its index is a
constant-time operation. It has a time complexity of O(1).
 Insertion: Appending an element to the end of an array is usually a constant-time
operation, O(1) but insertion at the beginning or any specific index takes O(n) time
because it requires shifting all of the elements.
 Deletion: Same as insertion, deleting the last element is a constant-time operation, O(1)
but deletion of element at the beginning or any specific index takes O(n) time because it
requires shifting all of the elements.
 Searching: Linear Search takes O(n) time which is useful for unsorted data and Binary
Search takes O(logn) time which is useful for sorted data.

How Do You Declare an Array?

Arrays are typically defined with square brackets with the size of the arrays as its argument.

Here is the syntax for arrays:

1D Arrays: int arr[n];

2D Arrays: int arr[m][n];

3D Arrays: int arr[m][n][o];

How Do You Initialize an Array?

You can initialize an array in four different ways:

 Method 1:

int a[6] = {2, 3, 5, 7, 11, 13};

 Method 2:

int arr[]= {2, 3, 5, 7, 11};

 Method 3:

int n;

scanf(“%d”,&n);

int arr[n];

for(int i=0;i<5;i++)

scanf(“%d”,&arr[i]);

 Method 4:

int arr[5];

arr[0]=1;

arr[1]=2;

arr[2]=3;

arr[3]=4;
arr[4]=5;

How Can You Access Elements of Arrays in Data Structures?

You can access elements with the help of the index at which you stored them. Let's discuss it
with a code:

#include<stdio.h>

int main()

int a[5] = {2, 3, 5, 7, 11};

printf(“%d\n”,a[0]); // we are accessing

printf(“%d\n”,a[1]);

printf(“%d\n”,a[2]);

printf(“%d\n”,a[3]);

printf(“%d”,a[4]);

return 0;

}
What Operations Can You Perform on an Array?

 Traversal

 Insertion

 Deletion

 Searching

 Sorting

Traversing the Array:

Traversal in an array is a process of visiting each element once.

Code:

#include<stdio.h>

int main()

int a[5] = {2, 3, 5, 7, 11};

for(int i=0;i<5;i++)

//traversing ith element in the array

printf(“%d\n”,a[i]);

return 0;
}

Insertion:

Insertion in an array is the process of including one or more elements in an array.

Insertion of an element can be done:

 At the beginning

 At the end and

 At any given index of an array.

At the Beginning:

Code:

#include<stdio.h>

int main()

{
int array[10], n,i, item;

printf("Enter the size of array: ");

scanf("%d", &n);

printf("\nEnter Elements in array: ");

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

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

printf("\n enter the element at the beginning");

scanf("%d", &item);

n++;

for(i=n; i>1; i--)

array[i-1]=array[i-2];

array[0]=item;

printf("resultant array element");

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

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

}
 getch();

return 0;

Algorithm

At the End:

Code:

#include<stdio.h>

#include<conio.h>

int main()

int array[10], i, values;

printf("Enter 5 Array Elements: ");

for(i=0; i<5; i++)

scanf("%d", &array[i]);
printf("\nEnter Element to Insert: ");

scanf("%d", &values);

array[i] = values;

printf("\nThe New Array is:\n");

for(i=0; i<6; i++)

printf("%d ", array[i]);

getch();

return 0;

At a Specific Position:

Code:

#include <stdio.h>

int main()

int array[100], pos, size, val;

printf("Enter size of the array:");

scanf("%d", &size);
printf("\nEnter %d elements\n", size);

for (int i = 0; i < size; i++)

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

printf("Enter the insertion location\n");

scanf("%d", &pos);

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

scanf("%d", &val);

for (int i = size - 1; i >= pos - 1; i--)

array[i+1] = array[i];

array[pos-1] = val;

printf("Resultant array is\n");

for (int i = 0; i <= size; i++)

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

return 0;

}
Deletion:

Deletion of an element is the process of removing the desired element and re-
organizing it.

You can also do deletion in different ways:

 At the beginning

 At the end

At the Beginning:

#include<stdio.h>
int main()

int n,array[10];

printf("enter the size of an array");

scanf("%d" ,&n);

printf("enter elements in an array");

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

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

n--;

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

array[i]=array[i+1];

printf("\nafter deletion ");

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

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

}
At the End:

#include<stdio.h>

int main()

int n,array[10];

printf("enter the size of an array");

scanf("%d" ,&n);

printf("enter elements in an array");

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

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

printf("\nafter deletion array elements are");

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

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

Array - Insertion Operation

In the insertion operation, we are adding one or more elements to

the array. Based on the requirement, a new element can be
added at the beginning, end, or any given index of array. This is
done using input statements of the programming languages.

Algorithm

Following is an algorithm to insert elements into a Linear Array

until we reach the end of the array −

1. Start
2. Create an Array of a desired datatype and size.
3. Initialize a variable 'i' as 0.
4. Enter the element at ith index of the array.
5. Increment i by 1.
6. Repeat Steps 4 & 5 until the end of the array.
7. Stop

Example

Here, we see a practical implementation of insertion operation,

where we add data at the end of the array −

C C++JavaPython

#include <stdio.h>
int main(){
int LA[3] = {}, i;
printf("Array Before Insertion:\n");
for(i = 0; i < 3; i++)
printf("LA[%d] = %d \n", i, LA[i]);
printf("Inserting Elements.. \n");
printf("The array elements after insertion :\n"); // prints array
values
for(i = 0; i < 3; i++) {
LA[i] = i + 2;
printf("LA[%d] = %d \n", i, LA[i]);
}
return 0;
}

Output
Array Before Insertion:
LA[0] = 0
LA[1] = 0
LA[2] = 0
Inserting elements..
Array After Insertion:
LA[0] = 2
LA[1] = 3
LA[2] = 4
LA[3] = 5
LA[4] = 6
For other variations of array insertion operation, click here.
Array - Deletion Operation

In this array operation, we delete an element from the particular

index of an array. This deletion operation takes place as we
assign the value in the consequent index to the current index.

Algorithm

Consider LA is a linear array with N elements and K is a positive

integer such that K<=N. Following is the algorithm to delete an
element available at the Kth position of LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop

Example

Following are the implementations of this operation in various

programming languages −

C C++JavaPython

#include <stdio.h>
void main(){
 int LA[] = {1,3,5};
int n = 3;
int i;
printf("The original array elements are :\n");
for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]);
for(i = 1; i<n; i++) {
LA[i] = LA[i+1];
n = n - 1;
}
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++)
printf("LA[%d] = %d \n", i, LA[i]);
}

Output

The original array elements are :

LA[0] = 1
LA[1] = 3
LA[2] = 5
The array elements after deletion :
LA[0] = 1
LA[1] = 5

Array - Search Operation

Searching an element in the array using a key; The key element

sequentially compares every value in the array to check if the key
is present in the array or not.

Algorithm

Consider LA is a linear array with N elements and K is a positive

integer such that K<=N. Following is the algorithm to find an
element with a value of ITEM using sequential search.

1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop

Example

Following are the implementations of this operation in various

programming languages −

C C++JavaPython

#include <stdio.h>
void main(){
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
for(i = 0; i<n; i++) {
if( LA[i] == item ) {
printf("Found element %d at position %d\n", item, i+1);
}
}
}

Output

The original array elements are :

LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3

Array - Traversal Operation

This operation traverses through all the elements of an array. We

use loop statements to carry this out.
Algorithm

Following is the algorithm to traverse through all the elements

present in a Linear Array −

1 Start
2. Initialize an Array of certain size and datatype.
3. Initialize another variable ‘i’ with 0.
4. Print the ith value in the array and increment i.
5. Repeat Step 4 until the end of the array is reached.
6. End

Example

Following are the implementations of this operation in various

programming languages −

C C++JavaPython

#include <stdio.h>
int main(){
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}

Output

The original array elements are :

LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Array - Update Operation

Update operation refers to updating an existing element from the

array at a given index.

Algorithm

Consider LA is a linear array with N elements and K is a positive

integer such that K<=N. Following is the algorithm to update an
element available at the Kth position of LA.

1. Start
2. Set LA[K-1] = ITEM
3. Stop

Example

Following are the implementations of this operation in various

programming languages −

C C++JavaPython

#include <stdio.h>
void main(){
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
LA[k-1] = item;
printf("The array elements after updation :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}

Output

The original array elements are :

LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8

Array - Display Operation

This operation displays all the elements in the entire array using a
print statement.

Algorithm

Consider LA is a linear array with N elements. Following is the

algorithm to display an array elements.

1. Start
2. Print all the elements in the Array
3. Stop

Example

Following are the implementations of this operation in various

programming languages −

C C++JavaPython

#include <stdio.h>
int main(){
int LA[] = {1,3,5,7,8};
int n = 5;
int i;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
 }
}

Output

The original array elements are :

LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8

Functional Programming-Records
Records are known as the data structure to store the fixed number of
elements. Records are similar, just like the structure in the C language. At
the compilation time, expressions of records can translate into the tuple
expression.

Creation of Record
The 'record' keyword is used to create the record with the name of the
record and its field.

The syntax of the record is shown as below:

1. record(recodname, {field1, field2, . . fieldn})

Syntax used to insert the value in the record is as shown below:

1. #recordname {fieldName1 = value1, fieldName2 = value2 .. fieldNamen

= valuen}

Stack Data Structure

A Stack is a linear data structure that follows the LIFO (Last-In-First-
Out) principle. Stack has one end, whereas the Queue has two ends (front and
rear). It contains only one pointer top pointer pointing to the topmost element
of the stack. Whenever an element is added in the stack, it is added on the top of
the stack, and the element can be deleted only from the stack. In other words,
a stack can be defined as a container in which insertion and deletion
can be done from the one end known as the top of the stack.

Think of a stack like a pile of pancakes.

In a pile of pancakes, the pancakes are both added and removed from the
top. So when removing a pancake, it will always be the last pancake you
added. This way of organizing elements is called LIFO: Last In First Out.

Basic operations we can do on a stack are:

 Push: Adds a new element on the stack.

 Pop: Removes and returns the top element from the stack.
 Peek: Returns the top element on the stack.
 isEmpty: Checks if the stack is empty.
 Size: Finds the number of elements in the stack.

Experiment with these basic operations in the stack animation above.

Stacks can be implemented by using arrays or linked lists.

Stacks can be used to implement undo mechanisms, to revert to previous

states, to create algorithms for depth-first search in graphs, or for
backtracking.

Stacks are often mentioned together with Queues, which is a similar data
structure described on the next page.

Stack Implementation using Arrays

This is how it looks like when we use an array as a stack:

[
4,

1,

3,

Result:

push()pop()peek()isEmpty()size()

Reasons to implement stacks using arrays:

 Memory Efficient: Array elements do not hold the next elements

address like linked list nodes do.
 Easier to implement and understand: Using arrays to implement
stacks require less code than using linked lists, and for this reason it is
typically easier to understand as well.

A reason for not using arrays to implement stacks:

 Fixed size: An array occupies a fixed part of the memory. This means
that it could take up more memory than needed, or if the array fills up,
it cannot hold more elements.