Transcript Document
Vectors
4/10/2016 5:34 PM
Vectors
1
Outline and Reading
The Vector ADT (§5.1.1)
Array-based implementation (§5.1.2)
4/10/2016 5:34 PM
Vectors
2
The Vector ADT
The Vector ADT
extends the notion of
array by storing a
sequence of arbitrary
objects
An element can be
accessed, inserted or
removed by specifying
its rank (number of
elements preceding it)
An exception is
thrown if an incorrect
rank is specified (e.g.,
a negative rank)
4/10/2016 5:34 PM
Main vector operations:
elemAtRank(int r): returns the
element at rank r without
removing it
replaceAtRank(int r, Object o):
replace the element at rank r with
o
insertAtRank(int r, Object o):
insert a new element o to have
rank r
removeAtRank(int r): removes the
element at rank r
Additional operations size() and
isEmpty()
Vectors
3
Applications of Vectors
Direct applications
Sorted collection of objects (elementary
database)
Indirect applications
Auxiliary data structure for algorithms
Component of other data structures
4/10/2016 5:34 PM
Vectors
4
Operation
Output
S
Insert 7 at rank0
-
(7)
Insert 4 at rank 0
-
(4,7)
Return element at
rank 1
7
(4,7)
Insert 2 at rank 2
-
(4,7,2)
Return element at
rank 3
“error”
(4,7,2)
Remove element
at rank 1
-
(4,2)
Insert 5 at rank 1
-
(4,5,2)
Insert 3 at rank 1
-
(4,3,5,2)
Insert 9 at rank 4
-
(4,3,5,2,9)
Return element at
rank 2
5
(4,3,5,2,9)
4/10/2016 5:34 PM
Vectors
5
Array-based Vector
Use an array V of size N
A variable n keeps track of the size of the vector
(number of elements stored)
Operation elemAtRank(r) is implemented in O(1)
time by returning V[r]
V
0 1 2
4/10/2016 5:34 PM
n
r
Vectors
6
Algorithms
Algorithm insertAtRank (r,e):
for i= n -1,n-2, r do
A[i+1] A[i]
Algorithm removeAtRank (r,e):
for i= r, r+1, ...., n-2 do
A[i] A[i+1]
{fill in for the removed element }
{make room for the new element }
n n-1
A[r] e
n n+1
4/10/2016 5:34 PM
Vectors
7
Insertion
In operation insertAtRank(r, o), we need to make
room for the new element by shifting forward the
n - r elements V[r], …, V[n - 1]
In the worst case (r = 0), this takes O(n) time
V
0 1 2
r
n
0 1 2
r
n
0 1 2
o
r
V
V
4/10/2016 5:34 PM
Vectors
n
8
Deletion
In operation removeAtRank(r), we need to fill the
hole left by the removed element by shifting
backward the n - r - 1 elements V[r + 1], …, V[n - 1]
In the worst case (r = 0), this takes O(n) time
V
0 1 2
o
r
n
0 1 2
r
n
0 1 2
r
V
V
4/10/2016 5:34 PM
Vectors
n
9
Performance
In the array based implementation of a Vector
The space used by the data structure is O(n)
size, isEmpty, elemAtRank and replaceAtRank run in
O(1) time
insertAtRank and removeAtRank run in O(n) time
If we use the array in a circular fashion,
insertAtRank(0) and removeAtRank(0) run in
O(1) time
In an insertAtRank operation, when the array
is full, instead of throwing an exception, we
can replace the array with a larger one
4/10/2016 5:34 PM
Vectors
10
Time
Function
Time
size
O (1)
isEmpty
O (1)
elementAtrank
O (1)
replaceAtRank
O (1)
InsertAtRank
O (n)
removeAtRank
O (n)
4/10/2016 5:34 PM
Vectors
11