CS102 · Annotated SlidesLinked Lists — Linked Lists
Linked Lists · Annotated slides

Linked Lists

Linked data structures, the generic LinkedList<E> class and its operations, iterators, sorting a LinkedList with a Comparator, and PriorityQueue.

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: Slide 1
Exam weight Low
    Slide 2: The Class LinkedList
    Exam weight Low
    1. A linked structure: nodes holding data and a reference to the next node.
    Slide 3: Slide 3
    Exam weight Low
      Slide 4: Linked Lists
      Exam weight High
      1. Dynamic: grows and shrinks one node at a time; no fixed size.
      🎯 How this can come up · 1 question
      MCQ

      Compared with ArrayList, LinkedList is better at:

      Slide 5: Slide 5
      Exam weight Low
        Slide 6: The LinkedList Class
        Exam weight Low
        1. LinkedList<E> is generic; E = element type.
        Slide 7: Slide 7
        Exam weight Low
          Slide 8: LinkedList
          Exam weight Medium
          1. Methods: add, addFirst, addLast, getFirst, getLast, removeFirst, removeLast, get, size.
          🎯 How this can come up · 1 question
          MCQ

          Which method inserts at the front of a LinkedList?

          Slide 9: LinkedList (cont.)
          Exam weight Low
            Slide 10: Iterators
            Exam weight Low
            1. Iterators traverse the list: hasNext(), next(); ListIterator goes both ways.
            Slide 11: Iterators
            Exam weight Low
              Slide 12: Iterator Java Interface
              Exam weight Low
                Slide 13: Slide 13
                Exam weight Low
                  Slide 14: Slide 14
                  Exam weight Low
                    Slide 15: Slide 15
                    Exam weight Low
                      Slide 16: Slide 16
                      Exam weight Low
                        Slide 17: This example gives you how to sort a LinkedList using Comparator. The LinkedList contains user defined objects. By using Collections.sort method you can sort the LinkedList. You have to pass Comparator object which contains your sort logic. The example sorts the Empl objects based on highest salary.
                        Exam weight Low
                        1. Sort a LinkedList of objects with Collections.sort(list, comparator).
                        Slide 18: Slide 18
                        Exam weight Low
                          Slide 19: import java.util.LinkedList;
                          Exam weight Low
                            Slide 20: Slide 20
                            Exam weight Low
                              Slide 21: Slide 21
                              Exam weight Low
                                Slide 22: Slide 22
                                Exam weight Low
                                  Slide 23: !"! // Check code PriorityQueueTest.java ! !#! // Standard library class PriorityQueue test program. ! !$! import java.util.PriorityQueue;
                                  Exam weight High
                                  1. PriorityQueue: poll() always returns the smallest (highest-priority) element.
                                  🎯 How this can come up · 1 question
                                  MCQ

                                  A PriorityQueue<Integer> holding 5, 1, 3: poll() returns:

                                  Slide 24: Student Priority Queue Demo
                                  Exam weight Low