Data Structures in C

The data structures in c is a logical or mathematical model of a particular arrangement or organization of data. In other words, a data structures in c is a particular way of storing data in the computer’s memory so that it can be used easily and efficiently. Many different data structures might store the same data, each of which is suited to organize data differently. By analyzing the most frequent ways that your data is used, you can decide which data structure is appropriate. While designing a data structure, one must identify the logical structure of data in a particular application, accordingly choose the organization of data and find out various operations applied to it.

The choice of a good data structure makes it possible to perform a variety of critical operations effectively. An efficient data structure uses minimum memory space and execution time to process the structure as possible. A well-designed data structure has the following characteristics:

• It should be simple enough so that various operations(searching, insertion, sorting etc.) can be performed on data effectively.

• It must be rich enough to mirror the actual data relationship in the real-world (real-world modelling). In other words, the way you process the data will often mirror how the corresponding objects in the world interact.

The study of various data structures will expose you to a vast collection of tried and proven methods to design efficient programs. Thus as you develop an awareness of various data structures, it will help you choose the appropriate one in large software applications. Data structures are used in various diverse fields of computer science, such as :

• Operating System
• Numerical Analysis
• Artificial intelligence
• Simulation
• Network Analysis
• Computer Design
• Statistical analysis package
• Graphics

Each of these application areas may use different data structures for development. In many of these applications, a different type of data structure can solve the same problem. In such a situation, a designer plays a game of trade-off between speed and memory. One data structure utilizes memory efficiently but results in slow execution speed, whereas other data structures sacrifice memory for execution speed. Thus absolutely no best data structure exists. So designers must rely on their knowledge about the pros and cons of various data structures to choose the one that best fits each application.

We know that data may be organized in primary and secondary memory. The Data Structure only deals with the organization of data in main memory (RAM), whereas data in secondary memory is referred to as file structures.

Classification of Data Structures

In computer science, different data structures are known depending on the area of applications. Before going into details of each data structure, we will study how they are classified.

Various data structures can be classified as follows:

• Linear and Non-Linear Data Structures
• Homogeneous and Heterogeneous Data Structures
• Static and Dynamic Data Structures

Data Structures can be classified as Linear or Non-Linear based on whether the data items of a particular data structure are arranged in a linear sequence or not. By the term linear sequence, we mean that the particular data structure items are processed one after the other sequentially.

In a Linear data structure, the elements are arranged in a sequence so that processing of elements is possible in a linear fashion. In such a data structure, each element has a zero or one successor. Array, Stack, Queues, Linked list are examples of linear data structure.

In a non-linear data structure, the elements are not arranged in a sequence, i.e. there is no unique successor of an element. trees, graphs are examples of non-linear data structures. The operations like traversing, insertion and deletion are not performed linearly on these data structures. These data structures are multilevel data structures.

Data Structures can also be classified as homogeneous or heterogeneous data structures depending upon the type of elements in the data structure. In homogeneous data structures, all elements are of the same type, whereas in heterogeneous data structures, the elements may not be of the same type. An array in which all elements are of the same type is an example of a homogeneous data structure. However, A record in which elements are of different types is an example of a non-homogeneous data structure.

Another way of classifying data structure is as Static or Dynamic data structure. This classification is done depending on whether a fixed size is allocated to the structure. In the case of Static data structures, the size of the structure and its associated memory locations is fixed when the program is compiled. An array is an example of a static data structure. In a Dynamic data structure, the size of the structure and its associated memory locations is not fixed, i.e. it may vary. Such data structures are created as the program executes, and they expand or shrink to accommodate the data being stored. In programming languages like C, C++, dynamic data structures are implemented using pointers. For example, A stack can be implemented using an array or linked list. If the stack is implemented using the array, then it is a static data structure, and if it is implemented using a linked list, it is a dynamic data structure. The main drawback of static data structure is that memory space is either wasted or insufficient.

Operations On Data Structures

To process data stored in various data structures, there exist several operations. The choice of a particular data structure depends largely on how frequently a specific operation is performed.
The four basic operations that can be applied to a data structure are as follows:

• TRAVERSING: Accessing each record exactly once so that it can be processed. This operation of accessing and processing records is also known as 'visiting' the record. ·
• SEARCHING: Finding the specified record(s) in a given data structure based on a given key value.
• INSERTION: Addition of a new record to a data structure.
• DELETION: Removing an existing record from a data structure. Before deleting a record, it must be searched.
In addition to the above basic operations, some other operations can also be performed on some data structures. These include
• SORTING: Arranging records based on the key value in a specified order.
• MERGING: Combining the records of two similar sorted data structures to form a new data structure of the same type.
• COPYING: Selecting a particular range of records from a data structure and inserting it into another data structure of a similar type.
• CONCATENATION: Selecting the records of two similar data structures and combining them.

Data Structure Operation By Example

Consider an example of a company that maintains an employee file in which each record contains the following data about a company’s employee,
      (Empno, Empname, Designation, Salary, DOJ(Date of Joining))
Suppose we want to calculate the income tax of all the employees of the company. To accomplish this operation, we need to traverse the file to obtain the Salary of each employee so that each employee’s income tax can be calculated.
Suppose we want to obtain the Salary for a given employee number. For this, we need to search the file for the record containing the given employee number.
If a new employee joins the company, we need to insert his/her record into the file.

If an employee leaves the company, then we need to delete his/her record.
If we want to arrange the records of employees alphabetically, we need to sort the file based on the employee name key.
Suppose the same company opens a new branch in some other city that also maintains employee information. If the company’s president requires information about both the branches according to their name alphabetically, we need to merge two sorted files of different branches.