10/11/2018
Data Structure #2: Arrays
CS221N, Data Structures
The Array
Most commonly used data structure
Common operations
Insertion
Searching
Deletion
How do these differ for an ‘ordered array’?
How do these differ for an array which does not allow
duplicates?
1
10/11/2018
Array Storage
An array is a collection of data of the same type
Stored linearly in memory:
Collections
Collection: is a structured data type, that stores
data and provide operations for adding, removing,
updating data in the collection.
2
10/11/2018
Types of Data Structures
Linear DS
Linear DS is a list of elements where one
element follows the previous element.
Elements are normally ordered by position
(1st, 2nd, 3rd ….).
e.g. (Arrays, linkedlists, Stacks…..).
Types of Data Structures
Non-Linear DS
Non-Linear DS is a list of elements where
one element do not depend on the previous
element(s).
Hold elements that do not have positional
order.
e.g. (Trees).
3
10/11/2018
How to access DSs
Direct Access
Sequential Access
4
10/11/2018
Remember, value vs. reference…
In Java:
Data of a primitive type is a ____________.
All objects are ________________.
Java arrays are also considered references.
Defining a Java Array
Say, of 100 integers:
int[] intArray;
intArray = new int[100];
We can combine these statements:
Or, change the [] to after the variable name
What do the [] signify?
10
5
10/11/2018
We said an array was a reference…
That means if we do this:
int[] intArray;
intArray = new int[100];
What exactly does intArray contain? Let’s look internally.
11
The Size
Size of an array cannot change once it’s been declared:
intArray = new int[100];
But, one nice thing is that arrays are objects. So you can
access its size easily:
int arrayLength = intArray.length;
Getting an array size is difficult in many other languages
12
6
10/11/2018
Access
Done by using an index number in square brackets:
int temp = intArray[3]; // Gets 4th element
intArray[7] = 66; // Sets 8th element
How do we access the last element of the array, if we don’t
remember its size?
What range of indices will generate the IndexOutOfBounds
exception?
The index is an offset. Let’s look at why.
13
Initialization
What do the elements of this array contain:
int[] intArray = new int[100];
How about this one:
BankAccount[] myAccounts = new BankAccount[100];
What happens if we attempt to access one of these values?
int[] intArray = {0, 3, 6, 9, 12, 15, 18, 21, 24,
27};
Automatically determines the size
Can do this with primitives or objects
14
7
10/11/2018
Look at a book example…
See the example on p. 41-42, where we do the following:
Insert 10 elements into an array of integers
Display them
Find item with key 66
Delete item with key 55
Display them
Ask ourselves:
How could we make the initialization shorter?
How could we save declaring nElems?
15
This did not use OOP
So our next task will be to divide it up (p. 45)
What will we want for the array class? Let’s think about the
purpose of classes. They have data, and functions to manipulate
that data.
So in this case, what will our data be?
For functions, we’ll provide:
A constructor which takes a size and initializes the array
A function to retrieve a single element
A function to set a single element
And then modify main()
16
8
10/11/2018
Abstraction
This illustrates the concept of abstraction
The way in which an operation is performed inside a class is
invisible
Client of HighArray performs more complex operations
through simple method invocations
Never directly accesses the private data in the array
Now we can reuse HighArray much easier
Note – a client does not even really know about the member
array!
Hint, we’ll see later how we can change it.
17
