Introduction to Data Structure

Introduction to Data Structure & Analysis of Algorithms

What is Data Structure

Definition 1-Data Structure is a method of organizing data that considers not only the items or data values stored but also the relationship of each data items. Definition 2-Data Structure is a particular way of organizing and storing data in a memory so that it can be accessed and modified efficiently manner.   “Data Structure is a group or set of data values maintain the relationships among them and the operations that can be applied to the data and data items.”  In another way of describing the data structure, the term data structure is used to describe the way data is stored and the apply algorithm is used to describe the way data is processed. Data structures and algorithms are interrelated to each other.

“Data structure is a representation of logical relationship between data and individual elements of data.” To develop a program for an algorithm we should select an appropriate data structure for that algorithm. So data structure is represented as: Algorithm + Data structure = Program Or Data Structure=Program-Algorithm

A data structure is known as a linear if its elements are stored in sequence or a linear list. The linear data structures such as an array, stacks, queues and linked lists organize data in linear or sequential order. A data structure is known as a non linear if its elements are stored in hierarchical classification, where data and data items appear at various hierarchical levels such as   trees and graphs are widely used non-linear data structures. A tree and graph structure represents hierarchical relationship between data and individual data item.

Why Are Need of Data Structure

⮚     Data Structure gives different level of organization data. ⮚     Data Structure tells how data can be stored and accessed in its elementary level. ⮚     Data Structure provides operation on group of data, such as adding an item, looking up highest priority item. ⮚     Data Structure provides a means to manage huge amount of data efficiently. ⮚     Data Structure Provides fast searching and sorting of data.

A Data Structure Need

Ø Memory space for each item it stores in location based. Ø Time to perform each basic operation. Ø Programming effort in term of coder and machine. Ø Each problem has ingredients and constraints on available time and space. Ø Best data structure for the job need careful analysis of problem characteristics.

How to Selecting a Good Data Structure

Here some points are selection of suitable data structure 1.     Analyze the problem to determine the resource constraints a solution must meet. 2.     Determine basic operation that must be supported. Quantify resource constraint for each operation. 3.     Select the data structure that best meets these requirements. 4.     Each data structure has cost and benefits. 5.     Rarely is one data structure better than other in all situations.

Types of Data Structure /Classification of Data Structure

We can defined a data structure as follows- Data structure is a way of organizing a large amount of data set more efficiently manner so that perform any operation on that data becomes more easily. Every data structure is basically used to managing the large amount of data set. Every data structure follows a particular methodology complete any operations. The operations in data structure should follow the basic principle of that data structure. According to these data structure policy we can store, access or manage data according to their need. So there are two types of Data Structure - 1. Primitive Data Structure   2. Non Primitive Data Structure

1. Primitive Data Structure:- Primitive data structures are  classified into the following categories: 1.     Integer 2.     Floating-point Numbers 3.     Character 4.     Pointers  2. Non-Primitive Data Structure :- Non Primitive data structures are  classified into the following categories: 1.     Linear Data Structure 1.     Array 2.     List 3.     Stack 4.     Queue 2.     Non-Linear Data Structure 1.     Tree 2.     Graph 3.       File Data Structure

1.     Primitive Data Structure

These data types of data structures are the basic data structures and most of these are built-in many high-level programming languages. Primitive or basic data structures can be defined as data types present in the programming languages. The main property of a primitive data structure is they cannot be changed by programmer and they are elementary in fashion. Types of Primitive Data Structure:-   1. Integer: Integer holds all the integer values basically all the positive and negative numbers without decimal. Ex.-11, 209, 3452 etc.     2. Floating Points Numbers: Floating point numbers includes all the real number positive, fractions as well as negative with the decimal point. Ex. - = 11.0, 567.98 etc.   3. Character: Character holds every character may it be any number, alphabets or any special symbol but it would be represented inside the double or single inverted comma. The character size range of  0 to 255 Ex.- “Ram”, ’$’, ‘67’ etc.   4. Pointers: Pointer is variable which hold the memory address of another variable known as pointers etc.

2. Non-Primitive Data Structures

Non-primitive data structures are the user defined and complex data structures we use in high level programming language. Non-primitive data structures are user-defined data structures via many programming languages provide in-built support for these data structures and they are considered as the user-defined data structure. This type of data structure uses primitive data structures so non-primitive data structures are derived from primitive data structures. Non primitive data structures can be further divided into various types- Types of Non-Primitive Data Structure: There are three types of Non-Primitive Data Structure: 1.     Linear Data Structure   2.     Non-Linear Data Structure    3.     Files Data Structure

1.     Linear Data Structure

In the linear data structure where each elements are stored in a sequential or linear manner. If a data structure manages the data in sequential manner then that data structure is known as Linear Data Structure.   Types of Linear Data Structure-  There are four categories of linear data structure-  1. Array: Array is a similar or homogeneous collection of elements. In other words, an array can store only similar data types at same time. An array stores all the elements in a linear sequential manner and in a contiguous memory location. In the process of storing elements in contiguous memory location where each operation such as accessing and retrieving data elements is simple manner. There are many disadvantages of an array such as it can store only similar data types at once and are not that much memory available at once place it cannot work i.e. it is not using the non continuous memory location.   2. Stack: Stack is similar to array list but if follows the concept of LIFO principle to store and retrieve elements or data item. LIFO acronyms Last In First Out i.e. the element stored last in the stack would be retrieved first.   To perform the LIFO technique, the stack uses two operations push () and pop ().  Push () operation is used to insert an element in the stack list Pop () operation is used to retrieve element one or many in the stack list.   3. Queues: The Queue data structure is similar to list just the opposite of the stack principle where it uses the FIFO policy or technique. FIFO acronyms first in first out i.e. the element stored first in the queue would be retrieved first.   4. List (Linked List): The properties of a list are similar to an array principle and it also stores elements in a linear manner. So List means linked list uses the concept of dynamic memory allocation to store its elements at contiguous and non contiguous memory locations are arranged in a linear manner and linked with each other it through node.  Non-Linear Data Structure

