CS计算机代考程序代写 prolog data structure compiler Java Haskell ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II
List: recursive list processing

by

Marcel Turcotte

Version March 22, 2020

Preamble

Preamble

Overview

Overview

List: recursive list processing

We revisit the concept of recursivity, this time in the context of processing linked lists. We
develop a general strategy, “head & tail”, that can be applied to all the problems covered
in this course.

General objective:
This week, you will be able to design recursive methods for processing linked lists.

1 88

«To iterate is human, to recurse divine»
L. Peter Deutsch

Preamble

Learning objectives

Learning objectives

Recognize the problems for which recursion is appropriate.
Discuss the efficiency of recursive list processing in Java, especially in relation to
memory consumption.
Explain the role of parameters to control the flow of recursive program execution.
Paraphrase the “head & tail” for recursive processing of lists.
Use the “head & tail” strategy to design a recursive method for processing a linked
list.

Readings:
Pages 233-238 of E. Koffman and P. Wolfgang.

3 88

Preamble

Plan

Plan

1 Preamble

2 Theory

3 Implementation

4 Principles

5 Prologue

4 88

Theory

Discussion

What problems have you solved using recursivity?
What do these problems have in common?

5 88

Theory

The solution to a given problem can be constructed from the solutions of the
subproblems;
These sub-problems are of the same nature and therefore can be solved in the
same way;
The sub-problems are getting smaller and smaller (convergence);
Finally, there is a size of problems that can be solved in a trivial way, without
recursive calls, which are the base cases.

6 88

Remarks

Recursivity and iteration are of the same nature.
It is important that the size of the problems to be handled decreases, otherwise
there would be an infinite number of recursive calls (equivalent to the infinite
loop); in practice the program will terminate when all the memory reserved for
method calls is exhausted.
So there has to be a size of problem that can be solved without recursive calls,
in order to stop recursivity.
These are the base cases. There has to be at least one, but there can be more
than one.
The base cases should be processed first in order to stop the recursion, if
necessary.

7 88

Remarks (continued)

The programming languages Lisp, Prolog and Haskell, to name but a few, have no
iterative control statements, iteration is replaced by recursivity.

Compilers automatically transform some forms of recursivity into iteration.
The XSLT Transformations technology used in particular for certain Web
applications is based on the concept of recursivity.
Some treatments of binary search trees will be very simple to express using
recursivity, but very complex otherwise.

8 88

Theory

Pattern

Pattern

t ype method ( pa ramete r s ) {

type r e s u l t ;

i f ( t e s t ) { // base ca se

r e s u l t = c a l c u l a t i n g the r e s u l t // no r e c u r s i v e c a l l

} e l s e { // g e n e r a l ca s e

// pre−p r o c e s s i n g : p a r t i t i o n i n g the data

r e s u l t = method ( sub−problem ) ; // r e c u r s i v e c a l l

// post−p r o c e s s i n g : combine the r e s u l t
}

re tu rn r e s u l t ;
}

9 88

Theory

Factorial

Factorielle

