1 of 25

Lecture 2: List Case Study

CSE 373: Data Structures and Algorithms

1

CSE 373 23SU

CSE 373 23SU

1

2 of 25

Agenda

Quick ADT Review

List Case Study

Questions

CSE 373 23SU

2

3 of 25

Announcements

Things are live!

  • course website – one stop for all things 373
  • Ed board – get your course content questions answered + connect with students
  • Gradescope
    • if you don’t see yourself on the Canvas / Gradescope / Ed Board lmk!!

​

Project 0 Released – Due Friday June 30th at 11:59PM

  • sorry about delay in release! project host site had moved :(
  • 143 review
  • OH start today!
  • Get started on setup now!
  • project resubmissions….sure! just email us at cse373-instructors@cs.washington.edu
  • style clarification… do what makes you happy! (as long as you’re not breaking the autograder)

​

Website troubleshooting… please be patient with us :(

CSE 373 23SU

3

4 of 25

Quick ADT Review

List Case Study

Generics

Questions

CSE 373 23SU

4

5 of 25

Review: Full Definitions

  • Abstract Data Type (ADT)
    • A definition for expected operations and behavior
    • A mathematical description of a collection with a set of supported operations and how they should behave when called upon
    • Describes what a collection does, not how it does it
    • Can be expressed as an interface
    • Examples: List, Map, Set
  • Data Structure
    • A way of organizing and storing related data points
    • An object that implements the functionality of a specified ADT
    • Describes exactly how the collection will perform the required operations
    • Examples: LinkedIntList, ArrayIntList

CSE 373 23SU

5

6 of 25

ADTs we’ll discuss this quarter

  • List: an ordered sequence of elements
  • Set: an unordered collection of elements
  • Map: a collection of “keys” and associated “values”
  • Stack: a sequence of elements that can only go in or out from one end
  • Queue: a sequence of elements that go in one end and exit the other
  • Priority Queue: a sequence of elements that is ordered by “priority”
  • Graph: a collection of points/vertices and edges between points
  • Disjoint Set: a collection of sets of elements with no overlap

CSE 373 23SU

6

7 of 25

Questions?

CSE 373 23SU

7

8 of 25

Quick ADT Review

List Case Study

Questions

CSE 373 23SU

8

9 of 25

Case Study: The List ADT

list: a collection storing an ordered sequence of elements

  • Each item is accessible by an index
  • A list has a size defined as the number of elements in the list

 Expected Behavior:

  • get(index): returns the item at the given index
  • set(value, index): sets the item at the given index to the given value
  • append(value): adds the given item to the end of the list
  • insert(value, index): insert the given item at the given index maintaining order
  • delete(index): removes the item at the given index maintaining order
  • size(): returns the number of elements in the list

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

names.append("Anish");           

names.append("Amanda");

names.insert(0, "Brian");

CSE 373 23SU

9

10 of 25

Case Study: List Implementations

List ADT

get(index) return item at index

set(item, index) replace item at index

append(item) add item to end of list

insert(item, index) add item at index

delete(index) delete item at index

size() count of items

state

behavior

Set of ordered items

Count of items

ArrayList<E>

get return data[index]

set data[index] = value

append data[size] = value, if out of space grow data

insert shift values to make hole at index, data[index] = value, if out of space grow data

delete shift following values forward

size return size

​

state

behavior

data[]

size

LinkedList<E>

get loop until index, return node’s value

set loop until index, update node’s value

append create new node, update next of last node

insert create new node, loop until index, update next fields

delete loop until index, skip node

size return size

state

behavior

Node front

size

ArrayList

uses an Array as underlying storage

LinkedList

uses nodes as underlying storage

0

1

2

3

4

88.6

26.1

94.4

0

0

88.6

26.1

94.4

list

free space

CSE 373 23SU

10

11 of 25

Implementing Insert

0

1

2

3

​

​

​

​

insert(10, 0)

3

4

5

numberOfItems =

3

insert(element, index) with shifting

5

4

3

10

4

insert(10, 0)

numberOfItems =

3

insert(element, index) with shifting

4

3

4

5

10

ArrayList<E>

LinkedList<E>

CSE 373 23SU

11

12 of 25

Implementing Delete

0

1

2

3

​

​

​

​

3

4

5

numberOfItems =

3

delete(index) with shifting

delete(0)

10

3

4

5

4

numberOfItems =

3

delete(index) with shifting

delete(0)

4

3

4

5

10

ArrayList<E>

LinkedList<E>

CSE 373 23SU

12

13 of 25

Implementing Append

0

1

2

3

4

5

6

7

​

​

​

​

​

​

​

​

0

1

2

3

​

​

​

​

append(2)

3

5

numberOfItems =

append(element) with growth

4

10

4

2

5

10

3

4

5

ArrayList<E>

append(2)

numberOfItems =

append(element) with growth

4

5

3

4

5

10

2

LinkedList<E>

CSE 373 23SU

13

14 of 25

Review: Complexity Class

complexity class: A category of algorithm efficiency based on the algorithm's relationship to the input size N.

Complexity Class

Big-O

Runtime if you double N

Example Algorithm

constant

O(1)

unchanged

Accessing an index of an array

logarithmic

O(log2 N)

increases slightly

Binary search

linear

O(N)

doubles

Looping over an array

log-linear

O(N log2 N)

slightly more than doubles

Merge sort algorithm

quadratic

O(N2)

quadruples

Nested loops!

...

...

...

...

exponential

O(2N)

multiplies drastically

Fibonacci with recursion

Note: You don’t have to understand all of this right now – we’ll dive into it soon.

CSE 373 23SU

14

15 of 25

List ADT tradeoffs

0

1

2

3

4

‘h’

‘e’

‘l’

‘l’

‘o’

‘h’

​

‘o’

/

‘e’

​

‘l’

​

‘l’

​

ArrayList<Character> myArr

front

LinkedList<Character> myLl

Last time: we used “slow” and “fast” to describe running times.

Let’s be a little more precise.

Recall these basic Big-O ideas from 12X: Suppose our list has N elements

  • If a method takes a constant number of steps (like 23 or 5) its running time is O(1)
  • If a method takes a linear number of steps (like 4N+3) its running time is O(N)

For ArrayLists and LinkedLists, what is the O() for each of these operations?

  • Time needed to access Nth element
  • Time needed to insert at end (what if the array is full?)

What are the memory tradeoffs for our two implementations?

CSE 373 23SU

15

16 of 25

List ADT tradeoffs

Time needed to access Nth element:

  • ArrayList:
  • LinkedList:

Time needed to insert at Nth element (if the array is full!)

  • ArrayList:
  • LinkedList:

Amount of space used overall/across all elements

  • ArrayList:
  • LinkedList:

Amount of space used per element

  • ArrayList:
  • LinkedList:

​

O(1) constant time

O(N) linear time

O(N) linear time

O(N) linear time

sometimes wasted space at end of array

compact, one node for each entry

minimal, one element of array

tiny bit extra, object with two fields

0

1

2

3

4

‘h’

‘e’

‘l’

‘l’

‘o’

‘h’

​

‘o’

/

‘e’

​

‘l’

​

‘l’

​

ArrayList<Character> myArr

front

LinkedList<Character> myLl

CSE 373 23SU

16

17 of 25

Design Decisions

For every ADT there are lots of different ways to implement them

Based on your situation you should consider:

  • Memory vs Speed
  • Generic/Reusability vs Specific/Specialized
  • One Function vs Another
  • Robustness vs Performance

​

This class is all about implementing ADTs based on making the right design tradeoffs!

A common topic in interview questions!

CSE 373 23SU

17

18 of 25

A quick aside: Types of memory

int[] array = new int[3];

array[0] = 3;

array[1] = 7;

array[2] = 3;

Node front = new Node(3);

front.next = new Node(7);

front.next.next = new Node(3);

Arrays - contiguous memory: when the “new” keyword is used on an array the operating system sets aside a single, right-sized block of computer memory

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

​

d672

8baf

020a

​

​

​

713f

04e3

2e6e

3

7

3

Nodes- non-contiguous memory: when the “new” keyword is used on a single node the operating system sets aside enough space for that object at the next available memory location

array

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

​

4b44

​

​

052f

d3cd

​

​

23d4

​

​

front

3

7

3

More on how memory impacts runtime later in this course…

CSE 373 23SU

18

19 of 25

Design Decisions

Situation #1: Write a data structure that implements the List ADT that will be used to store a list of songs in a playlist.

​

Features to consider:

  • add or remove songs from list
  • change song order
  • shuffle play

Why ArrayList?

  • optimized element access makes shuffle more efficient
  • accessing next element faster in contiguous memory

​

​

Why LinkedList?

  • easier to reorder songs
  • memory right sized for changes in size of playlist, shrinks if songs are removed

​

CSE 373 23SU

19

20 of 25

Design Decisions

Situation #2: Write a data structure that implements the List ADT that will be used to store the history of a bank customer’s transactions.

​

Features to consider:

  • adding a new transaction
  • reviewing/retrieving transaction history

​

Why ArrayList?

  • optimized element access makes reviewing based on order easier
  • contiguous memory more efficient and less waste than usual array usage because no removals

​

​

Why LinkedList?

  • if structured with front pointing to most recent transaction, addition of transactions constant time
  • memory right sized for large variations in different account history size

​

CSE 373 23SU

20

21 of 25

Design Decisions

Situation #3: Write a data structure that implements the List ADT that will be used to store the order of students waiting to speak to a TA at a tutoring center

​

​

ArrayList – optimize for addition to back

LinkedList - optimize for removal from front

CSE 373 23SU

21

22 of 25

Real-World Scenarios: Lists

LinkedList

  • Image viewer
    • Previous and next images are linked, hence can be accessed by next and previous button
  • Dynamic memory allocation
    • We use linked list of free blocks
  • Implementations of other ADTs such as Stacks, Queues, Graphs, etc.

ArrayList

  • Maintaining Database Records
    • List of records you want to add / delete from and maintain your order after
  • Implementations of other ADTs such as Stacks, Queues, Graphs, etc.

CSE 373 23SU

22

23 of 25

Quick ADT Review

List Case Study

Generics

Questions

CSE 373 23SU

23

24 of 25

Quick ADT Review

List Case Study

Questions?

CSE 373 23SU

24

25 of 25

That’s all!

CSE 373 23SU

25