Abstract Data Types and ArrayList

What is the lecture 'Abstract Data Types and ArrayList' trying to do? (slide 2)

Go from generic to specific (ideas, not types). Start with an abstract idea ('I want to be able to do THESE actions'), which likely becomes an interface. Finish with a specific implementation of it (ArrayList for the List ADT).

Primary source for the ADT and ArrayList lecture

CS 2336 Zybook sections 11.1, 16.1, and 15.

What does an abstract idea usually become in Java code?

An interface.

ADT analogy: wake-up routine (the concept)

Some things in life have well-defined ideas. A wake-up routine always includes: dress, eat breakfast, leave for the day. The concept is fixed, but HOW each step is done varies.

Wake-up routine: how the 'Dress' step can be implemented differently

Do I coordinate my outfit? Do I just grab clothes from the closet? Or (cough) do I get them from the floor? Same step, different implementations.

Wake-up routine: how 'Eat breakfast' can be implemented differently

Cereal, cook something, dining hall, restaurant, or drive-thru. Same step, different implementations.

Wake-up routine: how 'Leave for the day' can be implemented differently

Pack a bag, pack a purse, pack pockets, take keys or a bus pass. Same step, different implementations.

Key idea of the wake-up routine analogy

The concept (what must happen) is well defined, but the implementation (how it happens) varies from person to person. That is exactly what an ADT captures.

Wake-up Routine diagram: properties (attributes)

Wake-up Time (07:00 AM, Time), Routine Steps ([list of tasks], Array/List), Duration (45 mins, TimeDelta), Status (Not Started, String/Boolean), Active (True, Boolean).

Wake-up Routine diagram: methods (operations)

startRoutine() executes sequence. editSteps(newList) modifies tasks. setWakeTime(time) updates alarm. viewRoutine() returns steps. completeStep(index) marks progress.

ADT as a 'contract'

In creating an ADT, you are creating a contract: here is what this type of thing MUST do, but the HOW is left to implementations. Just like interfaces: saying WHAT to do without saying HOW.

What do you know when you use an ADT? (2 guarantees)

1) Certain operations will work, no matter the implementation. 2) You can switch one implementation with another.

Why does the instructor declare List

Because List defines everything he needs, so he can swap in a different List implementation later without changing his code (program to the ADT/interface, not the implementation).

Code: declaring by ADT type vs implementation type

List names = new ArrayList<>(); (good, ADT type on the left) | ArrayList names = new ArrayList<>(); (ties you to one implementation)

Abstract data type (ADT)

Where we know WHAT a certain kind of object should do, but not the details. We are not thinking code, but general methods, leaving things open for different implementations (the slide crosses out 'interpretations' and writes 'implementations').

Do ADTs involve code details?

No. We are not thinking code, but general methods. The details are left open for different implementations.

ADT animal example: climbing

We know many animals climb, but there is no one defined way to climb: 1) use claws to grab the tree, 2) grab limbs and pull up, 3) jump. 'Climb' is the ADT operation, the three ways are implementations.

What does the word 'abstract' mean in ADT?

It says that someone else fills out the HOW. Like an abstract class, where there are 1 or more methods with no code.

ADT vs abstract class (the comparison on the slide)

The 'abstract' in ADT is like an abstract class, where there are 1+ methods with no code and someone else fills in the how.

Cooker ADT: the situation

In a kitchen there are multiple ways to cook: oven, stove, microwave, air fryer. Question posed: can we make this an ADT? Yes, as a Cooker ADT.

Cooker ADT: setIntensity

Sets the cooking intensity. Means different things per device: the temperature (oven, air fryer), power level (microwave), burner setting (stove).

Cooker ADT: insertItem

Places the food in. Means place INSIDE for microwave, oven, and air fryer, and ON TOP OF for the stove.

Cooker ADT: removeItem

Takes the food out. 'See above' on the slide: same idea as insertItem (inside the device, or off the top of the stove).

Cooker ADT: setTimer

Behaves differently per cooker: might turn it off (microwave, air fryer), inform the user (oven), or do nothing (stove).

Cooker ADT: setMode

The oven sets it (bake, convection, broil). The other cookers ignore it.

Cooker ADT: preheat

A no-op (does nothing) for the microwave. (Others, like an oven, would actually preheat.)

Cooker ADT: list of all operations

setIntensity, insertItem, removeItem, setTimer, setMode, preheat.

