What is Data Structure?
Data Structure is a systematic way to store and organize data so that it can be used efficiently. For example arrays, Linked List, Stack, Queue, etc. are data structures. Whether it is Operating System, Compiler Design, Artificial intelligence, Graphics or anything else, Data structure is useful in every aspect of computer science. Data structure is associated with algorithms that allows programmers to handle data in efficient ways and enhance the performance of the application.
Every data structure has its own interface that represents the operations it supports. Interface provides the list of supported operations and type of parameters only. Implementation provides the internal representation of data structure along with the definition of the algorithms used in the operations of that data structure.
Why Data Structure is required?
Applications are getting complex and data is crucial as well. The applications therefore faces several problems now-a-days that can easily be resolved with data safety by using data structures. Let’s have a look on the issues arising in lack of DS:
Multiple Requests: There may be thousands of user search for data at the same time on a web server. In such case, a fast server also fails while searching the data.
Data Search: Let us assume an inventory of 1 million (10⁶) items of a store. If the application is to search an item, it has to search an item in 1 million (10⁶) items every time slowing down the search. As data grows, search will become slower.
Processor Speed: Processor speed although being very high, falls limited if the data grows to billion records.
A data structure can organize data in such a way that all items may not be required to be searched, and the required data can easily be searched instantly.
Benefits of Data Structure
As we have already discussed it can arrange and store data in a proper manner. Let us have a look on the benefits of using DS in our applications:
Re-usability: Data structures are reusable. We have implement a DS only once and then we can use it at any other place. We can compile an implementation of a DS into libraries which can be used by different clients.
Efficiency: A program will be more efficient if we choose the best suited DS for it. Let’s take an example to search a particular record in a set of data. If we organize that data in an array, we will have to search sequentially for the particular record. That means using an array may not be the best suit here. There are better data structures that can make the search process efficient like ordered array, binary search tree or hash tables.
Abstraction: DS is specified by the ADT which provides a level of abstraction. The client program uses the data structure through interface only, without getting into the implementation details.
Basic Terminologies in DS
Entity Set: Entities of similar attributes form an entity set.
Field: Field is a single elementary unit of information representing an attribute of an entity.
Record: Record is a collection of field values of a given entity.
File: File is a collection of records of the entities in a given entity set.
Attribute and Entity: An entity is that which contains certain attributes or properties, which may be assigned values.
Data: Data are values or set of values.
Data Item: Data item refers to single unit of values.
Group Items: Data items that are divided into sub items are called as Group Items.
Elementary Items: Data items that cannot be divided are called as Elementary Items.
Data Structure Classification
We can classify DS into Premitive and Non-Premitive. The following hierarchy shows the classification in details:
Linear Data Structures
Linear DS is one where all of its elements are arranged in linear order. The elements are stored in non-hierarchical way where each element has the successors and predecessors except the first and last element.
Linear DS are of following types:
An array is a collection of similar type of data items. Each data item of an array is called an element of that array. The data type of the elements may be any valid data type like char, int, float or double.
The elements of an array share the same variable name but each one has its own index number known as subscript which is unique. An array can be one dimensional, two dimensional or multidimensional.
Linked list is also a type of linear DS. It is used to maintain a list in the memory. It can be seen as the collection of nodes stored at non-contiguous memory locations. Each node of the list contains a pointer to its adjacent node.
Stack is a linear DS in where insertion and deletions are allowed only at one end called top. A stack is an abstract data type (ADT). We can implement a stack in most of the programming languages. It is named so because it behaves like a real-world stack. For example piles of plates or deck of cards etc. It works on Last-In-First-Out (LIFO) methodology.
Queue is a linear type of DS. Here we can insert elements only at one end called rear and delete element only at the other end called front. It is also an abstract data structure similar to stack. Queue is opened at both end therefore it works on First-In-First-Out (FIFO) methodology for storing the data items.
Non Linear Data Structures
In non-linear type of DS each element is connected with two or more other elements in a non-linear arrangement. The data elements are not arranged in sequential structure.
Nonlinear DS are of following types:
Trees are multilevel data structures. It has hierarchical relationship among its elements known as nodes. The bottom most nodes in the hierarchy are known as leaf node and the topmost node is known as root node. Each node contains pointers to point adjacent nodes.
This DS is based on the parent-child relationship among the nodes. Each node in the tree can have more than one children except the leaf nodes whereas each node can have at most one parent except the root node.
Graphs is a pictorial representation of set of elements connected by the links known as edges. Elements are represented as vertices. A graph is different from tree in the sense that a graph can have cycle while the tree cannot have the one.
Operations on Data Structures
We can apply following operations on a data structure:
Insertion: the process of adding an element to DS at any location.
Deletion: the process of removing an element from DS from any random location.
Searching: the process of finding the location of an element within DS. We can perform this operation either by using Linear Search or by using Binary Search algorithm.
Sorting: the process of arranging DS in a specific order. There are several algorithms to perform sorting such as insertion sort, selection sort, bubble sort, etc.
Merging: the process of joining two DS of same type to produce the third one.
Traversing: Every DS has its own set of data elements. Visiting each element of DS in order to perform some specific operation like searching or sorting is known as traversing.
Was this article helpful? We would love to hear from you. Don’t forget to share your views in the comment section below. Keep visiting our Tech Blogs and stay updated with our future posts.