1 of 35

To do: February 1

Object obj1 = new Object();

System.out.println(obj1);

1. Which method is called when a reference variable is printed?

2. Describe the output.

2 of 35

Object class toString() method

Object obj1 = new Object();

System.out.println(obj1);

//toString() method of Object class is called

3 of 35

Inheritance Review

https://csawesome.runestone.academy/runestone/books/published/csawesome/Unit9-Inheritance/topic-9-1-inheritance-day1.html

4 of 35

Warm-up #2 - What is the output? Why?

Object obj2 = "cat";

System.out.println(obj2); // output #1

System.out.println(obj2.substring(0,2)); // output #2

5 of 35

Class diagram of relationship between Object and String

6 of 35

Warm-up #2 - What is the output? Why?

Object obj2 = "cat";

System.out.println(obj2); // cat

System.out.println(obj2.substring(0,2)); // Error

7 of 35

An interface is a list of methods that must be implemented.
An interface may not contain any implemented methods.
No instance variables and no constructors.

What is an interface?

8 of 35

Interface Comparable <T>

Type Parameters:�T - the type of objects that this object may be compared to

Compares this object with the specified object for order.

9 of 35

Interface Comparable <T>

int compareTo(T o)

currentObject.compareTo(parameterObject)

Returns 0 → objects are equal
Returns int<0 (negative integer) → current object precedes� parameter object
Returns int>0 (positive integer) → current object comes after� parameter object

10 of 35

sort methods

Arrays.sort() and Collections.sort()

require that the object type implement the Comparable interface so that the array can be sorted according to the natural ordering of its elements.

The natural ordering is defined by the implementation of the compareTo() method.

11 of 35

Warm-up #3 - what is the output?

Comparable c1 = 4;

Comparable c2 = 7;

System.out.println(c1.compareTo(c2)); // output #1

Comparable c3 = "dog";

Comparable c4 = "bird";

System.out.println(c3.compareTo(c4)); // output #2

12 of 35

Warm-up #3 - what is the output?

Comparable c1 = 4;

Comparable c2 = 7;

System.out.println(c1.compareTo(c2)); // -1

Comparable c3 = "dog";

Comparable c4 = "bird";

System.out.println(c3.compareTo(c4)); // 2

13 of 35

Complete Repl.it - SpiralMatrix

Compare implementations

goFormative - Hackerrank Largest Rectangle using Stack (optional)

If you've already completed this, could you please resubmit so easier to share with everyone tomorrow?

Go over homework

14 of 35

Repl.it 10-01 Inheritance Review

Comparable c5 = new Student("Rachel", 18);

Comparable c6 = new Student("Kavi", 17);

Comparable c7 = new Student("Chris", 18);

System.out.println(c7.compareTo(c6));

15 of 35

Repl.it 10-01 Inheritance Review

Comparable c5 = new Student("Rachel", 18);

Comparable c6 = new Student("Kavi", 17);

Comparable c7 = new Student("Chris", 18);

System.out.println(c7.compareTo(c6)); // what is output?

/*

In order to sort a list of Students, the Student class needs to implement the Comparable interface.

Complete the compareTo implementation in Student class so that age is used (sorted from least to greatest), but if two different students have the same age, then the Students are sorted alphabetically by name.

*/

16 of 35

Repl.it 10-01 Inheritance Review

Comparable c5 = new Student("Rachel", 18);

Comparable c6 = new Student("Kavi", 17);

Comparable c7 = new Student("Chris", 18);

System.out.println(c7.compareTo(c6)); // 1

/*

In order to sort a list of Students, the Student class needs to implement the Comparable interface.

Complete the compareTo implementation in Student class so that age is used (sorted from least to greatest), but if two different students have the same age, then the Students are sorted alphabetically by name.

*/

17 of 35

Repl.it 10-01

Inheritance Review

18 of 35

Java�LinkedList

19 of 35

The Collection interface is the parent of the List interface and Set interface. The Collection interface has many methods listed including add(), clear(), remove(), and size().

Collection

List

Set

Collection Interface

20 of 35

The List interface extends the Collection interface.

ArrayList and LinkedList both implement the List interface.

List interface

ArrayList

LinkedList

List Interface

Collection interface

21 of 35

LinkedList in Java implements List as a doubly-linked list with both forward and backward pointers.

Unlike an ArrayList which also implements the List interface using a dynamic array, LinkedList does not store data in contiguous memory so does not provide random access.

Java LinkedList

22 of 35

Java ArrayList

A weakness of the Dynamic Array is that elements are stored in a contiguous block. As a consequence, when a new element is inserted into or removed from the beginning or middle of the collection, all the adjacent elements must be moved in order to make space for the new value.

Element being inserted into dynamic array

23 of 35

Java LinkedList

An alternative approach is to use the idea of a Linked List.

In a linked list each value is stored in a separate block of memory,

termed a link.

In addition to a value, each link contains a reference to the next link in sequence.

24 of 35

Comparing ArrayList and LinkedList

From p 111 of https://www.cs.utexas.edu/users/novak/cs314.pdf

25 of 35

LinkedList

Methods

26 of 35

LinkedList frequently used methods
Return	Name	Use
void	add(int index, E e)	inserts item e to the specified position in the list
boolean	add(E e)	adds item e to the end of the list
E	set(int index, E element)	Replaces the element at index with the specified element.
E	get(int index)	get the item at specified index
int	size()	returns the # of elements in the list
E	remove()	removes and returns the head (first element) of the list
void	clear()	removes all items from the list

import java.util.LinkedList;

27 of 35

LinkedList methods
Return	Name	Use
E	getFirst()	Returns the first element in this list.
E	getLast()	Returns the last element in this list.

import java.util.LinkedList;

28 of 35

LinkedList<String> list;

list = new LinkedList<String>();

list.add("c");

list.add("b");

list.add("a");

list.add(1, "d");

out.println(list);

OUTPUT

add() method

29 of 35

LinkedList<String> list;

list = new LinkedList<String>();

list.add("c");

list.add("b");

list.add("a");

list.add(1, "d");

out.println(list);

OUTPUT

[c, d, b, a]

add() method

30 of 35

LinkedList<String> list;

list = new LinkedList<String>();

list.add("c");

list.add("b");

list.add("a");

list.add(1, "d");

out.println(list.get(0) );

out.println(list.get(1) );

out.println("first " + list.getFirst());

out.println("last " + list.getLast());

OUTPUT

get() method

31 of 35

LinkedList<String> list;

list = new LinkedList<String>();

list.add("c");

list.add("b");

list.add("a");

list.add(1, "d");

out.println(list.get(0) );

out.println(list.get(1) );

out.println("first " + list.getFirst());

out.println("last " + list.getLast());

OUTPUT

c

d

first c

last a

get() method

32 of 35

A linked list is a linear data structure.
The elements or nodes are NOT stored in contiguous memory locations.
Each node contains a value and a reference to the next node in the list.

Linked Lists

33 of 35

Repl.it 10-02

Intro to LinkedLists

34 of 35

Write entire Student class after implementing Comparable interface in IN and submit to Hub
Complete Repl.it 10-01 and 10-02 and submit.

Tomorrow - I will not be on campus.

Homework

35 of 35

public void createSpiral(){

int val = 1, r = 0, c = 0;

int size = mat.length;

int side = size-1;

while(val<=size*size && side >=0){

// going down

for(int i=0; i<side; i++)

{

mat[r][c] = val++;

r++;

}

// going right - add for loop

// going up - add for loop

// going left - add for loop

r++;

c++;

side -= 2;

}

if(size%2!=0)

mat[size/2][size/2]=size*size;

}

SpiralMatrix