CH7. LIST AND ITERATOR ADTS
嚜澧H7.
LIST AND ITERATOR ADTS
ACKNOWLEDGEMENT: THESE SLIDES ARE ADAPTED FROM SLIDES PROVIDED WITH
DATA STRUCTURES AND ALGORITHMS IN JAVA, GOODRICH, TAMASSIA AND
GOLDWASSER (WILEY 2016)
LISTS
LIST ADT
?
?
A List is a general storage structure where items are accessed by index
Main operations
?
?
?
?
?
Element set(Index i, Element e) 每 Replaces the element of the list at index ? with element ?,
and returns the old element.
add(Index i, Element e) 每 Inserts a new element into the list so that it has index ?, thus moving all
subsequent elements to one index later in the list
Element remove(Index i) 每 Removes and returns the element at index ?, thus moving all subsequent
elements to one index earlier in the list.
Auxiliary operations
?
?
?
Element get(Index i) 每 Returns the element of the list at index ?.
size() 每 return the number of elements in the list
isEmpty() 每 return true if the list is empty
An error condition occurs if any index is outside of the range [0, size()?1] (except for add
which can add at index size()
EXAMPLE
? Follow along as we modify an initially empty list with the following operations
?
?
?
?
?
?
?
?
?
?
?
?
?
Operation
Return/Error
List Contents
add(0, A)
add(0, B)
get(1)
set(2, C)
add(2, C)
add(4, D)
remove(1)
add(1, D)
add(1, E)
get(4)
add(4, F)
set(2, G)
get(2)
每
每
A
Error
每
Error
A
每
每
Error
每
D
G
(A)
(B, A)
(B, A)
(B, A)
(B, A, C)
(B, A, C)
(B, C)
(B, D, C)
(B, E, D, C)
(B, E, D, C)
(B, E, D, C, F)
(B, E, G, C, F)
(B, E, G, C, F)
ARRAY LISTS
? An obvious choice for implementing the list ADT is to use an array, ?, where
? ? stores (a reference to) the element with index ?.
? With a representation based on an array ?, the get(?) and set(?,
?)
methods are easy to implement by accessing ?[?] (assuming ? is a legitimate
index).
??1
0
?
0 1 2
i
n
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- cs106a stanford handout 49 fall 2004 05 nick parlante
- chapter 19 java data structures
- ch7 list and iterator adts
- arrays and arraylists
- big o arraylist carnegie mellon university
- arrays stanford university
- arraylist reading 10
- arraylist in java
- java arraylist copyright © tutorialspoint
- building java programs chapter 10
Related searches
- stock list and price
- values list and definitions
- career list and salary
- autoimmune disorders list and symptoms
- business careers list and salaries
- 4th grade vocabulary list and definitions
- nyse stock list and price
- aarp rx drug list and prices
- vocabulary list and definitions printable
- stem words list and meaning
- college majors list and description
- personal core values list and the definitions