Data Structures

<Lecture 3: JAVA 2>

Sungmin Cha
New York University

09.11.2024
 Outline
• Review the previous lecture

• JAVA
– Group discussion
– Example 1
– Example 2
– Example 3

2
 Outline
• Review the previous lecture

• JAVA
– Group discussion
– Example 1
– Example 2
– Example 3

3
 JAVA’s Variables
• JAVA’s 8 primitive type variables
– There are 8 primitive types that save a data value
– These are allocated into Stack memory
Primitive Values Primitive Size
Datatypes
byte 1 byte
short 2 bytes
Integers
Numbers int 4 bytes
long 8 bytes
Floating float 4 bytes
Values
double 8 bytes
Character char 2 bytes
Boolean boolean 1 bit 4
 Primitive Types
• Memory allocation of primitive type variables
– Example:
 abstracted figure

x
int x;
x=5;
5 Stack memory

0x12AB5

5
 Reference Types
• JAVA’s reference types
– All types except for primitive types
 Class, Array, etc.
– Refer to the object through the location value
– In Stack, a reference variable is allocated
 The real object is allocated to Heap

6
 Reference Types
• Memory allocation of reference type variables
– Example:

Circle c;
c = new circle(15);

c radious = 15 heap

stack 0x3EF3B 0x3EF3B

0x4AF23
7
 Stack and Heap Memory
• Stack
– Stack is where all the local variables and temporary
information for functions/methods are stored.
– It is organized in a collection of memory blocks, called stack
frames.
Stack

bat(15)

bar(15)

foo

main
8
 Stack and Heap Memory
• Arrays and Heap
– Arrays in JAVA are always stored on the heap in consecutive
memory locations
– Example:
Allocate object on the heap Size = 4byte * 10

address 100 104 108 112 … 136

0 0 0 0 0 0 0 0 0 0 heap

array

stack 100
9
 Outline
• Review the previous lecture

• JAVA
– Group discussion
– Example 1
– Example 2
– Example 3

10
 Group Discussion
• Group discussion
– Make a group consisting of 2-4 students
– Solve examples together with group members
 In both the main lecture and recitation

11
 Examples
• Example 1: what happens in memory
– Assume that there is a class called Circle. It has a public data
field called radius.
– It has a one-parameter constructor that takes a radius of a circle
as its argument and creates a Circle object with that radius.

12
 Examples
• Example 1: what happens in memory
What is the
What is the output memory layout of
of this code? this code?

13
 Examples
• Example 1: what happens in memory

Heap
Stack

14
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10 = 20

Stack

c1 c2 c3

15
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10 = 20

Stack

c1 c2 c3

16
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10
30 = 20

Stack

c1 c2 c3

17
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10
30 = 20

Stack

c1 c2 c3

18
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10
30 = 20

Stack

c1 c2 c3

19
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10
30 = 20

Stack

c1 c2 c3

20
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10
30 = 20
5

Stack

c1 c2 c3

21
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10
30 = 20
5

Stack

c1 c2 c3

22
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10
30 = 20
5

Stack

c1 c2 c3

23
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10
30 = 20
5

Stack

c1 c2 c3

24
 Examples
• Example 1: what happens in memory

Heap
Radius Radius
= 10
15
30 = 20
5

Stack

c1 c2 c3

25
 Examples
• Example 2: what happens in memory

– How is the above array laid out in memory?

– Assuming the code fragment is part of a main function,
what is stored on the stack and what is stored in the heap?

– How does the memory image change?

26
 Examples
• Example 2: what happens in memory
Heap
Stack

27
 Examples
• Example 2: what happens in memory
Heap
Stack

28
 Examples
• Example 3: swap function
– Given the swap function, consider the following code fragment

– If we execute the below code after the call to swap function,

what will be output be?
– How does the memory layout of the Stack change?

29
 Examples
• Example 3: swap function (for primitive variables)
– What happens in memory for swap function? Stack

30
 Examples
• Example 3: swap function (for reference variables)
– Given the swap function, consider the following code fragment

– If we execute the above code, what will be output be?

– How does the layout of both the Stack and Heap change?
31
 Examples
• Example 3: swap function (for reference variables)
– What happens in memory for swap3 function? Stack
Heap

32
 Pass-by-value
• JAVA employs pass-by-value!
– The function parameter values are copied to another variable
and then the copied object is passed to the function.
– For primitive variables, the real value is stored in the Stack
 As a result, it sends the copied real value to the function
– In the case of reference variables, the actual location of the
object allocated in the Heap is stored in the Stack
 Hence, it sends the copied location of the object to the function

33
 Examples
• Example 4: new swap function
– What happens in memory for swap function? Stack

How to swap num1

and num2?

main
num1 = 3.1415
num2 = 2.1718
3.1415 2.1718
34
 Examples
• Example 4: new swap function
– Let’s make a simple function that swaps a value in two floating-
point variables.
– Goal
1. Take two inputs of the actual number and save them into a variable
2. Print a value saved in the variable
3. Apply swap function
4. Print a value saved in the variable
– Hints
 Using other types of variable
 Using a primitive variable but applying a trick based on the
characteristic of local variable in Stack memory

35
 Examples
• Example 4: new swap function
– Brightspace/Contents/Tools/Ed discussion/Ed workspace
– Public/swap function

36
 Examples
• Example 4: new swap function
– Fork workspace

– You can share and

work with group members

37
 Other Contents
• For JAVA programming..
– System.out.println, java.util.Scanner
– Class, Overriding, Interface, Generic
– Other packages
– Garbage Collection
– …

38
 Overview of this course
• Two parts of this course
1. Preliminary (1-2 weeks)
 JAVA programming
 Algorithm complexity and recursion.

2. Data Structures (12 weeks)

 Linear Data Structures (e.g., Array, List, Stack, etc.)
 Basic sorting algorithms
 Non-linear Data Structures (e.g., Tree and Graph, etc.)

39
 Thank you!

E-mail: sungmin.cha@nyu.edu

40