Data Structures

 Unit-1

Introduction:

WHAT IS DATA STRUCTURE?

In computer science, a data structure is a way of organizing and storing data in a computer program so that it can be accessed and used efficiently. Data structures provide a means of managing large amounts of data, enabling efficient searching, sorting, insertion and deletion of data.

Data structures can be categorized into two types: Primitive data structures and non-primitive data structures.

Primitive data structures are the most basic data structures available in a programming language, such as integers, floating-point numbers, characters and Booleans.

Non-primitive data structures are complex data structures that are built using primitive data types, such as arrays, linked lists, stacks, queues, trees, graphs and hash tables.

The choice of data structure for a particular task depends on the type and amount of data to be

processed, the operations that need to be performed on the data and the efficiency requirements of the program. Efficient use of data structures can greatly improve the performance of a program, making it faster and more memory-efficient. 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.

The choice of a good data structure makes it possible to perform a variety of critical operations effectively. An efficient data structure also uses minimum memory space and execution time to process the structure.

Data Structure is a systematic way to organize data in order to use it efficiently.

Following terms are the foundation terms of a data structure.

 Interface − Each data structure has an interface. Interface represents the set of operations that a data structure supports. An interface only provides the list of supported operations, type of parameters they can accept and return type of these operations.

2 Data Structures

 Implementation − Implementation provides the internal representation of a data structure. Implementation also provides the definition of the algorithms used in the operations of the data structure.

Characteristics of a Data Structure

 Correctness − Data structure implementation should implement its interface correctly.

 Time Complexity − Running time or the execution time of operations of data structure must be as small as possible.

 Space Complexity − Memory usage of a data structure operation should be as little as possible.

Need for Data Structure

As applications are getting complex and data rich, there are three common problems that applications face now-a-days.

1. Efficient data processing: Data structures provide a way to organize and store data in a way that allows for efficient retrieval, manipulation and storage of data. For example, using a hash table to store data can provide constant-time access to data.

2. Memory management: Proper use of data structures can help to reduce memory usage and

optimize the use of resources. For example, using dynamic arrays can allow for more efficient use of memory than using static arrays.

3. Code reusability: Data structures can be used as building blocks in various algorithms and

programs, making it easier to reuse code.

4. Abstraction: Data structures provide a level of abstraction that allows programmers to focus on the logical structure of the data and the operations that can be performed on it, rather than on the details of how the data is stored and manipulated.

5. Algorithm design: Many algorithms rely on specific data structures to operate efficiently.

Understanding data structures is crucial for designing and implementing efficient algorithms.

6. Data Search − Consider an inventory of 1 million (106) items of a store. If the application is to search an item, it has to search an item in 1 million (106) items every time slowing down the search. As data grows, search will become slower.

3 Data Structures

7. Processor Speed − Processor speed although being very high, falls limited if the data grows to billion records.

8. Multiple Requests − As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data.

Importance of Data Structures in Programming

 Efficient data access and manipulation: Data structures enable quick access and manipulation of data. For example, an array allows constant-time access to elements using their index, while a hash table allows fast access to elements based on their key. Without data structures, programs would have to search through data sequentially, leading to slow performance.

 Memory management: Data structures allow efficient use of memory by allocating and deallocating memory dynamically. For example, a linked list can dynamically allocate memory for each element as needed, rather than allocating a fixed amount of memory upfront. This helps avoid memory wastage and enables efficient memory management.

 Code reusability: Data structures can be reused across different programs and projects. For example, a generic stack data structure can be used in multiple programs that require LIFO (Last-In-First-Out) functionality, without having to rewrite the same code each time.

 Optimization of algorithms: Data structures help optimize algorithms by enabling efficient data access and manipulation. For example, a binary search tree allows fast searching and insertion of elements, making it ideal for implementing searching and sorting algorithms.

 Scalability: Data structures enable programs to handle large amounts of data effectively. For example, a hash table can store large amounts of data while providing fast access to elements based on their key.

Basic Terminology

 Data − Data are values or set of values.

 Data Item − Data item refers to single unit of values.

