Pre-Announcement

Jimmy has questions:

• Do you like being appreciated? (mix)
• Respected? (mix)
• Like inspiring the youth of today (mix)
• Whether yes or no, join OASES?
• But what is it?
• Tutor elementary school kids in Oakland.
• Great way to meet people.
• Rewarding and inspiring.

​

Next week, 3:30 - 6 PM in FSM Cafe, drop in info sessions.

• Monday thru Friday!�

Announcements

The College of Engineering is still trying to get us some office hours for M/T/W.

• Tentative location in Bechtel Hall. Will let you know as I get confirmation.
• Please use labs on Thursday/Friday.

​

Josh office hours schedule:

• Type 1: HW/Project help.
• In Bechtel or one of the Soda labs.
• Schedule will vary week to week.
• Type 2: Anything other than HW/Project help.
• In 779 Soda.
• Mondays: 2 - 3 PM, Wednesdays: 4 - 5 PM

�

​

One Last Note on Plagiarism

Collaboration Policy

We have enumerated very specific rules whose violation will result in an F (see about.html):

​

• By You Alone: All project code that you submit (other than skeleton code) should be written by you (or your partner) alone, except for small snippets that solve tiny subproblems (examples in collaboration policy online).
• Do Not Possess or Share Code: Before a project deadline, you should never be in possession of solution code that you did not write (on paper, electronically, etc.). You are equally culpable if you share. DO NOT GIVE YOUR CODE TO ANYONE, EVEN IF THEY ARE DESPERATE.
• Cite Your Sources: When you receive significant assistance from someone else (with ideas, debugging, etc.), you should cite that help somewhere in your source code. You will not be penalized for receiving this help.��

Permissible But with Extreme Caution

• Helping someone debug (don’t touch their keyboard/mouse/other).
• Looking at someone else’s code to help them.
• Ultra Danger: Looking at someone else’s code to understand something. If you do this, don’t write code anytime soon after looking at that code, your solution is going to gravitate straight to theirs.

​

Were it enforceable, I’d say no looking at code at all, but I want you to take these rules seriously (unlike, say, speed limits).

• The effect should be as if you’d never seen anyone’s else code at all.

Plagiarism will (Probably) be Detected, and Dealt with Harshly

Plagiarism detection software is very sophisticated.

• Also easy to use!
• Example: 70+ cases in Spring 2014.

​

We will fail you.

​

Please contact me if 61B is causing massive disruptions to your life.

Quick Note on Autograders / Debugging

Autograder is not intended to be your debugging tool.

• It is a bad habit to rely on teacher provided tools for correctness.

​

Example: The ReadRadius test is failing in the autograder, but works fine when you run the provided TestReadRadius.java file.

• Approach #0: Assume the autograder is broken (unlikely but possible).
• Approach #1: Visually inspect your code for errors. Sometimes works.
• Approach #2: Ask for help in office hours / Piazza. OK, but slow!
• Approach #3: Look inside TestReadRadius.java to see how it works. Try input files other than planets.txt, e.g.
• Create your own input file.
• Use one of the other input files in the /data folder.

​

CS61B, Spring 2016

Lecture 5: DLLs and Arrays

• Doubly Linked Lists
• Generic SLists
• Arrays
• Arrays vs. Classes

Summary of Last Time (From IntList to SList)

List of Improvements:

• Improvement #1: Rebranding IntList -> IntNode. For pedagogical clarity.
• Improvement #2: Creating an SList class with a private IntNode front. Hides details regarding references from users of our class.
• Neat side effect: Can now have size zero list.
• Improvement #3: Add a size variable to make size() fast.
• Improvement #4: Add a sentinel node to make code simpler.
• Improvement #5: Add a getBackNode helper method to simplify code.�

Doubly Linked Lists

(In Brief)

One (Avoidable) Downside of SLists

Inserting at the back of a list is much slower than the front.

private IntNode getBackNode() {

IntNode p = sentinel;

while (p.next != null) {

p = p.next;

}

return p;

}

public void insertBack(int x) {

IntNode back = getBackNode();

back.next = new IntNode(x, null);

size += 1;

}