Cooker ADT: which implementations does the lecture use?

Oven, stove, microwave, air fryer.

What is a 'no-op'?

An operation that does nothing. Example from the lecture: preheat is a no-op for the microwave, and setMode is ignored by non-oven cookers.

Same ADT method, different behavior across implementations (cooker examples)

setTimer: microwave/air fryer turn it off, oven informs the user, stove does nothing. setMode: oven sets bake/convection/broil, others ignore. This shows implementations can interpret the same operation differently.

After you define an ADT, what two things can you create from it?

Either a base class (abstract base class) or an interface.

When should an ADT become an (abstract) base class?

When some operations are the SAME for all types (shared code can live in the base class).

When should an ADT become an interface?

When there is NO commonality in HOW the operations happen.

Is the Cooker ADT a base class or an interface? Why?

An interface, because the way each cooker performs the operations has no commonality.

Abstract base class vs interface for an ADT (decision rule)

Some operations identical across types: abstract base class. No commonality in how operations happen: interface.

ADT vs data structure

ADT != data structure. Data structures are IMPLEMENTATIONS of ADTs. The ADT covers the WHAT, data structures cover the HOW.

Examples of data structures implementing ADTs (slide 18)

ArrayList and LinkedList implement List. TreeMap and HashMap implement Map.

Which ADT do ArrayList and LinkedList implement?

List.

Which ADT do TreeMap and HashMap implement?

Map.

How do ADTs and data structures map onto Java code?

ADTs generally become interfaces, and data structures implement those interfaces.

Is List an ADT or a data structure? Is ArrayList?

List is an ADT (an interface describing what a list does). ArrayList is a data structure (an implementation of the List ADT).

Problem that motivates the List ADT

We want to store a group of objects. We could support one specific way (like an array) or think more broadly and create an abstract data type.

Why not just use an array for storing a group of objects?

As we'll see later in the course, an array is not always the best option. An ADT lets us choose different implementations.

Class exercise: what should a list support?

Operations like add, remove, get by index, size, and isEmpty (the List ADT diagram on slides 20 to 22 shows these).

List ADT diagram: properties

Elements (an ordered collection of items, array or linked structure), Size (current number of elements, Integer), Index (zero-based pointer to element position, Integer), Is Empty (indicates if the list contains elements, Boolean).

List ADT diagram: methods

add(element) appends element to end. remove(element) deletes the first occurrence. get(index) returns element at position. size() returns the total number of items. isEmpty() checks if list has items.

Are these valid List implementations? ArrayList, LinkedList, Set (slide 22)

ArrayList: YES (uses an array behind the scenes). LinkedList: YES (each element points to the next). Set: NO (items are not ordered, and a list is an ordered collection).

Why is a Set NOT a valid List implementation?

A Set's items are not ordered, but a List is an ordered collection accessed by index.

Why is ArrayList a valid List implementation?

It uses an array behind the scenes, and it supports the ordered, indexed operations the List ADT requires.

Why is LinkedList a valid List implementation?

Each element points to the next element, but it still provides the ordered, indexed List operations.

List interface: general categories of operations (slide 24)

Adds and inserts, searching and sorting, removing, finding and retrieving, and more.

List interface: 'and more' operations (slide 25)

