Unit 2
Introduction to Data Structures
Dr. Saleh Alhazbi
CMPS303‐Data Structures
Data & Data Structures
What is data?
It is a collection of unprocessed facts that include numbers, texts, or symbols which can be processed by
computers to obtain useful information.
What is a Data Structure?
It is a way of organizing a collection of data items in such a way that computer performs operations on
these data efficiently. Examples of data structures include: arrays, linked lists, trees, stacks, queues, hash
tables, ..etc.
Why do we need to study data structures?
In order to write efficient programs
What is the efficient program?
It is the one that has less cost than other alternatives in terms of space (memory) and time.
To write an efficient program, you should select
good algorithm, and select the most appropriate
data structure.
Why should we care about program’s speed and space
when current computers have high speed and large
memories?
Because data also has grown rapidly, they need to be stored, processed and retrieved
efficiently
Example of huge data
Facebook: 2.6 billion active users (2020)
Every day, half million new users are created. Every minute, 510,000 comments are posted.
Google receives 63,000 search request/ second, means 3.8 million searches per
minute
Tradeoff between time and space
it is usually difficult to develop efficient
program based on the two aspects, it is
common that developer has to tradeoff
between time and space. For example,
reducing time might require more space
and vice versa.
Arrays
An array is a data structure that contains a group of elements of the same data type
Each element , or cell, in an array has an index, which uniquely refers to the value stored in that position.
The length of an array determines the maximum number of things that can be stored in the array
Arrays in Java
Two ways to declare an array in Java:
int [] a={3,1,9,4}; int [] a=new int[5];
Example
Assume we want to store high scores for a game in an array. First we define the GameEntry (name and
score)
We need to build a class (let’s call it Scoreboard) that
uses an array (call it board) to hold these entries.
Adding a New Entry
When adding a new entry, the entries should be maintained ordered from highest to lowest
score.
We need to shift the elements to
put the new one in its proper
position
How many shift operations we
need?
What is the worst case?
What is the best case?
Removing an Entry
When removing an entry, the entries also should be maintained ordered from highest to lowest score.
Assume we want to delete “Paul” , we can’t
have null elements in the middle, so we need
to shift the elements
How many shift operations
we need?
What is the worst case?
What is the best case?
Disadvantages of Arrays
- Fixed Size
1
• It might not be enough to hold the [Link] the system fails.
• It might not be fully utilized to hold information, waste the memory.
2- Programming languages has limitations on the maximum size of the array that can be
defined. Hence, does not work with huge information.
3- To define an array, needed memory must be contiguous not scattered. Hence, even if
more than needed memory is available it is very possible that the array cannot be defined
because the memory is not adjacent.
4-Poor performance:
• Shifting is required when inserting and removing in a sorted array.
• Shifting is required when removing an element from unsorted array.