Arrays and Nodes

CSE 373 A Sp 25

Announcements

• Complete Self-Introduction Slide!
• Course Website + Canvas Overview
• Course policies in development
• Deques to be released soon

​

Review: OOP Components

Classes: define the meaning behind “objects”, including state and behavior 🗺️

Interfaces: set a contract for classes, to have established methods 📝

​

Review: OOP & Abstraction

Clients: Utilize products, expecting them to perform in certain ways. 👩‍💻

Implementers: Maintain baseline for clients to use safely (“promise”) 👷‍♀️

​

​

Review: OOP & Abstraction

Abstraction: Can use a product without knowing its inner workings. 🙈

Encapsulation: A tool for hiding implementation details away, often by using classes. 🚧

​

​

​

​

Pre-Class Q1

Dynamic Arrays

​

💭 How can we implement an ArrayList? Using an array!

1. When adding elements, create a new array with capacity = data.length + 1, and copy over the data. 🐢

​

• Track size*! Also start with capacity for 10 elements. Increase this when needed. 🏎️💨

​

* Is size the same as elementData.length?

ArrayList Code

​

Pre-Class Q2

​

Pre-Class Q3

​

​

​

Invariants

ArrayList invariant. The i-th element in the list is always at elementData[i].

​

​

​

​

Which elementData array is also valid for an ArrayList representing [5, 6]?

1

size: 2

elementData:

index 0 1 2 3

ArrayList

List

index 0 1

index 0 1 2 3

A

index 0 1 2 3

B

index 0 1 2 3

C

index 0 1 2 3

D

Aside - Invariants

​

Invariants simply refer to set rules/conditions that should always hold true. (Connects to mathematics)

Informal EX:

• For a queue, the next element to remove (oldest element) is always at the front. This is the element we can peek()! 🚶🚶🚶🚶

Linked Nodes

​

💭 How can we implement a LinkedList? Using linked nodes!

Nodes contain:

• A value for its element
• A reference* (link) to the next node 👉
• If null, we reached the end!

Our list is built upon a reference to the first link in the sequence.

​

* Recall reference semantics!

Node Class Code

​

​

​

LinkedList.add

In the homework, we studied the LinkedList method add(E element).

Node current = front;

while (current.next ! = null) {

current = current.next;

}

current.next = new Node(element);

What does each part of this code do? What node will current refer to at the end?

​

​

What feels slow about this code? Brainstorm a potential fix.

2

Back Pointer - LinkedDeque

​

ADTs and Collections

​

Abstract Data Types indicate general expected functionality, often through interfaces. (List)

We implement ADTs often by using classes. (ArrayList)

Collections refer to objects used to represent objects known as elements*

• Many ADTs fit this definition! Like ‘containers’

​

*What is the E type parameter?

​

​

​

Abstract data types

List<E>. Ordered sequence. Implemented by ArrayList and LinkedList.

​

​

​

​

​

​

Set<E>. Unordered collection of unique elements.

Map<K, V>. Distinct keys associated with values.

Stack<E>. Last-in, first-out (LIFO) sequence.

Queue<E>. First-in, first-out (FIFO) sequence.

3

size: 2

elementData:

size: 2

front

index 0 1 2 3

Queue

add

remove

Map

ArrayList

LinkedList

List

index 0 1

Okay - So Now What?

​

The process of identifying common problems and designing custom solutions to them is central to our course!

​

Let’s try using our ArrayList and LinkedList knowledge in application.

​

​

Music Playlist

Imagine you want to use queues to build a music playlist that can add songs, play the next song (removing it from the queue), and more. The LinkedList class can be used to implement the Queue interface, but you want to explore other options.

How can you use resizing arrays to implement the Queue interface?

add(E element).

​

​

remove().

4

Queue

add

remove

Thanks! See you all next week! ~

​

Today’s Song:

“Love at First Sight”

Vacations

​