What is Data Structure ?
Data structure is a way to store and organize data in memory so that it can be used efficiently. Here, we have used the word efficiently, which in terms of both the space and time. The data structure is not any programming language like C, C++, java etc. Data Structure can be defined as the group of data elements which provides an efficient way of storing and organizing data in the computer so that it can be used efficiently. Some examples of Data Structures are arrays, linked lists, stack, queue etc.
To structure the data in memory, 'n' number of algorithms were proposed, and all these algorithms are known as Abstract data types. These abstract data types are the set of rules. We require some data structure to implement a particular ADT. An ADT tells what is to be done and data structure tells how it is to be done.
Need of Data Structure
- Data Structure are used in almost every program or software system.
- Specific data structures are essential components of many algorithms, and make possible the management of huge amounts of data, such as large integrated collection of databases.
- It tells us how data can be stored and accessed in its elementary level.
- Provide operation on large group of data, such as adding an item, looking up highest priority item.
- Provide fast searching and sorting of data.
- Provide a means to manage huge amount of data efficiently.
Advantages of Data Structures
The following are the advantages of a data structure:
- Efficiency: If the choice of a data structure for implementing a particular ADT is proper, it makes the program very efficient in terms of time and space.
- Reusability: The data structure provides reusability means that multiple client programs can use the data structure.
- Abstraction: The data structure specified by an ADT also provides the level of abstraction. The client cannot see the internal working of the data structure, so it does not have to worry about the implementation part. The client can only see the interface.
Basic Terminology
Data Structures are the building blocks of any program or the software. Choosing the appropriate data structure for a program is the most difficult task for a programmer.
Data
Data can be defined as an elementary value or the collection of values. In computer's storage, data is a series of bits (binary digits) that can have the value as one or zero. Examples: student names, enrolment number, addresses, etc.
Group Items
Data Items that can be divided into sub-items are called group items. Example: name of a person is a group item because it can be divided into three three sub-items namely; first name, middle name and last name.
Elementary Items
Data Items that cannot be divided into sub-items are called group items. Example: roll number of a student.
Data Type
A data type is a feature of data which tells the compiler or interpreter how the programmer intends to use the data. It can be categorized in two ways namely primitive data type and composite or non-primitive data type.
Variable
A variable is a container that stores a value. A variable is a name of memory location and used to store data.
Record
Record can be defined as the collection of various data items. The elements of records are usually called fields. Each field may have a different type.
File
A file is a collection of various records of the entities in a given entity set.
Entity and Attribute
A single unique object that represents data or which may be assigned some value. Attribute is the property that describes an entity.
Entity Set
An entity set is a set of entities of the same type.
Field
Field is a single elementary unit of information representing the attribute of an entity.
Database
Collection of information in permanent storage for faster retrieval and updation.
Data Warehouse
Management of huge data of legacy data (the data we keep at a different place from our fresh data in the database to make the process of retrieval and updation fast) for better analysis.
Big Data
Analysis of too large or complex data, which cannot be dealt with the traditional data processing applications.
Types of Data Structure
Primitive Data Structure
The primitive data structures are primitive data types. The int, char, float, double and pointer are primitive data structures that can hold a single value.
Linear Data Structure
The arrangement of data in a sequential manner is known as a linear data structure. The data structure used for this purpose are Arrays, stacks etc. In these data structures, one element is connected to only one another element in a linear form. In linear data structures, the elements are stored in non-hierarchical way where each elements has the successors and predecessors except the first and last element.
Arrays
An array is a collection of similar type of data items and each data item is called an element of an array. The data type of the element may be any valid data type like char, int, float or double.
The elements of array share the same variable name but each one carries a different index number known as subscript. The array can be one dimensional, two dimensional, or multidimensional.
Linked Lists
Linked list is a linear data structure which 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
Stack is a linear list in which insertion and deletions are allowed only at one end, called top. A stack is an abstract data type (ADT), can be implemented in most of the programming languages.
Queue
Queue is a linear list in which elements can be inserted only at one end called rear and deleted only at the other end called front. It is an abstract data structure, similar to stack. Queue is opened at both end therefore it follows First-In-First-Out (FIFO) methodology for storing the data items.
Non-Linear Data Structure
When one element is connected to the 'n' number of elements known as a non-linear data structure. This data structure does not form a sequence i.e. each item or element is connected with two or more than items in a non-linear arrangement. In this case, the elements are arranged in a random manner.
Trees
Trees are multilevel data structures with a hierarchical relationship among its elements known as nodes. The bottommost nodes in the hierarchy are called leaf node while the topmost node is called root node. Each node contains pointers to point adjacent nodes.
Graphs
Graphs can be defined as the pictorial representation of the set of elements connected by the links known as edges. A graph is different from tree in the sense that a graph can have cycle while a tree can not have the one.
Other Types
Static Data Structure
It is a type of data structure where the size is allocated at the compile time. Therefore, the maximum size is fixed.
Dynamic Data Structure
It is a type of data structure where the size is allocated at the run time. Therefore, the maximum size is flexible.
Homogenous
All the elements are of same data type. Example: Array.
Non-Homogenous
The elements may or may not be of same data type. Example: Structures.
Major Operations
The major or the common Operations that can be performed on the data structure are:
- Traversing: It means to access data item in data structure exactly once so that it can be processed.
- Searching: We can search for any element in a data structure.
- Sorting: We can sort the elements of a data structure either in ascending or descending order.
- Insertion: We can also insert a new element in a data structure.
- Updation: We can also update the element, i.e. we can replace the element with another element.
- Deletion: We can also perform the delete operation to remove the element from the data structure.
- Merging: Logical arrangement formed from combination two lists of sorted data.
Comments
Post a Comment