Scribd
Upload
17 views

3_Introduction to Data Structures

The lecture introduces data structures and their organization, focusing on elementary data types, user-defined data types, and abstract data types (ADTs). It explains the implementation of ADTs using various data structures like arrays and linked lists, and distinguishes between linear and non-linear data structures. By the end of the course, students will learn to relate different data structures to specific problem-solving applications.

Uploaded by

Lakshmi Kanth Reddy Blkreddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
17 views

3_Introduction to Data Structures

The lecture introduces data structures and their organization, focusing on elementary data types, user-defined data types, and abstract data types (ADTs). It explains the implementation of ADTs using various data structures like arrays and linked lists, and distinguishes between linear and non-linear data structures. By the end of the course, students will learn to relate different data structures to specific problem-solving applications.

Uploaded by

Lakshmi Kanth Reddy Blkreddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 9

19CCE202 Data Structures and Algorithms

LECTURE 3 – INTRODUCTION TO DATA STRUCTURES

Dr. R. Ramanathan
Associate Professor
Department of Electronics and Communication Engineering
Amrita School of Engineering, Coimbatore
r_ramanathan@cb.amrita.edu
Objective
To understand the data organization and types to explore the data structures; to work with
abstract data types .

Key concepts
• Elementary data organization [CO01]
• Data types [CO01]
• Data structures [CO01]
• Abstract data type [CO01]
Elementary data • Data item
organization • Elementary items
• Group items
• Logical and mathematical
• Hierarchy
description of a structure
• Fields
• Implementation of a
structure on a computer • Record
• Quantitative analysis of a • Files
structure • Attributes
– Memory • Entity / entity set
– Processing time • Information
• Key / primary key
• Fixed / variable length records
System-defined data types (Primitive data types)
Data types • Data types that are defined by system are called
primitive data types.
A data type in a programming • Eg. int, float, char, double, bool, etc.
language is a set of data with • The number of bits allocated for each primitive data
predefined values. type depends on the programming languages, the
compilerand the operating system.
Examples of data types are:
integer, floating point, unit
User defined data types
number, character, string, etc.
• If the system-defined data types are not enough, then
• System-defined data types
most programming languages allow the users to define
(also called Primitive data their own data types, called user – defined data types.
types)
• This gives more flexibility and comfort in dealing with
• User-defined data types. computer memory
Abstract Data Type Examples of ADTs include list, stack, queue, set, tree,
graph, etc.
(ADT)
An ADT is a set of elements with a collection of well defined operations.
– The operations can take as operands not only instances of the ADT but other types of
operands or instances of other ADTs.
– Similarly results need not be instances of the ADT
– At least one operand or the result is of the ADT type in question.
A “Queue” is an ADT, can be implemented using data
Data Structures structures such as array, linked list, etc.

An implementation of an ADT is a translation into statements of a programming


language,
– the declarations that define a variable to be of that ADT type
– the operations defined on the ADT (using procedures of the programming language)
An ADT implementation chooses a data structure to represent the ADT.
– Each data structure is built up from the basic data types of the underlying programming
language
– uses the available data structuring facilities: arrays, records (structures in C), pointers,
files, sets, etc.
• Linear data structures: Elements are accessed in a
Data structures sequential order but it is not compulsory to store all
elements sequentially.
 Data structure is a Examples:
particular way of storing – Linked Lists,
and organizing data in a
– Stacks
computer so that it can be
used efficiently. – Queues.
 A data structure is a special • Non – linear data structures: Elements of this data
format for organizing and structure are stored/accessed in a non-linear order.
storing data. Examples:
– Trees
– graphs.
Abstract Data Types (ADTs) - revisited

• all primitive data types (int, float, etc.) support basic operations such as addition and
subtraction - The system provides the implementations for the primitive data types.
• For user-defined data types we also need to define operations - The implementation
for these operations can be done when we want to actually use them.
• In general, user defined data types are defined along with their operations.
• To simplify the process of solving problems, we combine the data structures with
their operations and we call this Abstract Data Types (ADTs).

An ADT consists of two parts:


1. Declaration of data
2. Declaration of operations
Abstract Data Types (ADTs) - revisited

• Commonly used ADTs include: Linked Lists, Stacks, Queues, Priority Queues,
Binary Trees, Dictionaries, Disjoint Sets (Union and Find), Hash Tables, Graphs, and
many others.
• While defining the ADTs do not worry about the implementation details. They come
into the picture only when we want to use them.
• Different kinds of ADTs are suited to different kinds of applications, and some are
highly specialized to specific tasks.
• By the end of this course, we will go through many of them and you will be in a
position to relate the data structures to the kind of problems they solve.

You might also like