Linked Lists and Iterators2-24-2004Opening DiscussionWhat did we talk about last class?Do you have any questions about the assignment? Remember that the design is due today.Why would you want to use a singly linked list or any other type for that matter? Sorting linked lists?Code for the Singly Linked ListLet’s review the code for a basic singly linked list. In particular, note the recurring pattern of walking a list. That is a very important pattern for you to recognize though you won’t be specifically using it much in the project.Code for a Doubly Linked ListNow let's look at code for a doubly linked list with a sentinel. You should note that this code is much simpler in many ways because it lacks all the special cases.IteratorsYou have now seen patterns for walking through the elements of an array and a linked list. These are very significant patterns when we are dealing with low level code. However, they are also very different and can’t be easily interchanged. We would like a pattern for walking through the elements of any container, whether it be an array, a linked list, or other things we will discuss later.To do this, we introduce the concept of an iterator.Iterators ContinuedAs the name implies, and iterator lets us iterate through the elements of a container. Java has an Interface called Iterator that has three methods. Let’s go to the Java API to look at those methods.Java also has a similar construct with a less common name called an Enumeration. This was used in older Java libraries.Using an IteratorIf we have some type of container, cont, that can give us an Iterator then we can use the following loop structure to walk through the elements of that container, regardless of the nature of the container.for(Iterator iter=cont.iterator; iter.hasNext(); )What would an Iterator for an array based list look like? How about a linked list?Sorting Linked Lists and Sorted ListsLike arrays, linked lists can be sorted. However, what is easy with each is different. The easiest sorts with linked lists build new lists instead of swapping pieces. (Insertion and Selection are easy.)You can also build lists that are always sorted. These have a different interface and fall into a completely different set of data structures which are associative.Iterator CodeLet's now go and write an iterator for one of our linked list classes.Minute EssayThe Iterator for a list can be a private inner class. How would this work? How can you use it outside of the class if it is private?Remember to generate your design today and put it out on the web. The working code is due Thursday.The midterm is two weeks from today.Read java.awt and
View Full Document
Unlocking...