​

Improvement #6: (???) Goal: Fast insertBack

How could we modify our list so that insertBack is also fast?

insertFront()

sentinel

getFront()

value

next

3

size

size()

insertBack()

Is .back enough? PollEv.com/jhug or Text JHUG to 37607

Suppose we want to support insert, get, and delete operations, will having a back pointer result for fast operations on long lists?

1. Yes
2. No

�If not, which operations would be slow?

insertBack()

sentinel

getBack()

value

next

3

size

size()

deleteBack()

back

.back Is Not Enough

Suppose we want to support insert, get, and delete operations, will having a back pointer result for fast operations on long lists?

• Yes
• No

�If not, which operations would be slow?

• Delete! Have to find the second to last item.

sentinel

value

next

3

size

back

Improvement #6: .back and ??? Goal: Fast insertBack

We added .back. What other changes might we make so that delete is also fast?

sentinel

value

next

3

size

back

Improvement #6: .back and .prev

We added .back. What other changes might we make so that delete is also fast?

• Add backwards links from every node (hence the name “doubly linked list”)

​

​

sentinel

item

next

2

size

back

prev

item

next

prev

item

next

prev

Doubly Linked Lists (Naive)

Reverse pointers allow all operations (insert, get, delete) to be fast.

sentinel

item

next

2

size

back

prev

0

sentinel

size

back

Doubly Linked Lists (Naive)

Non-obvious fact: This approach has an annoying special case: back sometimes points at the sentinel, and sometimes points at a ‘real’ node.

0

sentinel

size

back

sentinel

item

next

2

size

back

prev

Doubly Linked Lists (Double Sentinel)

One solution: Have two sentinels.

sentF

item

next

2

size

sentB

prev

0

sentF

size

sentB

null

This is one reasonable approach for Project 1A.

Doubly Linked Lists (Circular Sentinel)

Even better topology (IMO):

0

sentinel

size

sentinel

2

size

next

item

prev

This is my preferred approach for Project 1A.

Examples:

• sentinel.next.next is the node with item=17.
• sentinel.next.next.next is the sentinel node.
• The arrow in purple is sentinel.next.next.next

0

sentinel

size

Improvement #7: Fancier Sentinel Node(s)

While fast, adding .back and .prev introduces lots of special cases.

​

To avoid these, either:

• Add an additional sentB sentinel at the end of the list.
• Make your linked list circular (highly recommened for project 1), with a single sentinel in the middle.

Summary

List of Improvements:

• Improvement #1: Rebranding IntList -> IntNode. For pedagogical clarity.
• Improvement #2: Creating an SList class with a private IntNode front. Hides details regarding references from users of our class.
• Neat side effect: Can now have size zero list.
• Improvement #3: Add a size variable to make size() fast.
• Improvement #4: Add a sentinel node to simplify code.
• Improvement #5: Add a getBackNode helper method to simplify code.
• Improvement #6: Add .back and .prev to speed up back operations.
• Improvement #7: Add either a back sentinel (sentB) or make the topology of the list circular to simplify code.

Still many steps before we have an industrial strength data structure. Will discuss over coming weeks.�

Generic SLists

SLists

One issue with our SList class is that it only supports integers.

public class SList {� private IntNode sentinel;

private int size;�

public class IntNode {� public int item;� public IntNode next;�� public IntNode(int i, IntNode n) {� item = i; next = n;� }� }

...�}

​

SList s1 = new SList(5);

s1.insertFront(10);

SList s2 = new SList("hi");

s2.insertFront("apple");

​

SListLauncher.java:6: error: incompatible types: String cannot be converted to int

​

SList s2 = new SList("ape");

SLists

Java allows us to defer type selection until declaration.

public class SList<BleepBlorp> {� private Node sentinel;

private int size;�

public class Node {� public BleepBlorp item;� public Node next;�� public Node(BleepBlorp i, Node n) {� item = i; next = n;� }� }

...�}

​

SList<Integer> s1 = new SList<Integer>(5);

s1.insertFront(10);