4 Data Structures

 Group Items − Data items that are divided into sub items are called as Group Items.

 Elementary Items − Data items that cannot be divided are called as Elementary Items.

 Attribute and Entity − An entity is that which contains certain attributes or properties, which may be assigned values.

 Entity Set − Entities of similar attributes form an entity set.

 Field − Field is a single elementary unit of information representing an attribute of an entity.

 Record − Record is a collection of field values of a given entity.

 File − File is a collection of records of the entities in a given entity set.

Data structures can broadly be classified into two main categories:

1. Primitive Data Structures

Primitive data structures are the most basic types of data structures provided by programming languages. They include:

 Integer: Whole numbers (e.g., 1, 2, 100).

 Float: Numbers with decimal points (e.g., 3.14, 0.001).

 Character: Single characters (e.g., ‘A’, ‘B’).

 Boolean: Logical values (true or false).

Data Structures

Sample Program in C++ (Primitive Data Types)

#include <iostream>

using namespace std;

int main() {

int num = 10; // Integer

float pi = 3.14; // Float

char letter = 'A'; // Character

bool isHappy = true; // Boolean

cout << "Integer: " << num << endl;

cout << "Float: " << pi << endl;

cout << "Character: " << letter << endl;

cout << "Boolean: " << isHappy << endl;

return 0;

}

2. Non-Primitive Data Structures

Non-primitive data structures are more complex and are built using primitive data types. They are further divided into:

a. Linear Data Structures

In linear data structures, elements are arranged sequentially, and each element has a unique predecessor and successor (except the first and last elements).

 Array: A collection of elements of the same type, stored in contiguous memory locations.

 Linked List: A collection of nodes where each node contains data and a pointer to the next node.

 Stack: A collection of elements following the Last In First Out (LIFO) principle.

 Queue: A collection of elements following the First In First Out (FIFO) principle.

Sample Program in C++ (Array)

#include <iostream>

using namespace std;

int main() {

Data Structures

int arr[5] = {1, 2, 3, 4, 5}; // Array of integers

cout << "Array elements:" << endl;

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

cout << arr[i] << " ";

}

cout << endl;

return 0;

}

b. Non-Linear Data Structures

In non-linear data structures, elements are not arranged sequentially but follow a hierarchical or interconnected structure.

 Tree: A hierarchical structure where each node has a parent node and zero or more child nodes.

 Graph: A set of nodes (vertices) connected by edges, representing relationships.

Sample Program in C++ (Basic Tree Traversal)

#include <iostream>

using namespace std;

struct Node {

int data;

Node* left;

Node* right;

Node(int val) {

data = val;

left = right = nullptr;

}

};

void inOrder(Node* root) {

if (root == nullptr) return;

inOrder(root->left);

cout << root->data << " ";

7 Data Structures

inOrder(root->right);

}

int main() {

Node* root = new Node(1);

root->left = new Node(2);

root->right = new Node(3);

root->left->left = new Node(4);

root->left->right = new Node(5);

cout << "In-order Traversal: ";

inOrder(root);

cout << endl;

return 0;

}

c. File Structures

Specialized data structures designed for storing data in secondary storage for efficient retrieval and updates. Examples include B-trees and hash files.

Applications of Data Structures:

Arrays: Arrays are used to store a collection of homogeneous elements contiguous memory locations. They are commonly used to implement other data structures, such as stacks and queues, and to represent matrices and tables.

Linked lists: Linked lists are used to store a collection of heterogeneous elements with dynamic memory allocation. They are commonly used to implement stacks, queues and hash tables.

Trees: Trees are used to represent hierarchical data structures, such as file systems, organization charts, and network topologies. Binary search trees are commonly used to implement dictionaries and symbol tables.

Graphs: Graphs are used to represent complex relationships between data elements, such as social networks, transportation networks and computer networks. They are commonly used to implement shortest path algorithms and graph traversal algorithms.

Hash tables: Hash tables are used to implement associative arrays, which store key-value pairs. They provide fast access to data elements based on their keys.

