Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Chapter 3. Lists > Exercises - Pg. 74

Chapter 3 public void clear() { _headAndTail.setPrevious(_headAndTail); _headAndTail.setNext(_headAndTail); _size = 0; } How It Works Not surprisingly, the size() and isEmpty() methods are carbon copies of their array list counterparts. The last method, clear() , is almost, but not quite, as simple as the array list implementation. In order to maintain the correct behavior while using the sentinel, you need to set its next and previous values to point to itself. This ensures that when you insert the first element into the list, its next and previous val- ues will point to the sentinel, and, most important, the sentinel's next and previous values will point to the new element. Summar y This chapter demonstrated that lists can be used as a replacement for the use of arrays in most real- world applications. You learned that lists preserve insertion order and that they have no inherent concept of uniqueness. You've also covered quite a lot of code in order to examine two of the most common list implementa- tions and their relative performance characteristics. Both array lists and linked lists have similar search and iteration times. However, by their very nature, array lists have much better index-based access com- pared to linked lists. On the other hand, linked lists don't have the overhead of copying and resizing that array lists do, so they have generally better insertion and deletion times, especially at the ends. Although lists as described here are useful in many situations, there are times when slightly different behavior is needed. The next two chapters discuss some variations on lists, known as queues and stacks, that help solve some very specific computing problems. Exercises 1. 2. 3. 4. 5. 6. 7. 74 Write a constructor for ArrayList that accepts a standard Java array to initially populate List . Write an equals() method that will work for any List implementation. Write a toString() method that will work for any List implementation that prints the con- tents as a single line with values surrounded by square brackets and separated by commas. For example, " [A, B, C] " or " [] " for an empty List . Create an Iterator that will work for any List implementation. What are the performance implications? Update LinkedList to traverse backward if, when inserting and deleting, the desired index is more than halfway along the list. Rewrite indexOf() so that it will work for any list. Create a List implementation that is always empty and throws UnsupportedOperationException if an attempt is made to modify it.