The logical or mathematical model of a particular organization of data is called a data structure. A data structure is a way of storing and accessing the data into an acceptable form for a computer. So that data is processed in a small interval of time. In a simple way, we say that storing the data into computer memory is called a data structure.
A data structure can be broadly classified into
- Primitive data structure
- Non-primitive data structure
(i) Primitive data structure
The data structures, typically those data structures that are directly operated upon by machine-level instructions i.e. the fundamental data types such as int, float, double incase of ‘c’ are known as primitive data structures.
(ii) Non-primitive data structure
The data structures, which are derived from the primitive data structures called non-primitive data structures.
There are two types of non-primitive data structures.
- Linear:- whose elements form a sequence and every element has a unique predecessor and unique successor. Or a list, which shows the relationship of adjacency among elements, is said to be a linear data structure. The most, simplest linear data structure is a 1-D array. Other examples of linear data structures are link list, stack, queues, etc.
- Non-linear:- whose elements do not form a sequence and there is no unique predecessor and unique successor. Or A list, which doesn’t show the relationship of adjacency between elements, is said to be a non-linear data structure. Examples of non-linear data structures are trees and graphs.
More about Linear Data Structure: Little description of linear data structure is given below.
Link List: A link list is an example of linear data structures. it is a collection of nodes and each node can hold the address of previous nodes, next nodes, or both the nodes. It can be divided into a singly linked list, doubly or circular link list, and circular doubly linked list. A short description of the link list is given below:
- Singly-linked list: – A single linked list is used to traverse among the nodes in one direction.
- Doubly linked list: – A double linked list is used to traverse among the nodes in both the directions.
- Circular linked list: – It is a singly linked list in which the last node contains the address of the first node.
- Circular doubly link list: – It is also a doubly linked list whose first and last element contains the address of each other.
- Stack: – It is also called as last-in-first-out (LIFO) system. It is a linear list in which insertion and deletion take place only at one end. It is used to evaluate different expressions.
- Queue: – It is also called as first-in-first-out (FIFO) system. It is a linear list in which insertion takes place at once end and deletion takes place at other ends. It is generally used to schedule a job in operating systems and networks.
Non-linear data structure:-
The frequently used non-linear data structures are
- Trees: – It maintains the hierarchical relationship between various elements
- Graphs: – It maintains a random relationship or point-to-point relationship between various elements.
OPERATION ON DS
The four major operations performed on data structures are:
- Insertion structure: – Insertion means adding new details or new node into the data
- Deletion: – Deletion means removing a node from the data structure.
- Traversal: – Traversing means accessing each node exactly once so that the nodes of a data structure can be processed. Traversing is also called as visiting.
- Searching: – Searching means finding the location of a node for a given key value.
- Sorting: – It is a method to arrange data either in ascending order or in descending order.
- Merging: – Merging is a process of combining the data items of two Sorted lists into a single sorted list.
REPRESENTATION OF DATA STRUCTURES: Any data structure can be represented in two ways. They are: –
- Sequential representation
- Linked representation
A sequential representation maintains the data in contiguous memory locations which takes less time to retrieve the data but leads to time complexity during insertion and deletion operations. Because of its sequential nature, the elements of the list must be freed, when we want to insert a new element or new data at a particular position of the list. To acquire free space in the list, one must shift the data of the list towards the right side from the position where the data has to be inserted. Thus, the time taken by the CPU to shift the data will be much higher than the insertion operation and will lead to complexity in the algorithm. Similarly, while deleting an item from the list, one must shift the data items towards the left side of the list, which may waste CPU time.
The drawback of Sequential representation: –
The major drawback of sequential representation is taking much time for insertion and deletion operations unnecessarily and increasing the complexity of the algorithm.
(ii) Linked Representation: –
Linked representation maintains the list by means of a link between the adjacent elements which need not be stored in contiguous memory locations. During insertion and deletion operations, links will be created or removed between which takes less time when compared to the corresponding operations of sequential representation.
Applications and uses of Data Structures
We know that data may be organized in many different ways, the logical & mathematical organization of data is called a data structure. When we apply this data structure it comes up with the implementation of stack, queue, list, trees, sorting, and searching of data.
- Stack: In the computer, if any expression is to be calculated, it is calculated by using stack. For example any expression like a+b-c/e or (a+b)/e-f%g, etc.
- Queue: Implementation of a queue is also an important application of data structure. Nowadays computer handles multiuser, multiprogramming environment. In this environment a system(computer) handles several jobs at a time, to handle these jobs the concept of a queue is used.
- Link List: In computer science several times we face a situation, where we have to insert and delete items from any position that time the concept of link list is used.
- Tree: It stores data in a hierarchical fashion. In windows, all the directories are stored using the concept of trees.
Importance of Data Structure
In computer science, the Importance of data structure is everywhere. The data structure provides basic stuff to resolve problems. Its importance can be understood by the following:
- The software has two parts front end and back end. The front end provides an interface and the back end is called database which contains a record of customers. There can be million or trillion of customers. If we have to find out the record of a particular or a number of customers, it is done by searching the method which is an operation on a data structure.
- If any software is to be run, at first it is fed into computer memory. In computer memory jobs are entered into queues. And the queue is also a concept of data structure.
- As we know when jobs and processes are entered then queues are formed. These queues can have too many jobs or processes. In queues, jobs are processed in the same order as they entered. If any job is created it is placed at the end of a queue. Suppose we have to add or delete any job in any order then the concept of the queue will be failed and the concept of link list will be used.
- If any data is to be stored in hierarchical fashion then the concept of a tree is used.
- If data is to arranged alphabetically or numerically then it is done by sorting method which is an operation on a DS.
Comment you like or not our article on “Introduction to the Data Structure” and you can also visit our other article by click here.