CS210 · Annotated SlidesLists — Arrays, Linked Lists and Array Lists
Lists · Annotated slides

Arrays, Linked Lists and Array Lists

Arrays (the scoreboard example, inserting and removing by shifting), singly linked lists (insert/remove at head and tail), doubly linked lists with header and trailer sentinels, array lists, growable arrays (incremental vs. doubling, amortized analysis), positional lists and iterators. The Midterm 1 and Quiz 1 question banks are mostly linked-list code. (This handout carries an earlier student’s handwritten notes.)

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up
Slide 1: 9/17/2016 5:37 PM
Exam weight Low
  1. Arrays: length/capacity, declaring, the GameEntry/Scoreboard example.
Slide 2: 9/17/2016 5:37 PM
Exam weight Low
    Slide 3: 9/17/2016 5:37 PM
    Exam weight High
    1. Adding an entry at index i shifts n − i elements forward; removing shifts them back.
    🎯 How this can come up · 1 question
    MCQ

    Inserting at index 0 of an array holding n elements costs:

    Slide 4: 9/17/2016 5:37 PM
    Exam weight Low
      Slide 5: 9/17/2016 5:37 PM
      Exam weight Low
        Slide 6: Slide 6
        Exam weight Low
          Slide 7: 9/17/2016 5:37 PM
          Exam weight Low
          1. Singly linked list: nodes with element + next; head (and tail) references.
          Slide 8: 9/17/2016 5:37 PM
          Exam weight Low
            ★ Past exam
            Slide 9: 9/17/2016 5:37 PM
            Exam weight High
            1. Insert at head: new node → newest.next = head → head = newest. O(1).

            Asked in a real exam

            ★ Quiz 1 question bank · code to insert at the head
            🎯 How this can come up · 1 question
            MCQ

            Correct code to insert node N at the head of a doubly linked list:

            Slide 10: 9/17/2016 5:37 PM
            Exam weight Low
            1. Insert at tail: O(1) with a tail reference.
            ★ Past exam
            Slide 11: 9/17/2016 5:37 PM
            Exam weight High
            1. Remove at head: head = head.next. O(1). Remove at tail of a SINGLY linked list is NOT O(1): you must walk to the node before the tail.

            Asked in a real exam

            ★ Midterm 1 question bank · remove the last node / second-to-last★ Quiz 1 question bank · which operation is slowest in an SLL
            🎯 How this can come up · 1 question
            MCQ

            Which singly-linked-list operation takes O(n) even with a tail pointer?

            Slide 12: Slide 12
            Exam weight Low
            1. Doubly linked list: prev and next; header and trailer sentinels simplify the edge cases.
            ★ Past exam
            Slide 13: 9/17/2016 5:37 PM
            Exam weight High
            1. Insert between p and its successor: link the new node both ways (4 pointer updates). Delete p: p.prev.next = p.next; p.next.prev = p.prev.

            Asked in a real exam

            ★ Quiz 1 question bank · Before.next = After; After.prev = Before
            🎯 How this can come up · 2 questions
            MCQ

            To unlink node X between Before and After in a DLL:

            MCQ

            A doubly linked list beats a singly linked list for:

            Slide 14: Slide 14
            Exam weight Low
              Slide 15: 9/17/2016 5:37 PM
              Exam weight Low
                Slide 16: traile 9/17/2016 5:37 PM
                Exam weight Low
                  Slide 17: Slide 17
                  Exam weight Low
                  1. Array list (java.util.List): get, set, add(i, e), remove(i); add/remove at i shift elements → O(n).
                  Slide 18: Slide 18
                  Exam weight Low
                    Slide 19: 9/17/2016 5:37 PM
                    Exam weight Low
                      Slide 20: Slide 20
                      Exam weight Low
                      1. Growable array: when full, copy into a bigger array.
                      Slide 21: 9/17/2016 5:37 PM
                      Exam weight High
                      1. Incremental strategy (+c each time): n pushes cost O(n²) → amortized O(n) per push. Doubling: O(n) total → amortized O(1).
                      Memory trickGrow by DOUBLING, not by a constant.
                      🎯 How this can come up · 1 question
                      MCQ

                      With the doubling strategy, the amortized cost of a push is:

                      Slide 22: Slide 22
                      Exam weight Low
                      1. Positional list ADT: positions stay valid while other elements change.
                      Slide 23: 9/17/2016 5:37 PM
                      Exam weight Low
                        Slide 24: 9/17/2016 5:37 PM
                        Exam weight Low
                          Slide 25: 9/17/2016 5:37 PM
                          Exam weight Low
                            Slide 26: 9/17/2016 5:37 PM
                            Exam weight Low
                            1. Iterator: hasNext(), next(). Iterable: iterator(). for-each uses them.
                            Slide 27: 9/17/2016 5:37 PM
                            Exam weight Low
                              Slide 28: 9/17/2016 5:37 PM
                              Exam weight Low
                                Slide 29: 9/17/2016 5:37 PM
                                Exam weight Low
                                  Slide 30: 9/17/2016 5:37 PM
                                  Exam weight Low
                                    Slide 31: 9/17/2016 5:37 PM
                                    Exam weight Low
                                      Slide 32: 9/17/2016 5:37 PM
                                      Exam weight Low
                                        Slide 33: 9/17/2016 5:37 PM
                                        Exam weight Low
                                          Slide 34: 9/17/2016 5:37 PM
                                          Exam weight Low