Types of data structure
In all, it can be seen that data structures are highly beneficial, not least because they allow the most basic pieces of computer software to function correctly. Without data structures, we would not have the modern computer of today.
Data structures can be classified as
- Simple data structure
- Compound data structure
- Linear data structure
Non linear data structure
Simple Data Structure:
Simple data structure can be constructed with the help of primitive data structure. A primitive data structure used to represent the standard data types of any one of the computer languages. Variables, arrays, pointers, structures, unions, etc. are examples of primitive data structures.
Compound Data structure: Compound data structure can be constructed with the help of any one of the primitive data structure and it is having a specific functionality. It can be designed by user.
It can be classified as
- Linear data structure
- Non-linear data structure
Linear data structure:
Collection of nodes which are logically adjacent in which logical adjacency is maintained by pointers OR Linear data structures can be constructed as a continuous arrangement of data elements in the memory. It can be constructed by using array data type. In the linear Data Structures the relationship
of adjacency is maintained between the Data elements.
Operations applied on linear data structure: The following list of operations applied on linear data structures By applying one or more functionalities to create different types of data structures.
For example: Stack, Queue, Tables, List, and Linked Lists.
Non-linear data structure:
Operations applied on non-linear data structures: The following list of operations applied on non-linear data structures.
- Traverse(reaching to that point)
- Sort the list of elements
- Search for a data element
Non-linear data structure can be constructed as a collection of randomly distributed set of data item joined together by using a special pointer (tag). In non-linear Data structure the relationship of adjacency is not maintained between the Data items.
We provide below informal definitions of a few important, common notions that we will frequently use in this lecture notes.
A finite sequence of instructions, each of which have a clear meaning and can be executed with a finite amount of effort in finite time is called algorithm. Whatever the input values, an algorithm will definitely terminate after executing a finite number of instructions.
Data type of a variable is the set of values that the variable may assume. Basic data types in C: int, char, float, double.
The first thing that we need to consider when writing programs is the problem. However, the problems that we asked to solve in real life are often nebulous or complicated. Thus we need to distill such as system down to its most fundamental parts and describe these parts in a simple precise language. This process is called abstraction.
Through abstraction, we can generate a model of the problem, which defines an abstract view of the problem. Normally, the model includes the data that are affected and the operations that are required to access or modify.
As an example,
Consider a program that manages the student records. The head of the Bronco Direct comes to you and asks you to create a program which allows administering the students in a class. Well, this is too vague a problem. We need to think about, for example, what student information is needed for the record? What tasks should be allowed? There are many properties we could think of about a student, such as name, DOB, SSN, ID, major, email, mailing address, transcripts, hair color, hobbies, etc. Not all these properties are necessary to solve the problem. To keep it simple, we assume that a student’s record includes the following fields: (1) the student’s name and (2) ID. The three simplest operations performed by this program include (1) adding a new student to the class, (2) searching the class for a student, given some information of the student, and (3) deleting a student who has dropped the class. These three operations can be furthermore defined as below:
- ADD (stu_record): This operation adds the given student record to the collection of student records.
- SEARCH (stu_record_id): This operation searches the collection of student records for the student whose ID has been given.
- DELETE (stu_record_id): This operation deletes the student record with the given ID from the collection. Now, we have modeled the problem in its most abstract form: listing the types of data we are interested in and the operations that we would like to perform on the data. We have not discussed anything about how these student records will be stored in memory and how these operations will be implemented. This kind of abstraction defines an abstract data type (ADT).