Exam 2 Flashcards
An array is an indexed structure:
elements may be accessed in any order using subscript
elements can be accessed in sequence using a loop that increments the subscript
With Java arrays object , you cannot
increase or decrease its length (length is fixed )
insert an element at a specified position
remove an element at a specified position
A _____ is a collection of elements, each with a position
list
In Java, the methods to be implemented by lists are defined in the ____ interface
List
Classes that implement the List interface provide the functionality of an array and offer several operations :
Obtain an element at a specified position
Replace an element at a specified position
Find a specified target value
Add an element at either end a
Remove an element from either end
Insert or remove an element at any position
Traverse the list
The simplest class that implements the List interface
ArrayList class
Use an ArrayList class when:
you will be adding new elements to the end of a list
you need to access elements quickly in arbitrary order
How do you declare a List “object” whose elements will reference String objects :
List myList = new ArrayList();
ArrayList is empty and has a default capacity of:
10 elements
In an ArrayList, you cannot access an element using a bracket index as you can with arrays (array[1]).
Instead use _____ method.
get()
How to search an ArrayList to get location
.indexOf()
List myList new ArrayList <>() ; language feature called:
generics
The statement creates a List of Strings; only references of type String can be stored in the list
Generic collections
In generic collection, String in this statement is called a:
type parameter
The _______________ sets the data type of all objects stored in a collection
type parameter
The general declaration for generic collection is:
CollectionClass ab1e= new 1ass<>() ;
In a generic collection The indicates a:
type parameter
Adding a noncompatible type to a generic collection will generate an error during:
compile time
The elements of a list can be of any type, including your own classes :
List inventory new ArrayList (); = new ArrayList();
In order to use _______ with a List of user-defined objects, there must be a way to determine when two objects are equal
indexof
indexOf is done by overriding the ______ method inherited from ______
equals
object
The equals method has a parameter of type:
Object
How to use Object.equals
public boolean equals (Object other)
What does Object.equals do?
Compares two references to determine if they refer to the same object:
An Object.equals method class must _____________ for the comparison to be meaningful
Override equals
How do you override an equals() in computer class?
@Override
public boolean equals (Object obj)
{
if (obj instanceof Computer)
{
Computer other = (Computer) obj:
return computePower() == other.computePower
}
(); return false ;
}Internally, the elements of an ArrayList are stored in an array. Three variables are needed:
theData : An array to hold the elements capacity : Physical size of array
size : Number of data items in the list
We have two add methods:
One will append at the end of the list
The other will insert an item at a specified position
Implementing add (String anEntry), If size is less than capacity, then to append a new item:
insert the new item at the position indicated by the value of size
increment the value of size
return true to indicate successful insertion
To insert into the middle of the array, the values at the insertion point are shifted over to make room, beginning at the end of the array and proceeding in the indicated order
Implementing add (int index, String anEntry)
When an item is removed , the items that follow it must be moved
________ to close the gap
forward
Creates a new array that is twice the size of the current array and then copy the contents of the new array
reallocate Method
Single-linked ArrayList is limited because
It’s add and remove method require a loop to shift elements
_________ is useful for inserting and removing at arbitrary locations without shifting elements, regardless of the size of the list
linked list
In a linked list, instead of using an array , each element is stored in a ______ and linked to the ______ element
node
next
A LinkedList object can be used anywhere an ArrayList is used :
List < String > myList = new Linkedlist<>();
List < String > myList = new Linkedlist<>();
The initial list is empty. How do we add strings?
myList.add(“Tom”);
A list node contains :
a data item
one (or more) link(s) (references to other node(s))
A Linkedlist object has a data field _____, which references the first list node.
head
Limitations of a singly-linked list include:
Insertion at the front is quickinsertion at other positions may require a list traversal to find insertion place
Insertion is convenient only after a referenced node
Removing a node requires a reference to the previous node
We can traverse the list only in the forward direction
Limitations such as:
Insertion at the front is quickinsertion at other positions may require a list traversal to find insertion place
Insertion is convenient only after a referenced node
Removing a node requires a reference to the previous node
We can traverse the list only in the forward direction
We can overcome these limitations by:
Adding a reference in each node to the previous node, creating a double-linked list
can be viewed as a moving place marker that keeps track of the current position in a particular linked list
An iterator
An Iterator object for a list starts at the:
List head
The programmer can move the Iterator by calling its _____ method.
next
The ________ stays on its current list item until it is needed
Iterator
By using an Iterator to traverse a linked list, the code segment can be:
rewritten so as to require n operations
Where is the iterative interface defined?
In java.util
The _____ interface declares the method ________ which returns an ________ object that iterates over the elements of that list
List
iterator
Iterator
An Iterator is:
it does not refer to a particular object at any given time
conceptually between elements
How do we process all List through Iterator?
Iterator iter = aList.iterator();
while(iter.hasNext()) {
item = iter.next();
}
You can use the ____________ method to remove items from a list as you access them.
Iterator remove()
deletes the most recent element returned in an Iterator
remove()
You must call next() before each remove(); otherwise , an _________ will be thrown
IllegalStateException
What’s the different LinkedList.remove(i) vs Iterator.remove
LinkedList.remove(i): must walk down the list each time , then remove
Iterator.remove removes items without starting over at the beginning
How do you remove all elements from a list of type Integer that are divisible by a particular value:
public static void remove DivisibleBy (LinkedList alist, int div)
Iterator iter = aList.iterator());
while ( iter.hasNext() ) {
int nextInt = iter.next ();
if ( nextInt % div == 0) {
iter.remove();
}
}
}
Iterator limitations:
How do we overcome these limitations?
Traverses List only in the forward direction
Provides a remove method, but no add method
You must advance the Iterator using your own loop if you do not start from the beginning of the list
ListIterator extends Iterator, overcoming these limitations
ListIterator positions are assigned an index from ____ to ____
0
Size
ListIterator has a method which is able to receive the proceeding and future index of items.
nextIndex();
previousIndex();
ListIterator is a subinterface of:
Iterator
Classes that implement ListIterator must provide the features of:
Both ListIterator and Iterator
Requires fewer methods
Can iterate over more general data structures
used by enhanced for loop
Iterator
Iterator is required by the ________ interface
Collection
ListIterator is required only by the _______ interface
List
The collection interface specifically excludes:
But including:
add (int , E)
get ( int)
remove ( int)
set (int, E )
add (E)
remove (Object)
the iterator method
In a general Collection the order of elements is:
not specified
For collections implementing the List interface, the order of the elements is determined by the:
index
In a general Collection, the position where an ______ is inserted is not specified
object
In ArrayList and LinkedList, add (E) always inserts at the ____ and always returns:
end
true
