ITI 1121. Introduction to Computing II – subtitle
ITI 1121. Introduction to Computing II
Stack: linked elements
by
Marcel Turcotte
Version February 9, 2020
Preamble
Preamble
Overview
Stack: linked elements
We implement a stack using linked elements.
General objective:
This week you will be able to implement a stack using linked elements.
Preamble
Learning objectives
Learning objectives
Implement a stack using linked elements.
Compare the implementations using arrays and linked elements of a stack.
Readings:
Pages 75-83, 157-159 of E. Koffman and P. Wolfgang.
2 38
Preamble
Plan
Plan
1 Preamble
2 Implementation using linked elements
3 Prologue
3 38
Implementation using linked elements
Implementation of a stack using
linked elements
Implementation using linked elements
Reminder
On the implementation of a stack using an
array
Access to the elements of an array is very fast, it always requires a constant
number of operations.
However, since arrays have a fixed size, there are some applications for which they
are not appropriate.
A frequently used technique to get around this limitation is to copy the elements of
the array into a new, larger array and replace the old one with the new one (dynamic
arrays).
On the other hand, this makes the insertions more expensive (compared to the
execution time because you have to copy all the elements of the old array to the new
one) and memory usage is increased because the physical size of the data structure
will generally be larger than its logical size.
5 38
Implementation using linked elements
Motivation
Linked structures
Let’s now consider an implementation always using an amount of memory proportional
to the number of elements contained in the structure.
p
13:00 14:30
These structures are efficient, in terms of execution time (for some operations),
because they avoid copying elements.
The structures considered here are linear, i.e. each element has a predecessor and a
successor (except for the first and last element).
Unlike array-based data structures, the elements in those structures are not
contiguous in memory.
6 38
Implementation using linked elements
Experimentation
The class Elem
Consider the following declaration ∗:
c l a s s Elem
E v a l u e ;
Elem
}
What’s so special about the definition of Elem?
The instance variable next is a reference to an object of the class Elem.
Is it valid?
Try it for yourself!
> javac Elem.java
Yes, it’s valid, although it does seem circular.
∗The issue of the visibility of variables will be addressed shortly..
7 38
What’s that for?
Declaring a variable of type Elem:
Elem
Create an object of the class Elem:
new Elem
8 38
What’s that for?
Save the reference in the variable p..
Elem
Notation: I will always use circles to represent the objects of the class Elem. The top
part represents the instance variable value while the bottom part represents the variable
next.
9 38
What’s the point?
p
How do we change the content of the instance variable value of the newly created
object?
p
13:00
We use the dot-notation in order to access the attributes of the object.
10 38
What’s that for?
Create a new object of the class Elem.
new Elem
13:00
p
How do you link the elements together?
11 38
What’s that for?
p
13:00
The variable next of the object designated by the reference variable p receives the
reference of the newly created object Elem.
12 38
What’s that for?
p
13:00
Change the contents of the variable value of the newly created object.
13 38
What’s that for?
Create a new object of the class Elem.
new Elem
p
13:00 14:30
How do we link this element to the others?
14 38
What’s that for?
p
14:3013:00
Change the content of the variable value of the newly created object.
15 38
What’s that for?
p
13:00 14:30 16:00
p . nex t . nex t = p ;
What does the above statement do?
16 38
What’s that for?
p . nex t . nex t = p ;
A circular structure has been created!
The last item is no longer accessible;
It’ll be picked up by the garbage collector (System.gc()).
⇒ This is the basis of the linked structures: informations (values) are linked to each
other by links (references).
17 38
Implementation using linked elements
Linked structures
Linked strutures
c l a s s Elem
E v a l u e ;
Elem
}
Linked data structures, such as this one, allow us:
to represent linear data structures, such as stacks, queues and lists;
they always use a quantity of memory proportional to the number of elements;
all this is made possible because the class declares an instance variable whose type is
a reference to an object of the same class.
⇒ When the structures are linear like these, we talk about (singly) linked lists.
18 38
Summary
Linked structures are an alternative to arrays for saving values.
They always use a quantity of memory proportional to the number of elements
saved since each element is saved in its container, an object of the class Elem. Each
container is linked to the next one by a reference variable.
For now, we limit ourselves to linear structures, but graphs or trees are also
possible.
19 38
Implementation using linked elements
Constructor
Constructor
This is the usual constructor of the class Elem:
pub l i c c l a s s Elem
E v a l u e ;
Elem
Elem (E va lue , Elem
t h i s . v a l u e = v a l u e ;
t h i s . nex t = next ;
}
}
20 38
and the usual usage,
p = new Elem
“A”
p
q = new Elem
“A””B”
p
q
Implementation using linked elements
Implementing the Stack interface
Implementing a Stack using linked elements
pub l i c c l a s s LinkedStack
pub l i c boolean empty ( ) {
}
pub l i c vo id push (E o ) {
}
pub l i c E peek ( ) {
}
pub l i c E pop ( ) {
}
}
What are the instance variables?
22 38
Implementation using linked elements
Instance variables
What are the instance variables?
23 38
Which of the following two strategies is preferable?
top
s
63 2
bottom
s
36 2
6
2
3
Discussion
25 38
Implementation using linked elements
Nested class
Class Elem and encapsulation principle
The visibility of the instance variables is not acceptable. It is a violation of the
principle of encapsulation.
What options do we have?
26 38
pub l i c c l a s s Elem
p r i v a t e E v a l u e ;
p r i v a t e Elem
pub l i c Elem (E va lue , Elem
t h i s . v a l u e = v a l u e ;
t h i s . nex t = next ;
}
pub l i c vo id s e t V a l u e (E v a l u e ) {
t h i s . v a l u e = v a l u e ;
}
pub l i c vo id s e tNex t ( Elem
t h i s . nex t = next ;
}
pub l i c E getVa lue ( ) {
re tu rn v a l u e ;
}
pub l i c Elem
re tu rn next ;
}
}
Java: nested class
28 38
Java: nested
Elem is a nested class of the class LinkedStack.
Although the visibility of the class and its variables is private, the class LinkedStack
has access to the instance variables of the class Elem because its implementation is
nested.
For now, the nested classes will be “static”. We will use them as if they were
top-level classes except that 1) the declaration is nested and 2) the implementation is
accessible to the outside class.
Later we will see that there is a second category of nested classes.
29 38
Implementation using linked elements
Implementation of the methods
boolean isEmpty()
top
s
63 2
30 38
E peek()
top
s
63 2
31 38
void push(E value)
top
s
63 2
32 38
E pop()
top
s
63 2
33 38
Prologue
Summary
The concept of reference variable is central to linked implementations.
The class Elem has two instance variables, one of them is used to save an element of
information, the other one is used as a tether for the next element of the list.
35 38
Next module
Error handling in Java: Exception
36 38
References I
E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.
37 38
Marcel Turcotte
Marcel.
School of Electrical Engineering and Computer Science (EECS)
University of Ottawa
38 / 38
Marcel.
Preamble
Overview
Learning objectives
Plan
Implementation using linked elements
Reminder
Motivation
Experimentation
Linked structures
Constructor
Implementing the Stack interface
Instance variables
Nested class
Implementation of the methods
Prologue