Introduction to Data Structures and Algorithms

Welcome to the introduction to data structures tutorial. Have you ever used a DVD case to store multiple DVDs or even a simple register used to store data manually? Both of the above real-life examples are a form of data structures.

Here DVDs in a DVD case and records in the register are examples of data and their arrangement in a particular structure makes them more easily accessible. Combining a similar concept with the digital world gives us data structures in computers.

A set of data in mathematics might be unchanging but in computers, they can grow, shrink or change with the use of algorithms. These are dynamic sets.

What is a Data Structure?

A data structure is a specific way of arranging the data in a computer so that its usage is more effective and efficient.

• Data structures are a set of algorithms.
• They are useful to store data in a way that makes it extremely accessible and easy to manipulate

Basic Terminologies of Data Structure

Here are a few standard terms that we will be using frequently in our Data Structure’s learning journey:

1. Data: Data is the elementary value or we can also say that it is a collection of values. For example, employee name and employee ID are data about an employee.

2. Group Item: Data items having sub-data items are known as group items. For example, names. I can have the first name and surname of the employee.

3. Record: Record is the collection of various data items. For example in the case of employee data, the record might consist of name, address, designation, pay scale, and working hours.

4. File: A file is a collection of multiple records of the same entity. For example, a collection of 500 employee records is a file.

5. Entity: Entity is a class of certain objects. Each entity has various attributes.

6. Attribute: Each attribute represents a particular property of the entity.

7. Field: Field is an elementary unit of the information that represents the attribute of an entity.

Types of Data structures

There are 2 types of data structures:

1. Primitive data structure

A primitive data structure or data type is defined by a programming language and the type and size of the variables, values are specific to the language. It does not have any additional methods. For example int, float, double, long, etc. These data types can hold a single value.

2. Non-primitive data structure

These data structures are defined by the programmers and not by the programming languages. These data structures can hold multiple values and make them easily accessible.

Non-primitive data structures can further be classified into two types:

a. Linear Data Structure

In the linear data structure, as the name suggests, data elements are arranged sequentially or linearly where each element is in connection with its previous and next element.

Since a single level is involved in a linear data structure, therefore, the whole data structure is traversable through all the elements in a single run only. These data structures are easy to implement. For example array, linked list, stack, and queue.

b. Non-linear Data Structure

In a non-linear data structure, the elements’ arrangement is not sequential or linear. Instead, they are arranged hierarchically. Hence we cannot traverse through each element in one run. 

Non-linear data structures are a little bit more difficult to implement than linear data structures but they use computer memory more efficiently compared to linear data structures. For example graphs and trees.

Data structures classification can also be done in the following two categories :

• Static data structures
• Dynamic data structures

1. Static Data Structure

Static data structures have a specific memory size, the allocation of which is done at the time of compilation. Therefore, these data structures have fix memory size.

An array is the best example of static data structure.

2. Dynamic Data Structure

Dynamic data structures have flexible memory sizes since the memory allocation is done at the run time. Hence, dynamic data structures can shrink or grow as and when required by deallocating or allocating the memory respectively.

For example, linked lists, stack, queue, graphs, and trees are dynamic data structures.

Basic Operations on Data Structures

Some major and most common operations performed on a data structure are:

1. Search: Finding an element in a data structure.

2. Insert: Inserting an element in a data structure.

3. Delete: Removing an element from a data structure.

4. Update: Manipulating an element in a data structure.

5. Sort: Arranging elements in a data structure in either ascending or descending order.

6. Traversing: Visiting every element of the data structure one by one, starting from the first element, to perform some specific operation.

7. Merging: Combining two data structures, possibly of different sizes but of the same type (for example both should be an array) to form a third data structure.

Characteristics of Data Structures

1. Time Complexity: Time complexity is the time taken for the execution of operations on the data structure. The expected time taken for execution should be minimum.

2. Space complexity: Space complexity is the memory used for the execution of data structure operations. Memory used should also be as little as possible.

3. Correctness: The interface of a data structure should be implemented correctly.

Advantages of Data Structures

• Data Structures make use of memory efficiently, which has a great impact on programs requiring the processing of large databases.
• Data structures allow efficient and effective use of computer memory, therefore, making the system highly efficient.
• Reusability of data structure by integrating them in a package makes them highly efficient.
• The data structures termed Abstract Data Types (ADTs) provides the level of abstraction. This means that clients cannot see the internal working of the data structure.
• There are multiple types of Data Structures present, allowing programmers to choose the one, which is most suitable to solve the problem in the best way.
• Unlike traditional methodologies, data structures allow the use of scientific approaches which affects processing speeds, multiple request handling, and searching/sorting through large data.

Why you should learn Data Structure

Suppose you want to search your record in your institution’s record book among hundreds of students in your institution. Let us assume that the arrangement of records is in ascending order. If you start from the beginning and keep on searching you are going to exhaust soon with almost 90% of data still not looked through.

The better option is to go to the middle of the register and look for the roll number. If the roll number in the middle of the record book is lower than yours then you need to search only the second half of the record book and if it is higher than your roll number, you have to look in the first half of the record book.

Repeat the same process for the selected half and now you have only a quarter of the record book to search from. Continue this process multiple times. In this way, you will find your record in the record work, and just like that, you have implemented the binary search algorithm without even knowing it.

I hope from the above simple example it is clear why data structures are important. There are many examples from daily life that implements data structures without us even knowing. Books arranged in alphabetical order on a shelf, phone books, and dictionaries arranged in alphabetical order, are all examples of data structures.

Everywhere, whether in the real world or the digital world, the data arrangement must be in an organized manner so that it is easily accessible and modifications can be done easily and as soon as possible without messing things up. We will see more real-life scenarios and use of data structures in further articles.

Applications of Data Structures

Each type of data structures has different applications, for example :

• Arrays are useful in the arrangement of the leaderboard of games where we need to simply store the title and the score in ascending order.
• Web pages are easily accessible by using previous and next URL links which is a good example of a linked list.
• Stacks are logic behind temporary storage in recursive operations. We will learn about these operations in detail in future articles
• The shortest path algorithm and traveling salesman algorithms use graphs as their major data structure.

Prerequisites to learn Data Structure

Basic knowledge of C programming is important before we go into a  deeper understanding of the data structures.

Conclusion

After going through this article, we now have a better understanding of what a data structure is and its different types. We also saw some real-life uses of data structures and the importance and need of learning data structures.