Home » Programming » Data Structure and Algorithm » Introduction to Data Structure and Algorithm

# Introduction to Data Structure and Algorithm

Data structure is a way of arranging all the data items in the computer’s memory and establishing a proper relationship between those data items. Data structures are the basic building blocks of a program. That is to say, the structural and functional aspects of the program depend on the design of the data structure. This is important to realize that the correct selection of the data structure for a program or application results in the enhanced efficiency of that program/application.

Data structure mainly specifies the following four things:

• Organization of data
• Accessing methods
• Degree of associativity
• Processing alternatives for information

An algorithm is a set of instructions to solve a certain problem. In fact, for a program you must select an appropriate algorithm along with a data structure. This ensures better efficiency of the program.

Program = Algorithm + Data Structures

For Example: To print entered integers in descending order

```Step 1: Start.
Step 2: Firstly, take integers as input from the user.
Step 3: Then, arrange those integers in data structure.
Step 4: After that, sort integers in descending order.
Step 5: Finally, print sorted integers.
Step 6: End.```

## Applications of Data Structures

• In web browsers, to store the search history of the user in  sorted manner according to time.
• In text editors, to implement undo/redo feature. That is to say, stack data structure maintains the change in document. And we can retrieve those data whenever needed.
• For asynchronous data transfer. Notably, we may not receive the data at the same rate as they are sent. To overcome this, we must choose a reliable data structure which will not affect the accuracy and efficiency of the system.
• For reversal of string. Firstly, we push every character of the string in the stack one by one. Finally, we retrieve/pop those characters whenever needed.
• Similarly, linux file system manages the directories and files in tree data structure.

## Classification of Data Structure

Data structures are the set of variables forming a basis of a programming tool. Moreover, they represent the relationship between data items and basic operations performed on them.

Data structures can be classified into two categories:

1. Primitive data structure
2. Non-Primitive data structure

### Primitive Data Structures

Primitive data structures are the basic data structures. Additionally, we can manipulate these data structures with machine level instructions. These are also known as simple data types since they cannot be recreated using other data structures. Basic data structures like integer, float, character and boolean are the primitive data types. To study more about the primitive data types you can visit here.

### Non-primitive Data Structure

Non-primitive data structures are more complicated data structures than primitive data structures. Also, they are derived from primitive data structures. Furthermore, non-primitive data structures emphasize on grouping of homogeneous (same) or heterogenous (different) data items with relationship between each data item. However, we cannot apply machine level instructions directly for manipulation of these data structures. There are two types of data structure based on the structure and arrangement of data.

1. Linear Data Structure (Example: Arrays, stacks, linked list, etc.)
2. Non-linear Data Structure (Example: graphs, trees, etc.)

#### Array

Array is the collection of data with the same data types stored in adjacent memory locations. Equally important, Traversing, searching and sorting are relatively easier in arrays. For this reason, storing relatively permanent collections of data is preferred in arrays.

For the array of size n, subscript “0” (zero) refers to the first element of the array and the subscript “n-1” for the last element. Hence, we can access the elements of array “A” with the subscript notation (bracket notation).

`A[0] for first item,A[1] for second item,A[2] for third item,..A[n-1] for last item`

Here the value N in A[N] is known as index or subscript. Arrays can be classified as one-dimensional or multidimensional arrays.

Syntax for declaration:

``datatype arrayName[size];``

Example:

``char name[10];``

#### Structure

Structure is the collection of data with same or different data types grouped together under a single name. Likewise, the individual structure elements or variables are called members.

Syntax for structure definition:

``````struct structureName
{
member 1;
member 2;
. . .
Member n;
};``````

Syntax for structure variable declaration:

``struct structureName variable_1, variable_2, …, variable_n;``

Also we can combine structure definition and variable declaration in one statement as,

``````struct Student
{
char name[20];
int age;
char gender;
} s1, s2;``````
##### Accessing members of a structure

Basically, there are two types of operators for accessing members of a structure depending on the structure variable declared i.e. either the variable is pointer type or non-pointer type variable.

1. Member operator (dot operator or period operator (.)) , for non-pointer type variable
2. Structure pointer operator (->), for pointer type variable

#### Unions

Unions are also the collection of data with same or different data types grouped together under a single name. The syntax for declaration and definition of unions are the same as that of structures. They differ from each other in terms of storage only. In structures, each member has their own memory locations while in unions all members use the same memory location which is equal to the largest member’s size.

Syntax for Declaration of union:

``````union unionName
{
data_type member1;
data_type member2;
. . .
data_type memberN;
};``````

Syntax for structure variable declaration:

``union unionName variable_1, variable_2, …, variable_n;``

Likewise the structures, we combine the union definition and variable declaration in one statement as,

``````unionStudent
{
char name[20];
int age;
char gender;
} s1, s2;``````

#### Pointer

A pointer is a variable which holds the address of another variable of the same data type rather than its actual value. Each memory cell has its unique address. Therefore, this address can be used to access the data residing at that location. So, a pointer variable points to those locations and we can directly alter the value of that memory location using pointer.

##### Pointer Declaration

We also need to declare pointers just like other variables. Declaration is same as other variables but we have to use asterisk (*) before the variable name.

Syntax:

``data_type *pointer_variable;``

Example:

``char *ptr;``

#### Class

Classes are the user defined data types which defines the types of data structures and the functions that operate on those data structures. To point out, the data inside the class are data members (or attributes) and functions are member functions (or methods). Likewise, the instances of classes are objects. Of course, they contain the member functions, variables, functions, etc. defined in the class definition.

Syntactically, classes are extensions of C Structures. C contains functions and overloaded operators whereas structures don’t. When we define a class we are basically creating a new abstract data type which we can treat as other data types.

Declaration of class:

``````Class ClassName
{
Access_specifier1: member_data1;
member_data2;
. . .
member_function1;
. . .
Access_specifier2: member_data1;
member_data2;
. . .
member_function1;
. . .
Access_specifier2: member_data1;
member_data2;
. . .
member_function1;
. . .
}``````

Declaration of object:

``ClassName objectName;``

An abstract data type is a data type which is packaged with the operations that are meaningful for the data type. In other words, we encapsulate the data and operations on the data and hide them from the user. For this reason, the user does not need to know the working mechanism behind the operations.

The ADT is the basic mathematical concept to define the data type. Basically, ADT is the collection of values and the set of operations that can be operated on those values. Another key point is every functions or operations can execute other operations to perform a certain task if required.

``````struct Number {