Exam 2 Extra Flashcards
What is the big -O for the single-linked list get operation
The list must be searched for in the index, thus O(n)
What is the big-O for the set operation
The list must be searched for the index, thus O(n)
What is the big-O for each add method?
Since a reference to the tail of the list is available, the add method is constant or O(1)
Each node in a single-linked list, has a reference to _______ and _______
The data
The next node
In a double-linked list, each node has a reference to _________, _________, and __________
Data
The next node
The previous node
To remove an item from a single-linked list, you need a reference to ____________.
The previous node
To remove an item from a double-linked list, you need a reference to _________.
the node
Why don’t we implement the Orderedlist by extending What would happen if someone called the add method? How about the set method?
extending the Linkedlist class we expose all of the public of the. If either the add or set method were called the invariant were ordered could be violated.
What other methods in the List interface could we include in the orderedlist class?
hashCode indexOf clear isEmpty subList contains containsAll equals lastIndexOf removeAll toArray retainAll
Why don’t we a listiterator method for the OrderedList class?
If we implement the listIterator method using delegation, we would obtain an instance of ListIterator that supported the add and set methods. however, we could have defined own ListIterator class that delegated to the ListIterator returned the List , but did not pass the add and set methods through
Why didn’t we write the hasPrevious method as follows?
public boolean hasPrevious () {
return nextItem.prev != null || (nextItem == null && size != 0);
If nextItem was null, then the expression nextItem.prev would result in a NullPointerException .
Why must we call next or previous before we call remove?
A call to next or previous sets lastItemReturned; if this is not set, then NullPointerException will be thrown
What happens if we call remove after we call add What does the Java API documentation say? What does our implementation do?
Java documentation says that IllegalStateException is thrown if remove called after a call to add oun implementation will NullPointerException lastItemReturned is set to null by add
Why don’t implement the OrderedList by extending Linkedlist? What would happen if someone called the add method ? How about the set method ?
By extending the LinkedList class we expose all of the public methods of the Linkedlist class. either the add set method were called the invariant that the items were ordered could be violated.
Why don’t we provide a listIterator method for the Orderedlist class?
If we implement the listIterator method using delegation, we would obtain an instance of ListIterator that supported the add and set methods. However, we could have defined our own ListIterator class that delegated to the ListIterator from the underlying List class, but did not pass the add and set
