Data Structure
Introduction
Data structure is a collection of related information that is used to store and manage data. All data structures have associated algorithms to manage the data structure while maintaining its properties.
In other words, a data structure is a way of organising all data items that considers not only the elements stored but also their relationship to each other.
Data is a programming construct used to implement an ADT. A data structure that is implementing an ADT consists of collection of variables for storing the data specified in the ADT and the algorithms for implementing the operations specified in ADT.
Abstract Data Types (ADT)
Abstract data type is a mathematical model or concept that defines a data type logically.
It specifies a set of data and collection of operations that can be performed on that data.
The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations.
The process of providing only the essentials and hiding the details is known as abstraction. We can think of ADT as a black box which hides the inner structure and design of the data type.
Given data structures are known as non-primitive data structures that emphasize on structuring of a group of homogeneous(same type) or heterogeneous (different type) data items.
C++ supports some data structures, such as
- arrays
- linked lists
- stacks
- queues
- trees
- graphs
Most of the data structures need pointer for their implementation.
To implement these data structures in C++, we create classes because a class is grouping of object that have common methods, operations, relationship and attributes. For example, vehicle is a class, where speed, acceleration and brake are common attributes.
Data Structure Operations
The data which is stored in our data structures are processed by certain set of operations. While selecting a particular data structure for the application we choose a given data structure largely on the frequency with which specific operation are performed.
The following operations we can perform on the data structures:
- Traversing:
- Searching:
- Inserting:
- Deleting:
- Sorting:
- Merging:
Accessing each data exactly once in the data structure so that each data item is traversed or visited.
Finding the location of data within the data structure which satisfy the searching condition or the criteria.
Adding a new data in the data structure is referred as Insertion.
Removing a data from the data structure is referred as deletion.
Arranging the data in some logical order for example, in numerical increasing order or alphabetically.
Combining the data of two different sorted files intoa single sorted file.
