Scribd
Upload
3 views

CUITM205 Data Structures 2

Data structures are systematic ways to organize, manage, and store data for efficient access and modification. They address common problems in applications such as data search, processor speed, and handling multiple requests. Different types of data structures, including static and dynamic, have specific characteristics and advantages, making them suitable for various applications.

Uploaded by

EPHRAIM S KUNAKA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
3 views

CUITM205 Data Structures 2

Data structures are systematic ways to organize, manage, and store data for efficient access and modification. They address common problems in applications such as data search, processor speed, and handling multiple requests. Different types of data structures, including static and dynamic, have specific characteristics and advantages, making them suitable for various applications.

Uploaded by

EPHRAIM S KUNAKA
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 16

Data Structures and Algorithms

CUITM205
What is a Data structure
• Data structure is a data organisation ,management and storage
format that enables efficient access and modification of data

• Data Structure is a systematic way to organize data in order to


use it efficiently.

• Data structure is used to denote a particular way of organizing


data for particular types of operation
What is a Data structure
Terms are the foundation terms of a data structure.
• Interface − Each data structure has an interface.
Interface represents the set of operations that a data
structure supports. An interface only provides the list
of supported operations, type of parameters they can
accept and return type of thesemoperations.
• Implementation − Implementation provides the
internal representation of a data structure.
Implementation also provides the definition of the
algorithms used in the operations of the data structure
Why do we need Data Structures
As applications are getting complex and data rich, there are three common problems that
applications face now-a-days.

• Data Search − Consider an inventory of 1 million(106) items of a store. If the


application is to search an item, it has to search an item in 1 million(106) items every
time slowing down the search. As data grows, search will become slower.

• Processor Speed − Processor speed although being very high, falls limited if the data
grows to billion records.

• Multiple Requests − As thousands of users can search data simultaneously on a web


server, even the fast server fails while searching the data.

To solve the above-mentioned problems, data structures come to rescue. Data can be
organized in a data structure in such a way that all items may not be required to be
searched, and the required data can be searched almost instantly.
Why do we need Data Structures
• Each data structure allows data to be stored in
a particular manner
• Data structures allow efficient data search and
retrieval
• Specific data structures work for specific
problems
• It allows management of large amounts of data
such as large databases and indexing services
such as hash tables
Characteristics of a Data Structure
• Correctness − Data structure implementation
should implement its interface correctly.
• Time Complexity − Running time or the
execution time of operations of data structure
must be as small as possible.
• Space Complexity − Memory usage of a data
structure operation should be as little as
possible.
Types of Data Structures
• Linear -the data items are arranged in a linear
sequence. Example: Array, Queue ,Stack etc

• Non-linear-the data items are not in


sequence. Example: Tree, Graph
Types of Data Structures
• Homogeneous -all the elements are of
same type. Example: Array

• Non-homogeneous-the elements may or


may not be of the same type
Types of Data Structures
• Static data structures are those whose sizes
and structures associated memory locations
are fixed, at compile time. Example: Array

• Dynamic structures are those which expands


or shrinks depending upon the program need
and its execution. Also, their associated
memory locations changes. Example: Linked
List created using pointers
Static data structure
• In Static data structure the size of the
structure is fixed. The content of the data
structure can be modified but without
changing the memory space allocated to it.
• Eg Array
Static Data Structure
Advantages of Static Data Structures
• Easy to check for overflow
• Memory allocation is fixed and therefore there is no problem with adding
and removing data items.
• Easy to program as there is no need to check for data structure size at any
given time/point
• An array allows random access and is faster to access elements than in other
data structures
Disadvantages of Static Data Structures
• Programmer has to estimate maximum amount of space needed, which may
be difficult
• Can waste a lot of space if some space is left with no data entered into it.
• Adding, removing and modifying elements is not directly possible. If done, it
requires a lot of resources like memory.
Dynamic Data Structure
• In Dynamic data structure the size of the
structure in not fixed and can be modified
during the operations performed on it.
Dynamic data structures are designed to
facilitate change of data structures in the run
time
• Eg Tree , Linked List
Dynamic Data Structure
Advantages of Dynamic Data Structures
• Only uses the space that is needed at any time
• Makes efficient use of the memory, no spaces lie idle at any given
point
• Storage no-longer required can be returned to the system for
other uses.
• Does not allow overflow
Disadvantages of Dynamic Data Structures
• Complex and more difficult to program as software needs to keep
track of its size and data item locations at all times
• Can be slow to implement searches
• A linked list only allows serial access
Abstract Data Type
• is special kind of datatype, whose behavior is
defined by a set of values and set of
operations.
• The keyword “Abstract” is used as we can use
these datatypes, we can perform different
operations. But how those operations are
working that is totally hidden from the user.
The ADT is made of primitive datatypes, but
operation logics are hidden.
Abstract Data Type
• Some examples of ADT are Stack, Queue, List etc..
• Stack −
– isFull(), This is used to check whether stack is full or not
– isEmpty(), This is used to check whether stack is empty or
not
– push(x), This is used to push x into the stack
– pop(), This is used to delete one element from top of the
stack
– peek(), This is used to get the top most element of the stack
– size(), this function is used to get number of elements
present into the stack
Abstract Data Type

• Queue −
– isFull(), This is used to check whether queue is full or not
– isEmpty(), This is used to check whether queue is empty or not
– insert(x), This is used to add x into the queue at the rear end
– delete(), This is used to delete one element from the front end of the queue
– size(), this function is used to get number of elements present into the queue

• List −
– size(), this function is used to get number of elements present into the list
– insert(x), this function is used to insert one element into the list
– remove(x), this function is used to remove given element from the list
– get(i), this function is used to get element at position i
– replace(x, y), this function is used to replace x with y value

You might also like