[CS61B] Notes for class 5-Linked lists

Array-based lists
Advantage: very fast access of each item
2 disadvantages:
    (1) Insert item at beginning or middle takes time proportional to length of array.
    (2) Array has a fixed length.                        

Linked lists (a recursively data type)
Made up of nodes. Each node has:
(1) an item
(2) a reference to next node in list

Linked lists vs. Array lists
Advantages of linked lists:
(1) Inserting item into middle of linked lists takes constant time, if you have a ref to previous node.
(2) List can keep growing until memory runs out.

Disadvantage of linked lists: Finding n-th item of a linked list takes time proportional to n. (Start at head, walk n-1 nodes.)

The "public" and "private" keywords
Private method or field: invisible and inaccessible to other classes.
Why?
(1) To prevent data form being corrupted by other classes.
(2) You can improve the implementation without causing other classes to fail.


The interface of a class: prototypes for public methods, plus description of their behaviours.

Abstract Data Type (ADT): A class with well-defined interface, but implementation details are hidden from other classes.

Invariant: A fact about a data structure that is always true. "A Date object always stores a valid date." Enforced by allowing access only through method calls.
If we don't have any restriction of a field, than we could declare this filed to "public"; Otherwise, we should declare it as "private."

Not all classes are ADTs! Some classes are data storage units, no invariants; field can be public.

Double-Linked Lists
Insert and delete items at both ends in constant running time.

Sentinel: A special node that does not represent an item. It points to the first and last nodes.