Introduction to Data Structures

Data structure is a way of arranging data so that it can be accessed, updated, and deleted at a low cost. Data structure is also used for data processing, storing, and retrieving. To build an efficient program, we might need to use data structure properly. The right data structure boosts the performance of a program broadly.

To understand data structure let's use an example. When a program (suppose, the program is Microsoft Word) is being executed in the system or computer. The operating system brings the docx file along with the program file itself to the main memory (RAM) from permanent storage (HDD or SSD), to execute the program. The data or docx file is stored in RAM in a way so that it can be accessed by the program file (MS Word) efficiently. Organizing/arranging that data in the main memory is the data structure.^[2]

Structure in simple words: Suppose an application, where users purchase railway tickets online. It has to process the ticket request which came first. Suppose the total number of seats on a train is 10. Now, 11 people have requested for a seat. The application has to accept only the first 10 requests and reject the last one. So, the application has to use the First In First Out (FIFO) structure to find out which 10 users will get the ticket. Their structure means a set of rules that holds the data together.^[3]

So, we can say arranging data in a set of rules is a data structure. For example, array, set, object in javascript, dictionary, and tuple in python, etc. are data structures. Each of the data structures has its own rules; how data will be stored, retrieved, modified, and deleted is different in different data structures.

Classification of Data Structure

There are mainly two types of data structure. Linear and Non-linear data structure. The following figure shows a basic classification of data structure visually.

• Linear Data Structure: Linear data structure is the data structure, where data elements are stored next to each other. In other words, the linear data structure is the data structure in which elements are arranged sequentially or linearly.^[1] As computer memory is arranged in a linear way, linear data structures are easy to implement. All the elements of linear data structure can be traversed in a single run only. The linear data structure can be divided into two parts. Static and dynamic data structure.

  • Static Data Structure: Static data structures have fixed memory sizes.^[1] The array is the right example of static data structure. The array has a fixed memory size. We need to specify the number representing the total elements count of the array while initializing it. We cannot remove an element or append more elements to an array than its size capacity. Because of this behavior array is a static data structure.

  • Dynamic Data Structure: Unlike static data structures, in dynamic data structures, size is not fixed.^[1] Its size can be updated during runtime. The linked list is an example of a dynamic data structure. In the linked list, we do not need to specify the size of the collection while initializing it. Its size can be increased or decreased during runtime.

• Non-linear Data Structure: In non-linear data structures, data elements are not arranged in a sequential way. Data is arranged in a hierarchical manner. Where one element can be connected to one or multiple elements. When programs become complex, non-linear data structures might perform better than linear data structures.^[4] Non-linear data structures can be divided into graph and tree-based data structures.

Difference between linear and non-linear data structure in simple words.

References

1. Geeks for Geeks

2. Udemy Course by Abdul Bari

3. Data Structures: A Pseudocode Approach with C (2nd Edition)

4. Data Structure and Types - Programiz