Transcript INroduction

Introduction to
Data Structures
Prepared by:
Eng. Ahmed & Mohamed Taha
Copyright © Wondershare Software
Agenda
 Data Structures and Algorithms.
 Characteristics of Data Structures.
 Abstract Data Types.
 General form of any Data structure
Company Logo
Copyright © Wondershare Software
Data Structures
 A data structure is an arrangement of data in a computer's
memory or even disk storage.
 An example of several common data structures are:
 arrays
 linked lists
 Queues
 Stacks
 binary trees
 hash tables.
 Algorithms, on the other hand, are used to manipulate the
data contained in these data structures such as searching
and sorting algorithms.
Company Logo
Copyright © Wondershare Software
Algorithms
 Many algorithms apply directly to a specific data structures. When
working with certain data structures you need to know how to
insert new data, search for a specified item, and deleting a specific
item.
 Commonly used algorithms are useful for:

Searching for a particular data item (or record).

Sorting the data. There are many ways to sort data. Simple
sorting, Advanced sorting

Iterating through all the items in a data structure. (Visiting
each item in turn so as to display it or perform some other
action on these items)
Company Logo
Copyright © Wondershare Software
Characteristics of Data Structures
Data Structure
Advantages
Disadvantages
Quick inserts
Fast access if index known
Slow search
Slow deletes
Fixed size
Faster search than
unsorted array
Slow inserts
Slow deletes
Fixed size
Stack
Last-in, first-out LIFO
access
Slow access to other items
Queue
First-in, first-out FIFO
access
Slow access to other items
Quick inserts
Quick deletes
Slow search
1
Array
2
Ordered Array
3
4
5
Linked List
6
Binary Tree
Company Logo
Quick search
Quick inserts
Quick deletes
(If the tree remains
balanced)
Deletion algorithm is complex
Copyright © Wondershare Software
Characteristics of Data Structures
Data Structure
7
Red-Black Tree
8
2-3-4 Tree
9
Hash Table
10
Advantages
Quick search
Quick inserts
Quick deletes
(Tree always remains
balanced)
Quick search
Quick inserts
Quick deletes
(Tree always remains
balanced)
(Similar trees good for
disk storage)
Very fast access if key is
known
Quick inserts
Heap
Quick inserts
Quick deletes
Access to largest item
Graph
Best models real-world
situations
11
Company Logo
Cont.
Disadvantages
Complex to implement
Complex to implement
Slow deletes
Access slow if key is not known
Inefficient memory usage
Slow access to other items
Some algorithms are slow and very
complex
Copyright © Wondershare Software
A red-black Tree
A red-black tree is a binary search tree where each node has a color attribute,
the value of which is either(red or black).
In addition to the ordinary requirements imposed on binary search trees, the
following additional requirements apply to red-black trees:
1.A node is either red or black.
2.The root is black. (This rule is sometimes omitted from other definitions.
Since the root can always be changed from red to black but not necessarily
vice-versa this rule has little effect on analysis.)
3.All leaves are black.
4.Both children of every red node are black.
5.Every simple path from a given node to any of its descendant leaves
contains the same number of black nodes.
Company Logo
Copyright © Wondershare Software
A red-black Tree Example
Company Logo
Cont.
Copyright © Wondershare Software
Abstract Data Types (ADT)
 An Abstract Data Type (ADT) is more a way of looking at a data structure:
focusing on what it does and ignoring how it does its job.
 A stack or a queue is an example of an ADT. It is important to understand that
both stacks and queues can be implemented using an array.
 It is also possible to implement stacks and queues using a linked list. This
demonstrates the "abstract" nature of stacks and queues: how they can be
considered separately from their implementation.
 To best describe the term Abstract Data Type, it is best to break the term down
into "data type" and then "abstract".
 data type: a data item with certain characteristics and the permissible
operations on that data. An “int”, for example, can contain any whole-number
value. It can also be used with the operators +, -, *, and /. understanding the
type means understanding what operations can be performed on it.
 Abstract: The word abstract in our context stands for "considered apart from the
detailed specifications or implementation“. Consider for example the stack class.
The end user knows that push() and pop() (amoung other similar methods)
exist and how they work. The user doesn't and shouldn't have to know how
push() and pop() work, or whether data is stored in an array, a linked list, or
some other data structure like a tree.
Company Logo
Copyright © Wondershare Software
General form of any Data structure
Data structure operations
Insert item
function
Company Logo
Delete item
function
Search for an
item function
Copyright © Wondershare Software
Thank you !
Copyright © Wondershare Software