CS210 · Annotated SlidesLists — Circular Linked Lists and Iterators
Lists · Annotated slides

Circular Linked Lists and Iterators

Round-robin scheduling, circular linked lists with only a tail reference (rotate, add, remove), and the Iterator and Iterable interfaces.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Circular linked Lists
Exam weight Low
    Slide 2: Round-Robin Scheduling
    Exam weight Low
    1. Round-robin scheduling: each process gets a time slice, then goes to the back.
    Slide 3: Round-Robin Scheduling
    Exam weight Low
      Slide 5: Circular Linked-Lists
      Exam weight Low
        Slide 6: Circular Linked-Lists
        Exam weight Low
          Slide 7: Circular Linked-Lists: rotate
          Exam weight Medium
          1. rotate(): tail = tail.next moves the first element to the back in O(1).
          Slide 8: Circular Linked-lists:
          Exam weight Low
            Slide 9: tail
            Exam weight Low
              Slide 10: one
              Exam weight Low
                Slide 11: Presentation for use with the textbook Data Structures and Algorithms in Java, 6 th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014
                Exam weight Low
                  Slide 12: Iterators
                  Exam weight Low

                    The Iterable Interface

                    • Java defines a parameterized interface, named Iterable, that includes the following single method:
                      • iterator: Returns an iterator of the elements in the collection.
                    • An instance of a typical collection class in Java, such as an ArrayList, is iterable (but not itself an iterator); it produces an iterator for its collection as the return value of the iterator method.
                    • Each call to iterator returns a new iterator instance, thereby allowing multiple (even simultaneous) traversals of a collection.

                    © 2014 Goodrich, Tamassia, Goldwasser

                    Lists and Iterators

                    13
                    Exam weight Low
                    1. Iterable has iterator(); for-each works on any Iterable.
                    Slide 14: The for-each Loop
                    Exam weight Low