Introduction to Data Structures
Data structures are a very important part and a key component of computer science. Without the presence of different types of data structures, it is impossible to store the information effectively. Data structures are a way to store, manipulate and retrieve data efficiently. Data structures are largely used in almost all the fields of computer science.
What is a Data Structure:
It is a way of structuring/organizing data in a computer so that we can make use of this data in the most efficient manner. The main purpose of using data structures is to reduce the space and time complexity of every possible computation. There are various kinds of data structures in computer science such as arrays, linked lists, stacks, queues, trees and graphs, etc.
Basic Terminologies of data structures:
Some of the most common terms used in data structures are:
1. Data: It is a collection of values or a single value that need to be stored somewhere for future use. For example, in schools and universities, the details of students such as student id, student name, etc. comprise of data.
2. Group-items: Group data items are sub-data items for a given data. For example, the student name could comprise First name, middle name and last name.
3. Records: Records are a collection of different data items. For example, the record of one student consists of his first name, middle name, last name, phone number, roll number, address, etc.
4. File: A file is a collection of more than one record. For example, if a course has 200 students enrolled, then we can store the records of all those students in a single file.
5. Entity: An entity is a class of various objects. Each entity comprises various attributes.
6. Attribute: An attribute describes a particular property of an entity. We can have more than one attribute for an entity.
7. Field: A field represents an attribute of an entity.
Types of Data Structures:
At the most basic level, we divide data structures into two categories: Primitive and Non-primitive. We can further classify non-primitive data structures into linear and non-linear.
1. Primitive data structures:
Primitive data structures are those that are by default defined in a programming language. It does not include any additional methods. For example, int, long, float, double, char, etc. are some of the primitive data structures. They are also known as primitive data types. They cannot hold multiple values at a time.
2. Non-primitive data structures:
Non-primitive data structures are those, which are not inbuilt in the programming language. Usually, the programmers define these data structures for making their problems easier. Non-primitive data structures have certain advantages over primitive data structures, such as they can hold multiple values at a time. Also, they are easily accessible.
We can further classify non-primitive data structures into two categories: Linear and Non-linear data structures.
a. Linear data structures: As the name suggests, linear data structures are those which can hold data in a linear or sequential manner. In linear data structures, each element has a connection with its previous and the next element. Some examples of linear data structures are: arrays, linked lists, stacks and queues
b. Non-linear data structures: Non-linear data structures are those in which the data is not arranged sequentially, rather we have the data in a hierarchical format. Due to hierarchical arrangement, we cannot traverse the whole data in one go.
Non-linear data structures are more efficient than linear data structures when it comes to efficiency and space and time complexity. Non-linear data structures are further categorized as Static and Dynamic.
1. Static Data structures: Static data structures are those which have a fixed memory size and this memory size is decided at the time of compilation itself. In static data structures, if we have once given a specific size to the data structure, we can’t shrink or expand it at the run time. The most suitable example of static data structures is an array.
2. Dynamic data structures: As the name suggests, these data structures have varying memory sizes i.e. we can change the size according to time and need at the run time as well. We allot the memory sizes to dynamic data structures at the run time.
A few examples of dynamic data structures are link lists, stacks, queues, trees and graphs.
Basic Operations on Data Structures:
The most common operations that we perform on almost all data structures are:
1. Search: We perform search operation on a data structure whenever we wish to find a particular element.
2. Traverse: Traversal includes visiting all the values in a data structure.
3. Insert: Insertion includes adding/inserting new elements into the pre-existing data structure.
4. Update: Update operation helps to manipulate one or more elements in a data structure.
5. Delete: This operation helps to delete one or more elements from a data structure.
6. Merge: It is used to combine two or more data structures. Merge operation is mostly performed on data structures of the same type.
7. Sort: Sorting means arranging the given data in either ascending or descending order.
Characteristics of Data Structures:
The following are the characteristics of data structures:
1. Time complexity: Time complexity gives us the time that the execution of a particular operation on a particular data structure will take. The time taken should be minimum so as to have better efficiency of the program.
2. Space complexity: Space complexity tells us about the extra memory space that any operation will take to complete its execution. We should try to use the minimum possible extra space for program execution.
3. Correctness: This characteristic says that we need to correctly implement the interface of the data structure.
Need to Learn Data Structures:
So, why do we need data structures? The simple answer to this question is to reduce space and time complexity as well as to improve the efficiency of the code.
Let us understand with the help of a small example. Suppose we wish to search the record of a particular student in a department out of 500 students. Consider that the student records are sorted in ascending order according to their roll numbers.
If we start searching from beginning to end one by one, it will take a lot of time. However, if we make use of binary search i.e. we first go to the middle record and check if the record to be searched is after the middle record or before. In this way, we have reduced the search by half. This is one of the examples that show how data structures improve the efficiency of any computation. There are many such uses of data structures in the whole of computer science.
If we see in our day-to-day life, we see a lot of examples of data structures. For example, all of us have a few books arranged on our study tables. This pile of books is an example of a stack implementation. Another example is whenever we go to a bank or stand in a queue to buy movie tickets, we are following first in first out principle. This is the implementation of the queue data structure.
Advantages of Data Structures:
- Reduce the computation time for any problem.
- These help to utilize the available memory space in a more efficient manner.
- Ensure the reusability of code as we can write the code for a stack or any data structure only once in the program and use it at multiple places.
- The abstract data types(ADT) provide us with the best way to understand and use data structures without going deep into the implementation details.
- There are multiple choices available. We can choose any one data structure according to our needs and the need for the problem to be solved.
- Data structures provide scientific computation methods that help in improving speed, efficiency and easier implementation of operations on data structures.
Applications of Data Structures:
- Arrays are useful whenever we have sequential and fixed-size data implementation. For example, in online or video games as well as in online coding contests, we have names and positions of players or students. These leaderboards are created with the help of arrays.
- We use stacks in all the recursive operations as function calls make use of the stack.
- In web pages, we make use of linked lists to visit another web page from a given URL in that web page.
- Priority queues help to implement heap and other data structures. Priority queues are also used in scheduling algorithms of the CPU.
- To find the shortest path between two points, we make use of graphs.
Conclusion:
Data structures are one of the most significant components of computer science. Data structures help to increase the computation power of any program and help to reduce the time taken to solve a problem. Thus, having a good knowledge of data structures is of utmost importance.