8 Data Structures

 Stacks: Stacks are used to store a collection of elements in a last-in-first-out (LIFO) order. They are commonly used to implement undo-redo functionality, recursive function calls and expression evaluation.

 Queues: Queues are used to store a collection of elements in a first-in-first-out (FIFO) order. They are commonly used to implement waiting lines, message queues and job scheduling.

Common operations on various Data Structures:

Data Structure is the way of storing data in computer’s memory so that it can be used easily and efficiently. There are different data-structures used for the storage of data. It can also be defined as a mathematical or logical model of a particular organization of data items. The representation of particular data structure in the main memory of a computer is called as storage structure.

For Examples: Array, Stack, Queue, Tree, Graph, etc.

Operations on different Data Structure:

There are different types of operations that can be performed for the manipulation of data in every data structure. Some operations are explained and illustrated below:

 Traversing: Traversing a Data Structure means to visit the element stored in it. It visits data in a systematic manner. This can be done with any type of DS.

 Searching: Searching means to find a particular element in the given data-structure. It is considered as successful when the required element is found. Searching is the operation which we can performed on data-structures like array, linked-list, tree, graph, etc.

 Insertion: It is the operation which we apply on all the data-structures. Insertion means to add an element in the given data structure. The operation of insertion is successful when the required element is added to the required data-structure. It is unsuccessful in some cases when the size of the data structure is full and when there is no space in the data-structure to add any additional element. The insertion has the same name as an insertion in the data-structure as an array, linked-list, graph, tree. In stack, this operation is called Push. In the queue, this operation is called Enqueue.

9 Data Structures

 Deletion: It is the operation which we apply on all the data-structures. Deletion means to delete an element in the given data structure. The operation of deletion is successful when the required element is deleted from the data structure. The deletion has the same name as a deletion in the data- structure as an array, linked-list, graph, tree, etc. In stack, this operation is called Pop. In Queue this operation is called Dequeue.

 Create: It reserves memory for program elements by declaring them. The creation of data structure can be done during

o Compile-time

o Run-time.

 Selection: It selects specific data from present data. You can select any specific data by giving condition in loop.

 Update: It updates the data in the data structure. You can also update any specific data by giving some condition in loop like select approach.

 Sort: Sorting data in a particular order (ascending or descending). We can take the help of many sorting algorithms to sort data in less time. Example: bubble sort which takes O (n^2) time to sort data. There are many algorithms present like merge sort, insertion sort, selection sort, quick sort, etc.

 Merge: Merging data of two different orders in a specific order may ascend or descend. We use merge sort to merge sort data.

 Split Data: Dividing data into different sub-parts to make the process complete in less time.

10 Data Structures

Algorithm Specifications:

What is an Algorithm? Algorithm Basics

The word Algorithm means” A set of finite rules or instructions to be followed in calculations or other problem-solving operations” or” A procedure for solving a mathematical problem in a finite number of steps that frequently involves recursive operations”. Therefore, Algorithm refers to a sequence of finite steps to solve a particular problem.

Use of the Algorithms:

Algorithms play a crucial role in various fields and have many applications. Some of the key areas where algorithms are used include:

Computer Science: Algorithms form the basis of computer programming and are used to solve problems ranging from simple sorting and searching to complex tasks such as artificial intelligence and machine learning.

Mathematics: Algorithms are used to solve mathematical problems, such as finding the optimal solution to a system of linear equations or finding the shortest path in a graph.

Operations Research: Algorithms are used to optimize and make decisions in fields such as transportation, logistics, and resource allocation.

Artificial Intelligence: Algorithms are the foundation of artificial intelligence and machine learning, and are used to develop intelligent systems that can perform tasks such as image recognition, natural language processing and decision-making.

Data Science: Algorithms are used to analyze, process, and extract insights from large amounts of data in fields such as marketing, finance and healthcare.

These are just a few examples of the many applications of algorithms. The use of algorithms is continually expanding as new technologies and fields emerge, making it a vital component of modern society.