Computer Science 15-111 (Sections A & B), Spring 2007
Class Notes: 21-Mar-2007
Logistics:
1.
All hw is graded (grade sheets on
Friday)
2.
Quiz 5 is Tomorrow! Topics:
a.
Complexity and Big-Oh
b.
Packages
c.
Quicksort
d.
Radixsort
e.
AND…. All topics from Quiz 4
3.
Reading:
a.
For Quiz 5:
i.
Packages: Section 7.4
ii.
Complexity and Big-Oh Notation:
Section 5.8 and Wikipedia page on
Big-Oh
iii.
Quicksort: Wikipedia page on Quicksort
iv.
Radixsort: Wikipedia page on Radixsort
(just the “Least Significant Digit” part)
v.
Our own Sorts.java
b.
For today’s topics:
i.
Dynamic Data Structures / Linked
Lists (Sections 12.0 – 12.4)
ii.
Iterators (Sections 12.8 – 12.9)
iii.
Javanotes: Section 9.2 (Linked Lists)
iv.
Wikipedia page on Linked Lists
But you can ignore
these topics on that page: persistent
data structures, unrolled linked lists, heapsort, CDR coding, and
internal/external storage.
Topics:
1. Assigned Reading
Be sure to read ALL of the assigned reading.
It may cover topics that we do not cover in class, yet you are
responsible for on quizzes and tests.
2. Kinds of Linked Lists
a. Singly-Linked List
b. Doubly-Linked List
c. Circularly-Linked List
d. Note 1: ArrayLists are Lists (hence the name), but
not Linked Lists!
e. Note 2: You can implement Linked Lists in Arrays (see
this
section), but it’s not commonly done.
3. Lists in Java
b. LinkedList
implements List
(as a doubly-linked list)
c. List
interface
d. Iterator
interface
e. ListIterator
interface extends Iterator
interface
4. Tradeoffs (see
this section)
a. Indexing (looking up)
b. Inserting (once you know where to
insert)
c. Deleting (once you know where to
delete)
d. Locality of Reference (are adjacent
elements stored next to each other in memory?)
e. Storage overhead
f.
Allocation
time (and free-lists / memory-pools)
5. Linked List Operations (see this
section)
6. Implementing our own Linked List, Iterator, and ListIterator
(mostly for Friday)