SList<String> s2 = new SList<String>("hi");

s2.insertFront("apple");

​

Generics

We’ll spend a lot more time with generics later, but here are the rules of thumb you’ll need for project 1:

• In the .java file implementing your data structure, specify your “generic type” only once at the very top of the file.
• In .java files that use your data structure, specify desired type twice:
• Once during declaration.
• Once during instantiation.
• When declaring or instantiating your data structure, use the reference type.
• int: Integer
• double: Double
• char: Character
• boolean: Boolean
• long: Long
• etc.�

SList<Double> s1 = new SList<Double>(5.3);

​

double x = 9.3 + 15.2;

s1.insertFront(x);

reference type

Arrays

Variables and Objects

Variables

• When a variable is declared, we get a box of bits big enough to hold one item of its declared type (either 8, 16, 32, 64).
• The box associated with a variable may only hold values of its declared type. Types in Java are:
• One of eight primitives (int, double, ...)
• References to an Object of a particular type.

​

Objects are either:

• An instance of a class (lecture 2).
• An array (the nitty gritty today).

Arrays

Arrays consist of:

• A fixed integer length (cannot change!)
• A sequence of N memory boxes where N=length, such that:
• All of the boxes hold the same type of value (and have same # of bits).
• The boxes are numbered 0 through length-1.

​

Like all objects, arrays are anonymous.

• You get one reference when its created.
• If you reassign all variables containing that reference, you can never get the array back.

​

Can access box i with bracket notation, e.g. A[i]

Arrays

Like classes, arrays are (almost always) instantiated with new.

​

Three valid notations:

• y = new int[3];
• x = new int[]{1, 2, 3, 4, 5};
• int[] w = {9, 10, 11, 12, 13};

�

All three notations create an array, which we saw on the last slide comprises:

• A length field.
• A sequence of N boxes, where N = length.�

Can omit the new if you are also declaring a variable.

Creates array containing 3 int boxes (32 x 3 = 96 bits total). Each container gets a default value.

As an aside: In Oracle’s implementation of Java, all Java objects also have some overhead. Total size of an array=192 + KN bits, where K is the number of bits per item (Sedgewick/Wayne pg. 201 for more)

Array Basics: http://goo.gl/tFyMEJ

int[] z = null;

int[] x, y;

x = new int[]{1, 2, 3, 4, 5};

y = x;

x = new int[]{-1, 2, 5, 4, 99};

y = new int[3];

z = new int[0];

int xL = x.length;

String[] s = new String[6];

s[4] = "ketchup";

s[x[3] - x[1]] = "muffins";

int[] b = {9, 10, 11};

System.arraycopy(b, 0, x, 3, 2);

​

Array Basics: http://goo.gl/nFYwzU

int[] z = null;

int[] x, y;

x = new int[]{1, 2, 3, 4, 5};

y = x;

x = new int[]{-1, 2, 5, 4, 99};

y = new int[3];

z = new int[0];

int xL = x.length;

String[] s = new String[6];

s[4] = "ketchup";

s[x[3] - x[1]] = "muffins";

int[] b = {9, 10, 11};

System.arraycopy(b, 0, x, 3, 2);

​

Arraycopy

Two ways to copy arrays:

• Item by item using a loop.
• Using arraycopy. Takes 5 parameters:
• Source array
• Start position in source
• Target array
• Start position in target
• Number to copy

​

arraycopy is (likely to be) faster, particularly for large arrays. More compact code.

• Code is (arguably) harder to read.�

System.arraycopy(b, 0, x, 3, 2);

​

(In Python): x[3:5] = b[0:2]

2D Arrays

Arrays of Array Addresses (http://goo.gl/VS4cOK)

int[][] pascalsTriangle;

pascalsTriangle = new int[4][];

int[] rowZero = pascalsTriangle[0];

pascalsTriangle[0] = new int[]{1};

pascalsTriangle[1] = new int[]{1, 1};

pascalsTriangle[2] = new int[]{1, 2, 1};

pascalsTriangle[3] = new int[]{1, 3, 3, 1};

int[] rowTwo = pascalsTriangle[2];

rowTwo[1] = -5;

int[][] matrix;

matrix = new int[4][];

matrix = new int[4][4];

int[][] pascalAgain = new int[][]{{1}, {1, 1},

{1, 2, 1}, {1, 3, 3, 1}};

• Syntax for arrays of arrays can be a bit confounding. You’ll learn through practice.

Array Boxes Can Contain References to Arrays!

int[][] pascalsTriangle;

pascalsTriangle = new int[4][];

int[] rowZero = pascalsTriangle[0];

pascalsTriangle[0] = new int[]{1};

pascalsTriangle[1] = new int[]{1, 1};

pascalsTriangle[2] = new int[]{1, 2, 1};

pascalsTriangle[3] = new int[]{1, 3, 3, 1};

int[] rowTwo = pascalsTriangle[2];

rowTwo[1] = -5;

int[][] matrix;

matrix = new int[4][];

matrix = new int[4][4];

int[][] pascalAgain = new int[][]{{1}, {1, 1},

{1, 2, 1}, {1, 3, 3, 1}};

• Syntax for arrays of arrays can be a bit confounding. You’ll learn through practice.

Array of int array references.

Create four boxes, each can store an int array reference

Create a new array with three boxes, storing integers 1, 2, 1, respectively. Store a reference to this array in pascalsTriangle box #2.

Creates 5 total arrays.

Creates 1 total array.

PollEv.com/jhug or Text JHUG to 37607 (http://goo.gl/fCZ9Dr)

What will be the value of x[0][0] and w[0][0] when the code shown completes?

1. x: 1, w: 1
2. x: 1, w: -1
3. x: -1, w: 1
4. x: -1, w: -1
5. Other

​

​

arraycopy parameters are:

1. Source array
2. Start position in source
3. Target array
4. Start position in target
5. Number to copy

int[][] x = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

int[][] z = new int[3][];

z[0] = x[0];

z[1] = x[1];

z[2] = x[2];

z[0][0] = -z[0][0];

int[][] w = new int[3][3];

System.arraycopy(x[0], 0, w[0], 0, 3);

System.arraycopy(x[1], 0, w[1], 0, 3);

System.arraycopy(x[2], 0, w[2], 0, 3);

w[0][0] = -w[0][0];

​

Arrays vs. Classes

Arrays vs. Classes

Arrays and Classes can both be used to organize a bunch of memory boxes.

• Array boxes are accessed using [] notation.
• Class boxes are accessed using dot notation.
• Array boxes must all be of the same type.
• Class boxes may be of different types.

​

int[] x = new int[]{100, 101, 102, 103};

public class planet {

public double mass;

public String name;

...

}

​

Arrays vs. Classes

Array indices can be computed at runtime.

​

​

int indexOfInterest = 1 + 1;

/* get contents of box #2 */

int k = x[indexOfInterest];�int j = x[-1 + 3];

Planet p = new Planet(6e24, "earth");

int[] x = new int[]{100, 101, 102, 103};

Both of these retrievals from an array are totally normal and work fine.

Arrays vs. Classes

Class member variable names CANNOT be computed and used at runtime.

​

​

String fieldOfInterest = "mass";

double m = p.fieldOfInterest;

double z = p[fieldOfInterest];

double a = p."mass";

double b = p["mass"];

Planet p = new Planet(6e24, "earth");

int[] x = new int[]{100, 101, 102, 103};

All of these attempts to use retrieve a field of interest are syntax errors in Java.

… if you reallllly want to do this, you can: https://goo.gl/JxpyLq

​

Another view

The only (easy) way to access a member of a class is with hard-coded dot notation.

​

​

​

​

​

​

The Java compiler does not treat text on either side of a dot as an expression, and thus it is not evaluated.

• See a compilers or programming languages class for more!

​

int k = x[indexOfInterest]; /* no problem */

double m = p.fieldOfInterest; /* won't work */

double z = p[fieldOfInterest]; /* won't work */

/* No (sane) way to use field of interest */

​

double w = p.mass; /* works fine */

​