Data Structures PDF

Data Structures 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. A data structure is not only used for organising the data. It is also...

Data Structures 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. A data structure is not only used for organising the data. It is also used for processing, retrieving, and storing data. There are different basic and advanced types of data structures that are used in almost every program or software system that has been developed. So we must have good knowledge of data structures. 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 organising, 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 Classification/Types of Data Structures: 1. Linear Data Structure 2. Non-Linear Data Structure. Linear Data Structure: Elements are arranged in one dimension, also known as linear dimension. Example: lists, stack, queue, etc. Non-Linear Data Structure Elements are arranged in one-many, many-one and many-many dimensions. Example: tree, graph, table, etc. Classification of Data Structure: Data structure has many different uses in our daily life. There are many different data structures that are used to solve different mathematical and logical problems. By using data structure, one can organize and process a very large amount of data in a relatively short period. Let’s look at different data structures that are used in different situations. Primitive data structure Primitive data structure is a data structure that can hold a single value in a specific location whereas the non-linear data structure can hold multiple values either in a contiguous location or random locations The examples of primitive data structure are float, character, integer and pointer. The value to the primitive data structure is provided by the programmer. The following are the four primitive data structures: o Integer: The integer data type contains the numeric values. It contains the whole numbers that can be either negative or positive. When the range of integer data type is not large enough then in that case, we can use long. o Float: The float is a data type that can hold decimal values. When the precision of decimal value increases then the Double data type is used. o Boolean: It is a data type that can hold either a True or a False value. It is mainly used for checking the condition. o Character: It is a data type that can hold a single character value both uppercase and lowercase such as 'A' or 'a'. Non-primitive data structure The non-primitive data structure is a kind of data structure that can hold multiple values either in a contiguous or random location. The non-primitive data types are defined by the programmer. The non-primitive data structure is further classified into two categories, i.e., linear and non-linear data structure. In case of linear data structure, the data is stored in a sequence, i.e., one data after another data. When we access the data from the linear data structure, we just need to start from one place and will find other data in a sequence. The following are the types of linear data structure: o Array: An array is a data structure that can hold the elements of same type. It cannot contain the elements of different types like integer with character. The commonly used operation in an array is insertion, deletion, traversing, searching. For example: int a = {1,2,3,4,5,6}; The above example is an array that contains the integer type elements stored in a contiguous manner. o String: String is defined as an array of characters. The difference between the character array and string is that the string data structure terminates with a 'NULL' character, and it is denoted as a '\0'. String data structure: char name = "Hello javaTpoint"; Linear data structure: Data structure in which data elements are arranged sequentially or linearly, where each element is attached to its previous and next adjacent elements, is called a linear data structure. Examples of linear data structures are array, stack, queue, linked list, etc. o Static data structure: Static data structure has a fixed memory size. It is easier to access the elements in a static data structure. An example of this data structure is an array. o Dynamic data structure: In the dynamic data structure, the size is not fixed. It can be randomly updated during the runtime which may be considered efficient concerning the memory (space) complexity of the code. Examples of this data structure are queue, stack, etc. Non-linear data structure: Data structures where data elements are not placed sequentially or linearly are called non-linear data structures. In a non-linear data  structure, we can’t traverse all the elements in a single run only. Examples of non-linear data structures are trees and graphs. String in Data Structure Strings are considered a data type in general and are typically represented as arrays of bytes (or words) that store a sequence of characters. Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’. // C program to illustrate strings #include int main() { // declare and initialize string char str[] = "Geeks"; // print string printf("%s", str); return 0; } String Operations: Strings support a wide range of operations, including concatenation, substring extraction, length calculation, and more. These operations allow developers to manipulate and process string data efficiently. Below are fundamental operations commonly performed on strings in programming. Concatenation: Combining two strings to create a new string. Length: Determining the number of characters in a string. Access: Accessing individual characters in a string by index.  Substring: Extracting a portion of a string. Comparison: Comparing two strings to check for equality or order. Search: Finding the position of a specific substring within a string. Modification: Changing or replacing characters within a string. Array Array is a linear data structure Array is a collection of items of the same variable type that are stored at contiguous memory locations. It is one of the most popular and simple data structures used in programming. Basic terminologies of Array Array Index: In an array, elements are identified by their indexes. Array index starts from 0. Array element: Elements are items stored in an array and can be accessed by their index. Array Length: The length of an array is determined by the number of elements it can contain. 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. Memory representation of Array In an array, all the elements are stored in contiguous memory locations. So, if we initialize an array, the elements will be allocated sequentially in memory. This allows for efficient access and manipulation of elements. Need of Array Data Structures Arrays are a fundamental data structure in computer science. They are used in a wide variety of applications, including: Storing data for processing Implementing data structures such as stacks and queues Representing data in tables and matrices Creating dynamic data structures such as linked lists and trees Declaration of Array Arrays can be declared in various ways in different languages. For better illustration, below are some language-specific array declarations: // This array will store integer type element int arr; // This array will store char type element char arr; // This array will store float type element float arr; Initialization of Array Arrays can be initialized in different ways in different languages. Below are some language-specific array initializations: int arr[] = { 1, 2, 3, 4, 5 }; char arr = { 'a', 'b', 'c', 'd', 'e' }; float arr = { 1.4, 2.0, 24, 5.0, 0.0 };  1. 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. Example:- 1. #include 2. int main() { 3. int numbers = {10, 20, 30, 40, 50}; 4. for(int i=0; i