Class4.md

title: IST-4-JAV Java Programming
subtitle: Class 4 - Going graphic
author: Alice BRENON `<alice.brenon@liris.cnrs.fr>`
date: 2022-10-19
institute:
	\includegraphics[height=.9cm]{figures/LIRIS}\quad
	\includegraphics[height=.9cm]{figures/INSA}
aspectratio: 169
header-includes:
	- \usepackage{fdsymbol}
	- \usepackage{textgreek}
	- \usepackage{bclogo}
	- \usepackage{Beamer/beamerthemePerso}
	- \setcounter{tocdepth}{1}

Complexity

Simple containers

Implementing interfaces

One interface, several implementations.

Two implementations

:::columns ::::{.column width=90%}

List

• a set of functionalities
• a contract to prove a class can act as a list

. . .

\rightarrow an interface! :::: :::

\vspace{0.5cm}

:::columns ::::column

ArrayList

\vspace{0.5cm}

• an array larger than the number of elements
• an index to remember where it stops

:::: ::::column

LinkedList

\vspace{0.5cm}

• a "head": the element in the current cell
• a "queue": the pointer to the rest of the list

:::: :::

Getting element at index i

:::columns ::::column

ArrayList

\vspace{0.5cm}

• check the bounds: O(1)
• return cell i: O(1)

\Rightarrow O(1)

:::: ::::column

LinkedList

\vspace{0.5cm}

does i == 0 ?

• if yes, get the head:
• otherwise, get the i-1\textsuperscript{th} element of the queue

\Rightarrow O(n)

:::: :::

Prepending

:::columns ::::column

ArrayList

\vspace{0.5cm}

• create a new array large enough: O(n)
• write the new element: O(1)
• copy all the other elements after: O(n)

\Rightarrow O(n)

:::: ::::column

LinkedList

\vspace{0.5cm}

• create a new cell with the new element pointing to the existing list: O(1)

\Rightarrow O(1)

:::: :::

Performance comparison

So which one is best?

• if frequent random access is needed: ArrayList
• if frequent modification is needed: LinkedList

\Rightarrow No "one-size-fits-all", implementation should match the use

In any case

Previously on IST-4-JAV (class 2)…

notion of type variable

. . .

List<String> al = new ArrayList<String>();

. . .

List<String> ll = new LinkedList<String>();

Associating values to keys

A common need

• "white pages", phone books…
• Domain Name System
• looking up users in a table by their ID
• finding the selected action in a menu

interface Map<K, V> {
	…
	V get(Object k);
}

Association list

:::columns ::::column

class Pair<K, V> {
	public K getKey() { … }
	public V getValue() { … }
}

:::: ::::column