In a non-linear data structure the storage of elements doesn’t follow a sequential order. If a data structure organizes  and manage the data list in random order then that data structure is known as Non-Linear Data Structure. Types of Non-Linear Data Structure  1. Graph: A graph in data structure basically uses  a network hierarchical form of two components vertices and edges. In the graph, each edges are used to connect vertices. A graph is may directed or indirect manners.  2. Tree: Tree data structure uses a hierarchical model of data structure to represent its elements of root or child node where each node represents a value. The main example of tree data structures is the Binary tree. The topmost node of the tree is called as the root node and the last node is called as a leaf node. Tree data structures are the most complex and efficient use in programming language. There are various use of data structure to solve many real-time problems.  3. File :-A file is a group or set or collection of records. When we are using a file, we can store data in the various format such as .txt, .bin, .obj etc. Many high level programming languages covered with a built-in file handling structure format. We can apply read, write and append operations on files, there are various operation performed such as insert and retrieve data from files.  The file is the simplest way of creating and retrieving data but it is not productive way when it comes to a huge amount of data or large data set.  4. Heap:-A heap is a tree-based data structure in which all the nodes of the tree are in a specific manner in concept of binary tree. Heap is a tree data structure where the arrange their node max heap or min heap accordingly their need.

Difference Between Linear and Non-linear Data Structure

S. NO Linear Data Structure Non-linear Data Structure 1 Data items are arranged in a linear manner where each and every elements is connected to its previous and next adjacent node. Data elements are connected in network hierarchically manner. 2 Single level is involved. Multiple levels are involved. 3 Its implementation is easy in comparison to non-linear data structure. Its implementation is difficult in comparison to linear data structure. 4 Data elements can be traversed or moving in a single run only. Data elements can’t be traversed or move in a single run only. 5 Memory level is not utilized in an efficient way. Memory level is utilized in an efficient manner. 6 Examples are linear data Structure such as array, stack, queue, linked list, etc. Examples are such as trees and graphs. 7 Applications of linear data structures are mainly use in application software development. Applications of non-linear data structures are use in Artificial Intelligence,deep learning  and image processing.

Data Structures: Organization of Data (In terms of Allocation of Memory)

The storing of data you work with in a program use some kind of structure or memory organization. Organisation of data means the best way of utilization of memory in our system. There are two ways of memory utilization- 1.     Contiguous memory allocation - (Static Memory Allocation) 2.     Non-Contiguous memory allocation- (Dynamic Memory Allocation)   1.     Contiguous Memory Allocation- (Static Memory Allocation)  Contiguous memory allocation is a method of storing data in contiguous or adjoining, sectors of memory at one place, if there is not enough available space at the one place data is written to multiple places which known as a non-contiguous  memory allocation i.e. A non contiguous memory allocation is a method of storing data in sectors of memory that are not adjoining at one place .

In contiguous memory allocation structures of data are kept together in memory. Example-An array.  Since each element in the array is located next to one elements. Each items in a non-contiguous structure and scattered in memory but we linked to each other in some manner.  Example-linked list

Example-A person’s id number represented with a integer that occupies two bytes of memory. But his or her name represented as a string of characters may need many bytes and may even be of varying length.

Non-Contiguous Memory Allocation- (Dynamic Memory Allocation)

Non-contiguous memory allocation are implemented as a set of data-items known as nodes, where each node can link to one or more other nodes in the set or group. The example of non-contiguous memory allocation is linked list. A linked list represents a linear list of one-dimensional type of non-contiguous memory allocation structure and tree is an example of a two-dimensional non-contiguous memory allocation structure. The best example of non-contiguous memory allocation structure known as a graph.

Difference Between Contiguous and Non-contiguous Memory Allocation  S.NO. Contiguous Memory Allocation Non-Contiguous Memory Allocation 1. Contiguous memory allocation reserve consecutive blocks of memory in computer system or  file. Non-Contiguous memory allocation allocates separate blocks of memory to a file/process. 2. Fast access data or Faster in Execution. Slow access data or Slower in Execution. 3. It is simple way for the Operating System to control. It is difficult way for the Operating System to control. 4. Overhead is low as not much address translations are required there while executing a process. Overhead is high are there as there are more address translations. 5. Both Internal and external fragmentation occurs in Contiguous memory allocation structure. Only external fragmentation occurs in Non-Contiguous memory allocation structure. 6. It covered single and multiple-partition allocation are available. It covered paging and segmentation in memory system. 7. In contiguous memory allocation, memory wastage is there. In non contiguous memory allocation, No memory wastage is there. 8.  Swapped-in processes are arranged in the originally allocated space (fix).  Swapped-in processes can be arranged in any place in the memory(default).

  Next Topic-
Our Data Structure and Analysis of Algorithm (DSA) Using C tutorials will guide you to learn DSA one step at a time.
Enroll in our DSA Course for FREE.