Data Structures
UNIT-1
1.Definition :
Data Structure is a way to store and organize data in a computer so that it can be used
efficiently. The idea is to reduce the space and time complexities of different tasks.
The data structure is not any programming language like C, C++, java, etc. It is a set of
algorithms that we can use in any programming language to structure the data in the memory.
Data structures are used in various fields such as:
● Operating system
● Graphics
● Computer Design
● Blockchain
● Genetics
● Image Processing
● Simulation etc.
2.Need for Data Structure
✔ It gives different level of organization data.
✔ It tells how data can be stored and accessed in its elementary level.
✔ Provide operation on group of data, such as adding an item, looking up highest priority
item. Provide a means to manage huge amount of data efficiently.
✔ Provide fast searching and sorting of data.
3.Advantages of Data structures
1. 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.
2. Reusability: The data structure provides reusability means that multiple client
programs can use the data structure.
3. 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.
4.Basic Terminology: Elementary Data Organization:
Data: Data are simply values or sets of values.
Data items: Data items refers to a single unit of values.
Attribute and Entity: An entity represents the class of certain objects. it contains various
attributes. Each attribute represents the particular property of that entity.
Ex: student
Attributes- Names, Age, Sex, SSN
Values- RohlandGail, 34, F, 134-34-5533
, Field is a single elementary unit of information representing an attribute of an entity.
Record is the collection of field values of a given entity.
File is the collection of records of the entities in a given entity set.
Abstract Data Type(ADT):
✔ In An abstract data type (ADT) is a collection of values and a set of operations without
specifying its implementation.
✔ For example in Array ADT set of values are index and item & set of operations are
create(),retrieval() and store().
✔ The purpose of the ADT is to hide the implementation details of a data structure, thus
improving software maintenance, reuse and portability.
✔ The developers of ADT will adapt changing requirements and save time.
✔ The users of ADT are concerned with the interface, but not the implementation.
✔ The different ADTs given by
⮚ String ADT, List ADT, Stack (last-in, first-out) ADT,
⮚ Queue (first-in, first-out) ADT
⮚ Binary Search Tree ADT etc
Example:
⮚ A List ADT contains operations known as add element, remove element, etc.
⮚ A List ADT can be represented by an array-based implementation or a linked-list based
implementation. In this the linked-list based implementation is so commonly used.
⮚ Similarly, a Binary Search Tree ADT can be represented in different ways with the
same operations known as insert, remove, display, etc.
5.CLASSIFICATION OF DATA STRUCTURES
Data structures are generally classified into
UNIT-1
1.Definition :
Data Structure is a way to store and organize data in a computer so that it can be used
efficiently. The idea is to reduce the space and time complexities of different tasks.
The data structure is not any programming language like C, C++, java, etc. It is a set of
algorithms that we can use in any programming language to structure the data in the memory.
Data structures are used in various fields such as:
● Operating system
● Graphics
● Computer Design
● Blockchain
● Genetics
● Image Processing
● Simulation etc.
2.Need for Data Structure
✔ It gives different level of organization data.
✔ It tells how data can be stored and accessed in its elementary level.
✔ Provide operation on group of data, such as adding an item, looking up highest priority
item. Provide a means to manage huge amount of data efficiently.
✔ Provide fast searching and sorting of data.
3.Advantages of Data structures
1. 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.
2. Reusability: The data structure provides reusability means that multiple client
programs can use the data structure.
3. 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.
4.Basic Terminology: Elementary Data Organization:
Data: Data are simply values or sets of values.
Data items: Data items refers to a single unit of values.
Attribute and Entity: An entity represents the class of certain objects. it contains various
attributes. Each attribute represents the particular property of that entity.
Ex: student
Attributes- Names, Age, Sex, SSN
Values- RohlandGail, 34, F, 134-34-5533
, Field is a single elementary unit of information representing an attribute of an entity.
Record is the collection of field values of a given entity.
File is the collection of records of the entities in a given entity set.
Abstract Data Type(ADT):
✔ In An abstract data type (ADT) is a collection of values and a set of operations without
specifying its implementation.
✔ For example in Array ADT set of values are index and item & set of operations are
create(),retrieval() and store().
✔ The purpose of the ADT is to hide the implementation details of a data structure, thus
improving software maintenance, reuse and portability.
✔ The developers of ADT will adapt changing requirements and save time.
✔ The users of ADT are concerned with the interface, but not the implementation.
✔ The different ADTs given by
⮚ String ADT, List ADT, Stack (last-in, first-out) ADT,
⮚ Queue (first-in, first-out) ADT
⮚ Binary Search Tree ADT etc
Example:
⮚ A List ADT contains operations known as add element, remove element, etc.
⮚ A List ADT can be represented by an array-based implementation or a linked-list based
implementation. In this the linked-list based implementation is so commonly used.
⮚ Similarly, a Binary Search Tree ADT can be represented in different ways with the
same operations known as insert, remove, display, etc.
5.CLASSIFICATION OF DATA STRUCTURES
Data structures are generally classified into
