INHERITANCE

In Lab 3, you modified several methods in the SList class so that a "tail" reference could keep track of the end of the list, thereby speeding up the insertEnd() method.

THE STACK AND THE HEAP

Java stores stuff in two separate pools of memory: the stack and the heap.

The heap stores all objects, including all arrays, and all class variables (i.e. those declared "static").

The stack stores all local variables, including all parameters.

LISTS

Let's consider two different data structures for storing a list of things: an array and a linked list.

An array is a pretty obvious way to store a list, with a big advantage: it enables very fast access of each item. However, it has two disadvantages.

LOOPS

while Loops

A while statement is like an if statement, but the body of the statement is executed repeatedly, as long as the condition remains true. The following example tests whether n is a prime number by attempting to divide it by every integer in the range 2...n - 1.

PRIMITIVE TYPES

Not all variables are references to objects. Some variables are primitive types, which store values like "3", "7.2", "h", and "false". They are:

DEFINING CLASSES

An object is a repository of data.

• Fields: are variables that hold the data stored in objects. Fields in objects are also known as instance variables. In Java, fields are addressed much like methods are, but fields never have parameters, and no parentheses appear after them. For example, suppose that amanda is a Human object. Then amanda.introduce() is a method call, and amanda.age is a field. Let's write a class definition for the Human class.

Goals of CS 61B

1. Learning efficient data structures and algorithms that use them.
2. Designing and writing large programs.
3. Understanding and designing data abstraction and interfaces.
4. Learning Java.

Analysis of Algorithms

Introduction

Cast of characters.

• Programmer needs to develop a working solution.
• Client wants to solve problem efficiently.
• Theoretician wants to understand.
• Basic blocking and tackling is sometimes necessary.
• Student might play any or all of these roles someday.

Union-Find

Dynamic connectivity

Given a set of N objects.

• Union command: connect two objects.
• Find/connect query: is there a path connecting the two objects?

Lecture notes of CS 61B