Does the list contain this object (or a group of them), retrieve a sublist (like String's substring()), and turn the list into an array.

List interface diagram (slide 23)

A List lst shown as indices 0 to 4 holding values 10, 25, 42, 17, 60, with the last element pointing to null. The diagram notes that duplicate values are allowed.

Are duplicate values allowed in a List?

Yes. The List diagram on slide 23 explicitly says 'Duplicate values allowed'.

Are List indices zero-based?

Yes. The first element is index 0 (List ADT: 'zero-based pointer to element position').

How does the lecture examine List methods?

Using ArrayList's implementation of them.

Docs referenced for List and ArrayList

Java SE 8 API docs: docs.oracle.com/javase/8/docs/api/java/util/List.html and …/ArrayList.html.

ArrayList: what is it?

A 'wrapper' around an array. It uses an array behind the scenes.

ArrayList: how does it grow?

It automatically grows the 'backing' array as needed by making a NEW array and copying everything over.

What is the 'backing array'?

The actual array an ArrayList uses behind the scenes to store its elements.

ArrayList: when is it fastest?

Fastest if you only modify (add at the end, set values). Adding or removing elsewhere requires shifting other values.

Why is adding/removing in the middle of an ArrayList slower?

Other values must be shifted over to make room (on add) or to close the gap (on remove).

ArrayList primary constructors (3 listed)

ArrayList() (empty), ArrayList(Collection c) (copy an existing collection), ArrayList(int capacity) (you give it a starting capacity).

ArrayList() constructor

Creates an empty list with a backing array of size 10 (per the slide).

ArrayList(Collection c) constructor

Copies over an existing collection into the new list.

ArrayList(int capacity) constructor

You give it a starting capacity (the initial size of the backing array).

What does 'Collection' mean?

A collection of the same class (E) or subclasses of it. (The slide says this is covered later.)

Collection vs List (slide callout)

Collection is a 'superclass' (superinterface?) of List, meaning List extends Collection.

Slide: how many 'primary' constructors, and what is the lecture's wording?

'Two primary constructors' is the slide heading, though three are listed: no-arg, Collection, and int capacity.

add(E e) signature and purpose

boolean add(E e). Adds an element (to the end of the list).

What is E in ArrayList methods?

The type of element. For ArrayList, E is String.

What does add(E e) return?

A boolean about success, but for ArrayList it will ALWAYS be true.

add(E e) diagram

add("Data") appends to the end: an array holding Apple, Banana, Cherry gets Date at index 3. A capacity bar shows the backing array may be larger than the number of elements.

add(int index, E element) signature and purpose

void add(int index, E element). INSERTS an element at the given index.

add(int index, E element): what happens to the other elements?

Everything at and to the 'right' of the new element is shifted back a spot to make room.

add(int index, E element): exception

Throws IndexOutOfBoundsException if the index is too high (greater than the current size). Inserting at index == size is allowed (same as appending).

add(E e) vs add(int index, E element)

add(E e) appends to the end and returns boolean (always true). add(int, E) inserts at a position, shifts later elements right, and returns void.

add(E) vs add(int, E): return types

add(E e) returns boolean. add(int index, E element) returns void.

contains(Object o) signature and purpose

boolean contains(Object o). FINDS an element. Returns true if it can find this element in the list.

Why does contains take Object instead of E?

Because List and ArrayList predate Java's generics.

What does contains() rely on?

The list elements (the you choose) implementing .equals(). Otherwise it is just checking whether the references are equal.

What happens if your element class does not override equals() and you call contains()?

It only checks reference equality (same object), so a different object with identical contents would not be found.

indexOf(Object o) signature and purpose

int indexOf(Object o). FINDS an element and returns the FIRST spot it is found (lowest index).

What does indexOf return if there are duplicates?

The lowest index where the element is found (the first occurrence).

What does indexOf return if the element is not in the list?

A negative value (-1). The slide's remove(Object) code relies on this with 'if (index < 0)'.

Does indexOf rely on equals()?

Yes. 'Also relies on .equals()' (same as contains).

Which ArrayList methods rely on equals()?

contains(Object), indexOf(Object), and remove(Object) (it finds the element using indexOf).

get(int index) signature and purpose

E get(int index). Gets a value by index.

get(int index): exception

Throws IndexOutOfBoundsException if the index is too high.

isEmpty() signature and meaning

boolean isEmpty(). Same as size() == 0.

remove(int index) signature and purpose

E remove(int index). Removes (and RETURNS) the element at this index.

remove(int index): what happens to other elements?

Everything to the right is shifted forward a slot to close the gap.

remove(Object o) signature and purpose

boolean remove(Object o). Removes the Object, if it can be found.

remove(Object o) return value

Returns true if the element was there (and removed), false otherwise.

Why doesn't remove(Object o) return the element?

There is no need, because you already have it or an equivalent one!

remove(int index) vs remove(Object o)

remove(int index): returns the removed element E, removes by position, shifts right elements forward. remove(Object o): returns boolean (was it there), removes the first match by equals().

remove() return types compared

remove(int index) returns E (the removed element). remove(Object o) returns boolean.

remove() diagram (slide 36)

ArrayList E remove(int index): shows an initial list, removing the element at index 1 (returned), then shifting remaining elements left, with a final list that is one element smaller.

size() signature and meaning

int size(). The size (number of elements) of the list.

size vs capacity

size is the number of elements in the list. capacity is the current size of the backing array it is using. size is NOT the capacity.