Why Study Data Structures?
◦ Data structures organize Data
◦ Good choice better program (more efficient program)
◦ Bad choice poor program performance
◦ Changes over time
◦ More powerful computers
◦ More complex applications
◦ More complex tasks
Cont..
Why Study Data Structures?
◦ Characteristics of problem’s solution
◦ Efficiency: a solution is efficient if it solves problem within resource constraints
◦ Time
◦ Space
◦ Cost: the amount of resources a solution will consume
What is Abstract Data Types (ADT)?
◦ Basic definitions
Đ Type: a set of objects
Đ Data item or element: a piece of information or record
Đ Member: a data item is said to be a member of a data type
Đ Simple data item: a data item containing no subparts
Đ Aggregate data item: a data item that may contain several pieces of information
Đ Abstract data type: a type and a collection of operations to manipulate that type
ADT are mathematical abstractions, an ADT only mentions what is to be done, not how.
Introduction to Data Structure
Computer is an electronic machine which is used for data processing and
manipulation.
When programmer collects such type of data for processing, he would require to store
all of them in computers main memory.
In order to make how computer work we need to know
Representation of data in computer.
Accessing of data.
How to solve problem step by step.
For doing all of this task we used Data Structure
Cont..
• Data Structure
– A way to store information
– A scheme for organizing related pieces of
information
• Algorithm
– Method for solving a problem
– Can be represented in any language
What is Data
Structure
A data structure is a
specialized format for
organizing, processing,
retrieving and storing data.
In computer programming,
a data structure may be
selected or designed to
store data for the purpose
of working on it with
various algorithms.
Cont..
What is Data
Structure
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.
examples of Data Structures are arrays, Linked List, Stack, Queue, etc.
Data Structures are widely used in almost every aspect of Computer Science i.e. Operating
System, Compiler Design, Artificial intelligence, Graphics and many more.
Data Structures are the main part of many computer science algorithms as they enable the
programmers to handle the data in an efficient way.
It plays a vital role in enhancing the performance of a software or a program as the main function
of the software is to store and retrieve the user’s data as fast as possible
Cont..
Data Structure
◦ A data structure is a particular way of organizing data in a computer so that it can be used
effectively.
◦ For example, we can store a list of items having the same data-type using the array data
structure.
Cont..
The representation of particular data structure in the main memory of a computer is called as
storage structure.
The storage structure representation in auxiliary memory is called as file structure.
It is define as the way of storing and manipulating data in organized form so that it can be used
efficiently
Data Structure mainly specifies the following four things:
1)organization of data 2)accessing method 3)degree of associativity 4) processing
alternative for
information
Algorithm + Data Structure = Program
Data Structure study Covers the following points
1) Amount of memory require to store
2) Amount of time require to process
3) Representation of data in memory
4) Operations performs on data
Cont..
Data Structure
◦ A data Structure is a physical implementation of an ADT
Ď. Each ADT operation is implemented by one or more subroutines
Ď. Data structures are organizations for data in the main memory
Selecting a Data Structure
◦ Analyze problem
◦ Determine basic operations
◦ Select a data structure
◦ Questions
◦ At what times(s) in the program run do inserts occur
◦ Are deletes allowed?
◦ Is there any Order to data processing?
Why study Algorithms ?
◦ Algorithms solve problems
◦ Good choice more efficient program
◦ Bad choice poor program performance
◦ Impact
◦ Different algorithms perform better on different inputs
◦ Input size can affect the performance
Cont..
Cont..
Algorithm/ Data Structure
◦ Each data structure requires:
◦ Space to store each item, including overhead
◦ Time to perform basic operations
◦ Programming effort
◦ Algorithms are closely related:
◦ Poor data structure choice higher complexity algorithms
◦ Good data structure choice algorithm trivial
Cont..
Algorithms and Programs
◦ Problem: task to be performed
◦ Algorithms: a method or process to solve a problem
◦ Algorithm transforms the input of a problem to its outputs
◦ Algorithm proprieties
1) Must be correct
2) It must be composed of a series of correct steps
3) There can be no ambiguity about which step is next
4) It must be finite in length
5) It must terminate
◦ Program: an instance of an algorithm, written in some programming language.
Types Of
DS
The DS are divided into
two types:
1) Primitive
2) Non primitive
Non primitive divided
into two type
3) Linear DS
4) Non linear DS
Cont..
DATA TYPES
A particular kind of data item, as defined by the values it can take, the Programming
language used, or the operations that can be performed on it.
◦ Primitive Data Structure
◦ Primitive Data Structure are basic structure and directly operated upon by machine
instructions.
◦ Primitive data structures have different representations on different computers.
◦ Integers, floats, character and pointers are example of primitive data structures.
◦ These data types are available in most programming languages as built in type.
Integer: It is a data type which allows all values without fraction part. We can used it for
whole
numbers.
Float: It is a data type which is use for storing fraction numbers.
Character: It is a data type which is used for character values.
Pointer: A variable that hold memory address of another variable are called pointer.
Cont..
Non Primitive Data Type
◦ These are more sophisticated data structures.
◦ These are derived from primitive data structure.
◦ The non – primitive data structures emphasize structuring of a group of homogeneous or
heterogeneous data items.
◦ Example of non – primitive data types are Array, List, and File etc.
◦ A non – primitive data type is further divided into Linear and non – Linear data structure.
Array: An array is a fixed size sequenced collection of elements of the same data type.
List: An ordered set containing variable number of elements is called as List.
File: A file is a collection of logically related information. It can be viewed as a large list of
records consisting of various fields.
Cont..
Linear Data Structures
A linear data structure simply means that it is a storage format
of the data in the memory in which the data are arranged in
contiguous blocks of memory.
Example is the array of characters it represented by one
character after another.
In the linear data structure, member elements form a sequence
in the storage.
There are two ways to represent a linear data structure in
memory.
static memory allocation
dynamic memory allocation
The possible operations on the linear data structure are:
1) Traversing 2) Insertion 3) Deletion 4) searching 5)
sorting
6) merging
Cont..
◦ Example of Linear data structure are Stack and
Queue
Stack
◦ Stack is a data structure in which insertion and
deletion operations are performed at one end
only.
◦ The insertion operation is referred to as ‘PUSH’
and deletion is referred as ‘POP’ operation
◦ Stack is also called as Last In First Out (LIFO)
data structure.
Queue
◦ The data structure which permits the insertion at
one and deletion at another end, known as
Queue.
◦ End at which deletion is occurs is known as
FRONT end and another end at which insertion
occurs is known as REAR end.
◦ Queue is also called as First In First Out (FIFO)
Cont..
Non-Linear Data
Structure
◦ Non linear DS are those data structure in which data
items are not arranged in a sequence.
◦ Example on Non Linear DS are Tree and Graph.
TREE
◦ A Tree can be define as finite data items (nodes) in which
data items are arranged in branches and sub branches
◦ Tree represent the hierarchical relationship between
various elements
Components of ◦ Tree consist of nodes connected by edge, the
represented by circle and edge lives connecting to circle.
Graph
Graph
◦ Graph is collection of nodes (information) and
connecting edges (Logical relation) between nodes.
◦ A tree can be viewed as restricted graph
◦ Graph have many types: 1) Simple graph 2) Mixed graph
3) Multi graph 4) Directed graph 5) Un-directed graph
Cont..
Difference Between Linear and Non Linear Data
Structure
Linear Data Structure Non – Linear Data Structure
◦ Every item is related to its previous ◦ Every item is attached with many
and next item. other items.
◦ Data is arranged in linear sequence. ◦ Data is not arranged in sequence.
◦ Data items can be traversed in a ◦ Data cannot be traversed in a single
single run run.
◦ E.g. Array, Stacks, Linked list, Queue ◦ E.g. Tree, Graph
◦ Implementation is easy. ◦ Implementation is difficult.
Collections
◦ A collection is a structured data type that stores data and provides operations to
manipulate this data (add, remove, and update)
◦ Collection types:
◦ Linear: List of elements where elements follow each other in a linear order (ordered
by position first, second, …, etc. ).
◦ E.g. Grocery list, array
◦ Nonlinear: List of elements which don’t have positional order
◦ E.g. Organization chart, trees and graphs
◦ Collection property such as
◦ Count: number of items in the collection
Cont..
Collection operations
◦ Add: Add a new element to the collection
◦ Insert: Add a new element to the collection at a specific location
◦ Remove: Remove a specific element from the collection
◦ Clear: Remove all element from the collection
◦ Contains: Determine if a specific element is a member of a collection
◦ IndexOf: Determine the index of a specific element in a collection
Direct Access Collections Cont..
◦Array: a collection of elements with the same data type that are
directly accessed via an integer index
◦String: a collection of characters that can be directly accessed
via an index
◦Struct (Structure or record): a composite data type that holds
data that may consist of many different data types
◦E.g.: Student record (num: int, name: string, avg: float)
Cont..
Sequential Access Collections
◦ Is a list that stores its elements in a sequential order (i.e., linear list)
◦ Linear list are not limited by size
◦ Items in linear list are referenced (i.e., can only be accessed by their positions)
◦ Examples: Stacks and Queues
Linear Lis
Cont..
Stack Queue
Queue Operations
Stack operations
Cont..
Hash Table Hierarchical Collections
A Record to be Hashed A Tree Collection
Cont..
Group Collections
◦ A nonlinear collection of items that are UNORDERED.
◦ Examples:
◦ sets,
◦ graphs,
◦ networks
Cont..
Sets
Set collection operations
Cont..
Graphs
The Traveling Salesman Problem
Cont..
Networks
A Network Collection
Operation on Data Structures
Design of efficient data structure must take operations to be performed on the DS into account.
The most commonly used operations on DS are broadly categorized into following types
1. Create: This operation results in reserving memory for program elements. This can be done by
declaration statement Creation of DS may take place either during compile-time or run-time.
2. Destroy: This operation destroy memory space allocated for specified data structure .
3. Selection: This operation deals with accessing a particular data within a data structure.
4. Updation: It updates or modifies the data in the data structure.
5. Searching: It finds the presence of desired data item in the list of data items, it may also find
locations of all elements that satisfy certain conditions.
6. Sorting: This is a process of arranging all data items in a DS in particular order, for example
either ascending order or in descending order.
7. Splitting: It is a process of partitioning single list to multiple list.
8. Merging: It is a process of combining data items of two different sorted list into single sorted
list.
9. Traversing: It is a process of visiting each and every node of a list in systematic manner.
What are Arrays?
Array is a container which can
hold a fix number of items and
these items should be of the same
type.
Most of the data structures make
use of arrays to implement their
algorithms.
•Following are the important terms
to understand the concept of
Array.
Element − Each item stored
in an array is called an element.
1. An array is a container of elements. Index − Each location of an
2. Elements have a specific value and data type, like "ABC", TRUE or FALSE, etc. element in an array has a
3. Each element also has its own index, which is used to access the element. numerical index, which is used to
identify the element.
Cont..
• Elements are stored at
contiguous memory locations.
• An index is always less than
the total number of array
items.
• In terms of syntax, any
variable that is declared as an
array can store multiple
values.
• Almost all languages have the
same comprehension of
arrays but have different
ways of declaring and
initializing them.
• However, three parts will
•Array name: necessary for easy reference to the collection of elements always remain common in all
•Data Type: necessary for type checking and data integrity
the initializations, i.e., array
•Elements: these are the data values present in an array
name, elements, and the data
type of elements.
Cont..
How to access a
specific array
value?
You can access any array item by
using its index
Syntax
arrayName[indexNum]
Example
balance[1]
Here, we have accessed the second value of the array using its index, which is 1.
The output of this will be 200, which is basically the second value of the balance
array.
Cont..
Array Representation
◦ Arrays can be declared in various ways in different languages. For illustration, let's take C array declaration.
