CS210 · Lists · Annotated SlidesArrays, Linked Lists and Array Lists
Original
Overview

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.)

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 34 slides
  1. 1 9/17/2016 5:37 PM
  2. 2 9/17/2016 5:37 PM
  3. 3 9/17/2016 5:37 PM
  4. 4 9/17/2016 5:37 PM
  5. 5 9/17/2016 5:37 PM
  6. 6 Slide 6
  7. 7 9/17/2016 5:37 PM
  8. 8 9/17/2016 5:37 PM
  9. 9 9/17/2016 5:37 PM
  10. 10 9/17/2016 5:37 PM
  11. 11 9/17/2016 5:37 PM
  12. 12 b c
  13. 13 9/17/2016 5:37 PM
  14. 14 y a
  15. 15 9/17/2016 5:37 PM
  16. 16 traile 9/17/2016 5:37 PM
  17. 17 AT.n.ie
  18. 18 Slide 18
  19. 19 9/17/2016 5:37 PM
  20. 20 sic
  21. 21 9/17/2016 5:37 PM
  22. 22 about.mn
  23. 23 9/17/2016 5:37 PM
  24. 24 9/17/2016 5:37 PM
  25. 25 9/17/2016 5:37 PM
  26. 26 9/17/2016 5:37 PM
  27. 27 9/17/2016 5:37 PM
  28. 28 9/17/2016 5:37 PM
  29. 29 9/17/2016 5:37 PM
  30. 30 9/17/2016 5:37 PM
  31. 31 9/17/2016 5:37 PM
  32. 32 9/17/2016 5:37 PM
  33. 33 9/17/2016 5:37 PM
  34. 34 9/17/2016 5:37 PM
Slide 1 / 34

9/17/2016 5:37 PM

Slide 1: 9/17/2016 5:37 PM

Notes

  1. Arrays: length/capacity, declaring, the GameEntry/Scoreboard example.

Slide 2 / 34

9/17/2016 5:37 PM

Slide 2: 9/17/2016 5:37 PM
Slide 3 / 34

9/17/2016 5:37 PM

Slide 3: 9/17/2016 5:37 PM

Notes

  1. Adding an entry at index i shifts n − i elements forward; removing shifts them back.

Exam angle

PredictionQ1

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

Slide 4 / 34

9/17/2016 5:37 PM

Slide 4: 9/17/2016 5:37 PM
Slide 5 / 34

9/17/2016 5:37 PM

Slide 5: 9/17/2016 5:37 PM
Slide 6 / 34

Slide 6

Slide 6: Slide 6
Slide 7 / 34

9/17/2016 5:37 PM

Slide 7: 9/17/2016 5:37 PM

Notes

  1. Singly linked list: nodes with element + next; head (and tail) references.

Slide 8 / 34

9/17/2016 5:37 PM

Slide 8: 9/17/2016 5:37 PM
Slide 9 / 34

9/17/2016 5:37 PM

Slide 9: 9/17/2016 5:37 PM

Notes

  1. Insert at head: new node → newest.next = head → head = newest. O(1).

Exam angle

PredictionQ1

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

Slide 10 / 34

9/17/2016 5:37 PM

Slide 10: 9/17/2016 5:37 PM
Slide 11 / 34

9/17/2016 5:37 PM

Slide 11: 9/17/2016 5:37 PM

Notes

  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.

Exam angle

PredictionQ1

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

Slide 12 / 34

b c

Slide 12: b c

Notes

  1. Doubly linked list: prev and next; header and trailer sentinels simplify the edge cases.

Slide 13 / 34

9/17/2016 5:37 PM

Slide 13: 9/17/2016 5:37 PM

Notes

  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.

Exam angle

PredictionQ1

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

PredictionQ2

A doubly linked list beats a singly linked list for:

Slide 14 / 34

y a

Slide 14: y a
Slide 15 / 34

9/17/2016 5:37 PM

Slide 15: 9/17/2016 5:37 PM
Slide 16 / 34

traile 9/17/2016 5:37 PM

Slide 16: traile 9/17/2016 5:37 PM
Slide 17 / 34

AT.n.ie

Slide 17: AT.n.ie

Notes

  1. Array list (java.util.List): get, set, add(i, e), remove(i); add/remove at i shift elements → O(n).

Slide 18 / 34

Slide 18

Slide 18: Slide 18
Slide 19 / 34

9/17/2016 5:37 PM

Slide 19: 9/17/2016 5:37 PM
Slide 20 / 34

sic

Slide 20: sic

Notes

  1. Growable array: when full, copy into a bigger array.

Slide 21 / 34

9/17/2016 5:37 PM

Slide 21: 9/17/2016 5:37 PM

Notes

  1. Incremental strategy (+c each time): n pushes cost O(n²) → amortized O(n) per push. Doubling: O(n) total → amortized O(1).

  2. Memory trick Grow by DOUBLING, not by a constant.

Exam angle

PredictionQ1

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

Slide 22 / 34

about.mn

Slide 22: about.mn

Notes

  1. Positional list ADT: positions stay valid while other elements change.

Slide 23 / 34

9/17/2016 5:37 PM

Slide 23: 9/17/2016 5:37 PM
Slide 24 / 34

9/17/2016 5:37 PM

Slide 24: 9/17/2016 5:37 PM
Slide 25 / 34

9/17/2016 5:37 PM

Slide 25: 9/17/2016 5:37 PM
Slide 26 / 34

9/17/2016 5:37 PM

Slide 26: 9/17/2016 5:37 PM

Notes

  1. Iterator: hasNext(), next(). Iterable: iterator(). for-each uses them.

Slide 27 / 34

9/17/2016 5:37 PM

Slide 27: 9/17/2016 5:37 PM
Slide 28 / 34

9/17/2016 5:37 PM

Slide 28: 9/17/2016 5:37 PM
Slide 29 / 34

9/17/2016 5:37 PM

Slide 29: 9/17/2016 5:37 PM
Slide 30 / 34

9/17/2016 5:37 PM

Slide 30: 9/17/2016 5:37 PM
Slide 31 / 34

9/17/2016 5:37 PM

Slide 31: 9/17/2016 5:37 PM
Slide 32 / 34

9/17/2016 5:37 PM

Slide 32: 9/17/2016 5:37 PM
Slide 33 / 34

9/17/2016 5:37 PM

Slide 33: 9/17/2016 5:37 PM
Slide 34 / 34

9/17/2016 5:37 PM

Slide 34: 9/17/2016 5:37 PM