pub l i c s t a t i c i n t f a c t o r i a l ( i n t n ) {
i n t s , r e s u l t ;
i f (n<=1) { // base ca se r e s u l t = 1 ; } e l s e { // g e n e r a l ca s e i n t n1 = n−1; s = f a c t o r i a l ( n1 ) ; r e s u l t = n ∗ s ; } re tu rn r e s u l t ; } The above method corresponds to the proposed model: First we check the base case, its result is calculated without recursive call (recursivity stops here!); The general case creates smaller and smaller subproblems. 10 88 Factorial — a terse implementation pub l i c s t a t i c i n t f a c t o r i a l ( i n t n ) { i f (n<=1) { re tu rn 1 ; } re tu rn n ∗ f a c t o r i a l ( n −1); } The statement return returns control to the caller, it stops the execution of the method, no other statement of this call will be executed. 11 88 Factorial — a terse implementation pub l i c s t a t i c i n t f a c t o r i a l ( i n t n ) { i f (n<0) { throw new I l l e g a l A r g u m e n t E x c e p t i o n ( I n t e g e r . t o S t r i n g ( n ) ) ; } i f (n<=1) { re tu rn 1 ; } re tu rn n ∗ f a c t o r i a l ( n −1); } 12 88 Theory : “head & tail” Let’s establish a general strategy for recursive list processing. Breaking the list into two parts, the first element (head) and the rest of the list (tail)∗ ∗Here, head and tail are not the instance variables. 13 88 Implementation Implementation of the class LinkedList We’ll use a singly linked list. pub l i c c l a s s L i n k e d L i s t implements L i s t {

p r i v a t e s t a t i c c l a s s Node {
p r i v a t e T v a l u e ;
p r i v a t e Node next ;
p r i v a t e Node (T va lue , Node next ) {

t h i s . v a l u e = v a l u e ;
t h i s . nex t = next ;

}
}

p r i v a t e Node head ;

// . . .
}

14 88

Implementation

size

Calculating the size of a list

Let’s first consider calculating the size of a list.
Let current, a variable of type Node, designate an element of the list.
Knowing that the size of the list starting with the element designated by
current.next is n,

what is the size of the list starting with the element designated current?
The size of the list starting with the element designated by current is n+1.

15 88

Calculating the size of a list

The strategy “head & tail” suggests that we start by posing the recursive call,
passing current.next.
i n t n = s i z e ( c u r r e n t . nex t ) ;

What’s the value of n? What does n mean?
This is the length of the list starting with the element designated by current.next.

What is the size of the list starting with the element designated current?
The length of the list starting with the element designated by current is n+1.

16 88

Calculating the size of a list

What’s the shortest valid list and how long is it?
It’s the empty list and its length is 0.

What is the value of current if the list is empty?
The value of current is null.

17 88

Calculating the size of a list

This suggests the following partial implementation:
i n t n ;

i f ( c u r r e n t == nu l l ) {

n = 0 ;

} e l s e {

n = 1 + s i z e ( c u r r e n t . nex t ) ;

}

What is the type of the parameter for the method size?
The type of the parameter is Node.

18 88

Calculating the size of a list

i n t s i z e ( Node c u r r e n t ) {

i n t n ;

i f ( c u r r e n t == nu l l ) {

n = 0 ;

} e l s e {

n = 1 + s i z e ( c u r r e n t . nex t ) ;

}

re tu rn n ;
}

19 88

i n t s i z e ( Node c u r r e n t ) {
i f ( c u r r e n t == n u l l ) {

r e t u r n 0 ;
}
r e t u r n 1 + s i z e ( c u r r e n t . nex t ) ;

}

Remarks

Notice that the method size uses no instance variables!
One controls recursivity using the parameter.
Each call has its own working memory (activation block) and therefore its own copies
of the local variables and parameters.

i n t s i z e ( Node c u r r e n t ) {

i f ( c u r r e n t == nu l l ) {
re tu rn 0 ;

}

re tu rn 1 + s i z e ( c u r r e n t . nex t ) ;
}

The base case is checked out first.

22 88

Calling the method size

How do we use this method to calculate the size of the list starting with the node
designated by head?
i n t s i z e ( Node c u r r e n t ) {

i f ( c u r r e n t == nu l l ) {
re tu rn 0 ;

}
re tu rn 1 + s i z e ( c u r r e n t . nex t ) ;

}

i n t s i z e ( ) {
re tu rn s i z e ( head ) ;

}

23 88

The recursive method is a helper

The first call is initiated by a method of visibility public. The value of head is passed
as a parameter.
pub l i c i n t s i z e ( ) {

re tu rn s i z e ( head ) ;
}

The recursive method must be of visibility private since its parameter is of type
Node.
p r i v a t e i n t s i z e ( Node c u r r e n t ) {

i f ( c u r r e n t == nu l l ) {
re tu rn 0 ;

}
re tu rn 1 + s i z e ( c u r r e n t . nex t ) ;

}

24 88

head

B CA

pub l i c i n t s i z e ( ) {
r e t u r n s i z e ( head ) ;

}

p r i v a t e i n t s i z e ( Node c u r r e n t ) {
i f ( c u r r e n t == n u l l ) {

r e t u r n 0 ;
}
r e t u r n 1 + s i z e ( c u r r e n t . nex t ) ;

}

In practice

Each call has its own activation block (working memory) on the call stack, so the
size of the system stack will be proportional to the size of the list.

26 88

Implementation

Summary

Summary

t ype method ( Node c u r r e n t ) {
type r e s u l t ;
i f ( c u r r e n t . . . ) { // base ca se

c a l c u l a t i n g the r e s u l t // no r e c u r s i v e c a l l
} e l s e { // g e n e r a l ca s e

// pre−p r o c e s s i n g
s = method ( c u r r e n t . nex t ) ; // r e c u r s i o n

// post−p r o c e s s i n g
}
re tu rn r e s u l t ;

}

27 88

“head & tail”

Steps:
What does method(current.next) mean?

The solution to a problem, smaller by an element.
How are we going to use this result to construct a solution for a list beginning with
the element designated by current?
What are the base cases?

What’s the shortest valid list?
What’s the result?

28 88

Implementation

findMax

LinkedList

Let’s now use a list whose elements have a method compareTo.
pub l i c c l a s s L i n k e d L i s t > {

p r i v a t e s t a t i c c l a s s Node {
p r i v a t e T v a l u e ;
p r i v a t e Node next ;
p r i v a t e Node (T va lue , Node next ) {

t h i s . v a l u e = v a l u e ;
t h i s . nex t = next ;

}
}

p r i v a t e Node head ;

// . . .
}

29 88

findMax

Let’s apply the strategy as suggested.
r e s u l t = f indMax ( c u r r e n t . nex t ) ;

What’s the value of result? What does result mean?
The largest value for the list beginning with the element designated current.next

What do we do if result is greater than current.value?
i f ( r e s u l t . compareTo ( c u r r e n t . v a l u e ) > 0) {

re tu rn r e s u l t ;
} e l s e {

re tu rn c u r r e n t . v a l u e ;
}

30 88

findMax

This process builds smaller and smaller problems. What’s the shortest valid list?
No, not the empty list, but the list containing only one element.

What’s the returned value going to be?
i f ( c u r r e n t . nex t == nu l l ) {

re tu rn c u r r e n t . v a l u e ;
}

31 88

pub l i c E findMax ( ) {
i f ( head == nu l l ) {

throw new NoSuchElementExcept ion ( ) ;
}
re tu rn f indMax ( head ) ;

}

p r i v a t e E findMax ( Node c u r r e n t ) {

i f ( c u r r e n t . nex t == nu l l ) {
re tu rn c u r r e n t . v a l u e ;

}

E r e s u l t = findMax ( c u r r e n t . nex t ) ;

i f ( r e s u l t . compareTo ( c u r r e n t . v a l u e ) > 0) {
re tu rn r e s u l t ;

} e l s e {
re tu rn c u r r e n t . v a l u e ;

}
}

head

B CA

p r i v a t e E findMax ( Node p ) {
i f ( p . nex t == n u l l ) {

r e t u r n p . v a l u e ;
}
E r = findMax ( p . nex t ) ;
i f ( r . compareTo ( p . v a l u e ) > 0) {

r e t u r n r ; ‘
} e l s e {

r e t u r n p . v a l u e ;
}

}

Each of the following examples
introduces a new problematic.

Implementation

E get(int index)

E get(int index)

The method E get(int index) returns the element at the specified value (index) of
the list.
What was the strategy adopted for the non-recursive method?

It was necessary to count the number of visited nodes and to stop the execution of the
loop while after having visited index nodes.

For a recursive method, how do we determine the number of nodes visited?
We could add a parameter to count the number of nodes visited. Initially 0, then 1, 2,
etc.

35 88

Study the following partial implementation:
pub l i c E get ( i n t i n d e x ) {

re tu rn get ( head , i n d e x ) ;
}

p r i v a t e E get ( Node c u r r e n t , i n t i n d e x ) {
. . .

}

If index represents the position of the element in relation to the list starting at
position current, what is the position of the element in relation to the list starting at
position current.next?

That’s right, index-1.
What will the method do if the value of the index is 0?

It must return current.value.
No recursive call is made.
That’s the base case.

E get(int index)

p r i v a t e E get ( Node c u r r e n t , i n t i n d e x ) {

i f ( i n d e x == 0) {
re tu rn c u r r e n t . v a l u e ;

}

re tu rn get ( c u r r e n t . next , index −1);

}

What would happen if the initial value of the index was greater than the total
number of items on the list?

index > 0 and current == null

37 88

E get(int index)

p r i v a t e E get ( Node c u r r e n t , i n t i n d e x ) {

i f ( c u r r e n t == nu l l ) {
throw new IndexOutOfBoundsExcept ion ( ) ;

}

i f ( i n d e x == 0) {
re tu rn c u r r e n t . v a l u e ;

}

re tu rn get ( c u r r e n t . next , index −1);

}

38 88

pub l i c E get ( i n t i n d e x ) {
i f ( i n d e x < 0) { throw new IndexOutOfBoundsExcept ion ( ) ; } re tu rn get ( head , i n d e x ) ; } p r i v a t e E get ( Node c u r r e n t , i n t i n d e x ) {

i f ( c u r r e n t == nu l l ) {
throw new IndexOutOfBoundsExcept ion ( ) ;

}

i f ( i n d e x == 0) {
re tu rn c u r r e n t . v a l u e ;

}

re tu rn get ( c u r r e n t . next , index −1);
}

head

B CA
p r i v a t e E get ( Node p , i n t i n d e x ) {

i f ( i n d e x == 0) {
r e t u r n p . v a l u e ;

}
r e t u r n get ( p . next , index −1);

}

Implementation

int indexOf(E element)

int indexOf(E element)

The method indexOf returns the position of the leftmost occurrence of the element
in this list, and −1 if the value is not found there.
The numbering of the elements starts at zero.

41 88

int indexOf(E element)

According to the “head & tail” strategy, the general case will involve a recursive call
such as this:
s = indexOf ( c u r r e n t . next , e l ement ) ;

What does the value of s represent?
It’s the position of the element in the list designated by current.next.

Compared to the current list, the one designated by current, what is the position of
element?

s + 1

42 88

int indexOf(E element)

If the value of s is greater or equal to zero, s is the position of the element in
the rest of list.
What does s == -1 mean?

The element was absent from the rest of the list.
Which case hasn’t been dealt with?

current.value.equals(element)
What value should we return then?

0

43 88

int indexOf(E element)

s = indexOf ( c u r r e n t . next , e l ement ) ;

i f ( c u r r e n t . v a l u e . e q u a l s ( e l ement ) ) {
r e s u l t = 0 ;

} e l s e i f ( s == −1) {
r e s u l t = s ;

} e l s e {
r e s u l t = 1 + s ;

}

44 88

int indexOf(E element)

What’s the base case?
The shortest list is the empty list, it doesn’t contain the element you’re looking for,
just return the special value -1.

i f ( c u r r e n t == nu l l ) {
re tu rn −1;

}

45 88

int indexOf(E element)

p r i v a t e i n t i ndexOf ( Node c u r r en t , E e lement ) {

i f ( c u r r e n t == nu l l ) {
re tu rn −1;

}

i n t r e s u l t = indexOf ( c u r r e n t . next , e l ement ) ;

i f ( c u r r e n t . v a l u e . e q u a l s ( e l ement ) ) {
re tu rn 0 ;

}

i f ( r e s u l t == −1) {
re tu rn r e s u l t ;

}

re tu rn r e s u l t + 1 ;
}

46 88

int indexOf(E element)

Is it working?
Yes.

There’s still a problem with that implementation.
What is it?

47 88

head

i n t i ndexOf ( Node p , E e ) {
i f ( p == n u l l ) r e t u r n −1;
i n t r = indexOf ( p . next , e ) ;
i f ( p . v a l u e . e q u a l s ( e ) ) r e t u r n 0 ;
i f ( r == −1) r e t u r n r ;
r e t u r n r + 1 ;

}

int indexOf(E element)

How do we stop recursive calls as soon as the value we’re looking for is found?
p r i v a t e i n t i ndexOf ( Node c u r r e n t , E e lement ) {

i f ( c u r r e n t == nu l l ) {
re tu rn −1;

}
i n t r e s u l t = indexOf ( c u r r e n t . next , e l ement ) ;
i f ( c u r r e n t . v a l u e . e q u a l s ( e l ement ) ) {

re tu rn 0 ;
}
i f ( r e s u l t == −1) {

re tu rn r e s u l t ;
}
re tu rn r e s u l t + 1 ;

}

49 88

int indexOf(E element)

p r i v a t e i n t i ndexOf ( Node c u r r en t , E e lement ) {

i f ( c u r r e n t == nu l l ) {
re tu rn −1;

}

i f ( c u r r e n t . v a l u e . e q u a l s ( e l ement ) ) {
re tu rn 0 ;

}

i n t r e s u l t = indexOf ( c u r r e n t . next , e l ement ) ;

i f ( r e s u l t == −1) {
re tu rn r e s u l t ;

}

re tu rn r e s u l t + 1 ;
}

50 88

Implementation

E indexOfLast(E element)

E indexOfLast(E element)

The method indexOfLast returns the position of the last (rightmost) occurrence of
the element, and -1 otherwise.
What are the changes to be made?
Can current.value.equals(element) be part of the base case?

No, recursion must go through the entire list.
How to process the result indexOfLast(current.next, element)?

51 88

pub l i c i n t i n dexOfLa s t (E e lement ) {
re tu rn i n dexOfLa s t ( head , e l ement ) ;

}

p r i v a t e i n t i n dexOfLa s t ( Node c u r r e n t , E e l ement ) {

i f ( c u r r e n t == nu l l ) {
re tu rn −1;

}

i n t r e s u l t = indexOfLa s t ( c u r r e n t . next , e l ement ) ;

i f ( r e s u l t > −1) {
re tu rn r e s u l t + 1 ;

} e l s e i f ( e l ement . e q u a l s ( c u r r e n t . v a l u e ) ) {
re tu rn 0 ;

}

re tu rn −1;
}

Implementation

boolean contains(E element)

Exercise

boolean contains(E element)

53 88

Implementation

boolean isIncreasing()

boolean isIncreasing()

The methods size, indexOf and contains only deal with one element at a time.
Let’s consider a recursive implementation of the method isIncreasing.
Examine each consecutive pair and return the value false as soon as a pair is not
increasing.
If the method attains the end of the list then the list is ascending!

54 88

boolean isIncreasing()

pub l i c boolean i s I n c r e a s i n g ( ) {
re tu rn i s I n c r e a s i n g ( head ) ;

}

55 88

boolean isIncreasing()

What’s the base case?
What’s the shortest valid list?

The empty list and the singleton are growing.

i f ( ( c u r r e n t == nu l l ) | | ( c u r r e n t . nex t == nu l l ) ) {
re tu rn t rue ;

}

56 88

boolean isIncreasing()

General case.
Which approach is preferable?
1. Do a recursive call, then process the result.
2. Process the current position, then do a recursive recursive call.

i f ( c u r r e n t . v a l u e . compareTo ( c u r r e n t . nex t . v a l u e ) > 0) {
re tu rn f a l s e ;

} e l s e {
re tu rn i s I n c r e a s i n g ( c u r r e n t . nex t ) ;

}

57 88

boolean isIncreasing()

p r i v a t e boolean i s I n c r e a s i n g ( Node c u r r e n t ) {

i f ( ( c u r r e n t == nu l l ) | | ( c u r r e n t . nex t == nu l l ) ) {
re tu rn t rue ;

}

i f ( c u r r e n t . v a l u e . compareTo ( c u r r e n t . nex t . v a l u e ) > 0 ) {
re tu rn f a l s e ;

}

re tu rn i s I n c r e a s i n g ( c u r r e n t . nex t ) ;
}

58 88

Implementation

Exercises

Exercices

void addLast(E element)
boolean equals(LinkedList other)

59 88

Implementation

void remove(E element)

void remove(E element)

We’re now considering methods that transform the structure of the list.
For the methods indexOf and contains, the main consequence of additional
recursive calls is the inefficiency of the method.
On the other hand, recursive methods that transform lists can lead to more serious
problems.
Consider the example of the method remove, which removes the first occurrence of
an object in the list.

60 88

void remove(E element)

Give the the high-level strategy.
Traverse the list.
Find the element.
Remove the element.

61 88

public void remove(E element)

What will be the difficulties?
We’ll remember that when traversing a singly linked list using a while loop, we had to
stop one position before the element to be removed, since it’s the variable next of the
preceding element that has to be modified.
To remove the first element, we must modify the variable head of the header, and not
the variable next of the preceding node.

62 88

public void remove(E element)

What are the preconditions?
element != null
The list is not empty.

What are the special cases?
The element being sought is in first position.

63 88

public void remove(E element)

pub l i c vo id remove (E e lement ) {

i f ( e l ement == nu l l ) {
throw new N u l l P o i n t e r E x c e p t i o n ( ” I l l e g a l argument ” ) ;

}

i f ( head == nu l l ) {
throw new NoSuchElementExcept ion ( ) ;

}

i f ( head . v a l u e . e q u a l s ( e l ement ) ) {
head = head . nex t ;

} e l s e {
remove ( head , e l ement ) ;

}

}

64 88

Remarks

For the first call to the method remove(Node current, E element), we know
that current.value.equals(element) is false. Why?

It’s the first call, current == head.
If head.value.equals(element) were true at the time of the call to the public method,
then there would have been no call to the private method.

The recursive method will preserve this property, it checks if the sought element,
element, is at the position that follows, current.next, and if yes, removes this node
and finishes, otherwise it continues its search.

65 88

remove(Node current, E element)

General case: Which scenario seems the most appropriate:
1. Do a recursive call, followed by a post-processing?
2. Do a pre-processing, followed by a recursive call (if necessary)?

Since we have to remove the leftmost element, should we do a pre-processing followed
by a recursive call (if necessary)? (Strategy 2)

66 88

remove(Node current, E element)

What’s the necessary pre-processing?
If current.next.value.equals(element), remove the next element.
Otherwise, process the rest of the list (recursive call).

67 88

remove(Node current, E element)

What’s the base case?
Singleton.
What do we do now?

Throw the exception NoSuchElementException.

68 88

remove(Node current, E element)

p r i v a t e vo id remove ( Node c u r r e n t , E e lement ) {

i f ( c u r r e n t . nex t == nu l l ) {
throw new NoSuchElementExcept ion ( ) ;

}

i f ( c u r r e n t . nex t . v a l u e . e q u a l s ( e l ement ) ) {
c u r r e n t . nex t = c u r r e n t . nex t . nex t ; // base ca se

} e l s e {
remove ( c u r r e n t . next , e l ement ) ; // g e n e r a l ca s e

}
}

69 88

pub l i c vo id remove (E e lement ) {
i f ( e l ement == n u l l ) {

throw new N u l l P o i n t e r E x c e p t i o n ( ” I l l e g a l argument ” ) ;
}
i f ( head == n u l l ) {

throw new NoSuchElementExcept ion ( ) ;
}
i f ( head . v a l u e . e q u a l s ( e l ement ) ) {

head = head . nex t ; // s p e c i a l c a s e
} e l s e {

remove ( head , e l ement ) ;
}

}

p r i v a t e vo id remove ( Node c u r r e n t , E e l ement ) {
i f ( c u r r e n t . nex t == n u l l ) {

throw new NoSuchElementExcept ion ( ) ;
}
i f ( c u r r e n t . nex t . v a l u e . e q u a l s ( e l ement ) ) {

c u r r e n t . nex t = c u r r e n t . nex t . nex t ; // base ca se
} e l s e {

remove ( c u r r e n t . next , e l ement ) ; // g e n e r a l ca s e
}

}

Exercises

void removeLast()
void removeLast(E element)
void removeAll(E element)
void remove(int pos)

71 88

Implementation

LinkedList subList(int fromIndex, int toIndex)

LinkedList subList(int fromIndex, int
toIndex)

The method will return a new list containing the elements located between the
positions fromIndex and toIndex of the original list, without changing it.

72 88

Discussion

Propose a strategy to build the resulting list.
1. Post-processing

Traverse the list to the highest index;
Return a list containing only the value at that position;
Add the current element to the start of the list, if its position is within the range.

2. Pre-processing
An empty list is passed as a parameter to the first call;
Add the current element to the end of the list, if the current position is part of the
interval;
Recusive call.

73 88

Strategy 1

Recursive calls traverse the list from left to right, recursion stops when the index
toIndex is reached.

Base Case:

L i n k e d L i s t r e s u l t ;

i f ( i n d e x == t o I n d e x ) {
r e s u l t = new L i n k e d L i s t () ;
r e s u l t . a d d F i r s t ( c u r r e n t . v a l u e ) ;

}

74 88

Strategy 1

General case:
r e s u l t = s u b L i s t ( c u r r e n t . next , i n d e x +1, f romIndex , t o I n d e x ) ;

What does result contain?
What’s the next step?

i f ( i n d e x > f romIndex ) {
r e s u l t . a d d F i r s t ( c u r r e n t . v a l u e ) ;

}

75 88

pub l i c L i n k e d L i s t s u b L i s t ( i n t f romIndex , i n t t o I n d e x ) {
r e t u r n s u b L i s t ( head , 0 , f romIndex , t o I n d e x ) ;

}

p r i v a t e L i n k e d L i s t s u b L i s t ( Node c u r r e n t , i n t i ndex , i n t f romIndex , i n t t o I n d e x ) {

L i n k e d L i s t r e s u l t ;

i f ( i n d e x == t o I n d e x ) {

r e s u l t = new L i n k e d L i s t () ;
r e s u l t . a d d F i r s t ( c u r r e n t . v a l u e ) ;

} e l s e {

r e s u l t = s u b L i s t ( c u r r e n t . next , i n d e x +1, f romIndex , t o I n d e x ) ;

i f ( i n d e x >= fromIndex ) {
r e s u l t . a d d F i r s t ( c u r r e n t . v a l u e ) ;

}
}

r e t u r n r e s u l t ;
}

The handling of the preconditions (range of illegal values) is left as exercise.

Strategy 2

For the second strategy, the list of results is created at the outset and elements
are inserted while traversing the list.

pub l i c L i n k e d L i s t s u b L i s t ( i n t f romIndex , i n t t o I n d e x ) {

L i n k e d L i s t r e s u l t = new L i n k e d L i s t () ;

s u b L i s t ( head , 0 , r e s u l t , f romIndex , t o I n d e x ) ;

r e t u r n r e s u l t ;
}

77 88

Strategy 2

Base Case:
i f ( i n d e x == t o I n d e x ) {

r e s u l t . addLast ( c u r r e n t . v a l u e ) ;
}

result.addLast(current.value) ou result.addFirst(current.value)?

78 88

Strategy 2

General case:
i f ( i n d e x >= fromIndex ) {

r e s u l t . addLast ( c u r r e n t . v a l u e ) ;
}
s u b L i s t ( c u r r e n t . next , i n d e x +1, r e s u l t , f romIndex , t o I n d e x ) ;

result.addLast(current.value) ou result.addFirst(current.value)?

79 88

pub l i c L i n k e d L i s t s u b L i s t ( i n t f romIndex , i n t t o I n d e x ) {

L i n k e d L i s t r e s u l t = new L i n k e d L i s t () ;

s u b L i s t ( head , 0 , r e s u l t , f romIndex , t o I n d e x ) ;

r e t u r n r e s u l t ;
}

p r i v a t e vo id s u b L i s t ( Node c u r r e n t , i n t i ndex , L i n k e d L i s t r e s u l t ,
i n t f romIndex , i n t t o I n d e x ) {

i f ( i n d e x == t o I n d e x ) {

r e s u l t . addLast ( c u r r e n t . v a l u e ) ;

} e l s e {

i f ( i n d e x >= fromIndex ) {
r e s u l t . addLast ( c u r r e n t . v a l u e ) ;

}

s u b L i s t ( c u r r e n t . next , i n d e x +1, r e s u l t , f romIndex , t o I n d e x ) ;
}

}

Principles

Principles

Parameters play an essential role when writing recursive methods.
A parameter of type Node, current, plays a key role in controlling the execution
of the method.

Sample tests for the base case:
current == null
current.next == null
current.value.equals(element)
current.next.value.equals(element)

General case:
The value of current.next is passed as a parameter for the recursive call in order to
process the rest of the list.

81 88

Principles

There are two mechanisms for passing information between calls.
1. Parameters:

A counter: If each call must know its position in the list, the value of a counter is
passed as a parameter, and each call passes to the value plus one.

We could also decrement the value with each call.
2. Return value:

The method size returns the size of the list from the element designated by its
parameter current.

For the caller, the size of the list is one more than the returned value.

82 88

t ype method ( Node c u r r e n t ) {

type r e s u l t ;

i f ( c u r r e n t . . . ) { // base ca se

c a l c u l a t i n g the r e s u l t // no r e c u r s i v e c a l l

} e l s e { // g e n e r a l ca s e

// pre−p r o c e s s i n g

s = method ( c u r r e n t . nex t ) ; // r e c u r s i o n

// post−p r o c e s s i n g

}

re tu rn r e s u l t ;
}

«head & tail»

Steps:
What does method(current.next) mean?

The solution to a problem, smaller by an element.
How are we going to use this result to construct a solution for a list beginning with
the current element?
What are the base cases?

What’s the shortest valid list?
What’s the result?

84 88

Prologue

Summary

We proposed the “head & tail” strategy
Base case: usually a test involving the value of current.
General case: recursive call passing the value of current.next as a parameter.

We control recursivity using the parameters.

85 88

Next module

Binary Research Trees: concept

86 88

References I

E. B. Koffman and Wolfgang P. A. T.
Data Structures: Abstraction and Design Using Java.
John Wiley & Sons, 3e edition, 2016.

87 88

Marcel Turcotte
Marcel.

School of Electrical Engineering and Computer Science (EECS)
University of Ottawa

88 / 88

Marcel.

Preamble
Overview
Learning objectives
Plan

Theory
Pattern
Factorial

Implementation
size
Summary
findMax
E get(int index)
int indexOf(E element)
E indexOfLast(E element)
boolean contains(E element)
boolean isIncreasing()
Exercises
void remove(E element)
LinkedList subList(int fromIndex, int toIndex)

Principles
Prologue