Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 81Linked Lists and Iterators3-4-20102Opening Discussion■Let's look at some solutions to the interclass problem.■Do you have any questions about the reading?■Do you have any questions about the assignment?■Minute EssaysDifference between System.out and System.err.Makes perfect sense in class...Practical uses of linked lists.Difference between ADT's and lists.Purpose of interfaces in the project.3Implementing a Singly Linked List■Let's work together to build an implementation of a singly linked list.4Sentinels■A sentinel is an extra node in the list the represents the “end” of the list and doesn't store data.■The purpose of the sentinel is to remove special cases. The next of the sentinel is what we have called head.■They are most useful in a doubly linked list where the previous of the sentinel is tail.5Implementing a Doubly Linked List■Now let's implement our List interface with a doubly linked list with a sentinel. The list will also be circular.■You should notice that this implementation never has to check for null because no references in the list should ever be null. This simplifies the code significantly. We also implicitly get a head and a tail with no extra work. If you don't have a sentinel you will write a lot of extra checks for nulls and even more to include a tail.6Iterators■Direct access on linked lists is very inefficient. How then should we walk through a list with outside code? Remember that the outside code doesn't have access to the nodes so it can't use the style of loop we have been doing internally.■The concept of an Iterator is something that abstracts the process of walking through all of the elements in a container. Iterators can not only be efficient, they also make code more flexible because they don't depend on the implementation details of the containers.7Iterating Lists■An iterator basically needs to encapsulate the information and functionality we would put into a standard method of going through a container.■With this in mind, what do we need to put in an iterator for an array based list?■What would we put in an iterator for a linked list?8Minute Essay■How do you think you would do a linked list in C? How is it different from the Java code?■Interclass problem – Write an iterator that goes through our linked list backwards. Try another one that skips every other
View Full Document