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

ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II
List: concept

by

Marcel Turcotte

Version March 12, 2020

Preamble

Preamble

Overview

Overview

List: concept

Following our exploration of stacks and queues, we look at another linear abstract type of
data (ADT), the list. We discover the generality of this ADT. We mention the
implementation using an array, but we focus our attention on three implementations using
linked elements: the singly linked list, the doubly linked list, and the circular doubly linked
list, starting with a dummy node.

General objective :
This week, you will be able to design an industrial-grade implementation of the
abstract data type list.

1 52

Preamble

Learning objectives

Learning objectives

Explain the role of reference variables in the implementation of a linked list.
Design a method to traverse a singly linked list.

Readings:
Pages 63-84 of E. Koffman and P. Wolfgang.

2 52

Preamble

Plan

Plan

1 Preamble

2 Definitions

3 Implementations

4 Prologue

3 52

Definitions

Definition

A list (List) is an abstract data type (ADT) to store objects, such that each element has a
predecessor and a successor (thus linear, ordered), and having no data access
restrictions; one can inspect, insert or delete anywhere in the list. A.K.A. Sequence.

4 52

Operations

The basic operations are:
int size(): returns the number of saved elements; the empty list has a size of 0;

int get(int index): access to the elements is by position (or by content).
What will be the index of the first element in the list, 0 or 1?

As for the arrays, the first element is at position 0;
void add(int index, E elem): adding an element at any position;
void remove(int index): removal of an element by position (or content).

5 52

Remarks

So lists are more general than stacks and queues.
These can be implemented using a list.

6 52

List

pub l i c i n t e r f a c e L i s t {
vo id add ( i n t i ndex , E elem ) ;
boolean add (E elem ) ;
E remove ( i n t i n d e x ) ;
boolean remove (E o ) ;
E get ( i n t i n d e x ) ;
E s e t ( i n t i ndex , E e l ement ) ;
i n t i ndexOf (E o ) ;
i n t l a s t I n d e xO f (E o ) ;
boolean c o n t a i n s (E o ) ;
i n t s i z e ( ) ;
boolean i sEmpty ( ) ;

}

The interface above declares a subset of the methods of the interface java.util.List.

7 52

https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/util/List.html

Implementations

Implementations

ArrayList
LinkedList

Singly linked list
Doubly linked list
List with a dummy node
Iterative processing (Iterator)
Recursive processing.

New concepts will be introduced as needed to improve the efficiency of our implementations.
Efficiency with respect to the execution time and/or memory use; we will be mainly
interested in the execution speed.

8 52

Implementations

ArrayList

Discussion: implement List using an array

Summarize the main features of implementing a list using an array:
An instance variable designates an array;
An instance variable to count the number of elements;
We create the array in the constructor of the class;
We’re using the dynamic array technique.

Given a list containing the elements a, b, c and d, give the contents of the array after
the call add(2, z).
For the resulting list, give the result of the call remove(0).

9 52

Implementations

Singly linked list

Singly linked list

The simplest implementation is the singly linked list (SinglyLinkedList).
We will use a “static” nested class to represent the nodes in the list. Each node
contains a value and is connected to its next one.

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 va 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 = va l u e ;
t h i s . nex t = next ;

}
}

10 52

Singly linked list

The class SinglyLinkedList has an instance variable that designates the first element
of the list, which we will call head.
The nested class is sometimes called Elem or Entry.

11 52

Implementations

addFirst(E elem)

addFirst(E elem)

Inserting an element at the start of the list requires:
1. the creation of a new node, as well as
2. adding the element to the list.

pub l i c vo id a d dF i r s t (E elem ) {

Node newNode ;
newNode = new Node(elem , nu l l ) ;

i f ( head == nu l l ) {
head = newNode ;

} e l s e {
newNode . nex t = head ;
head = newNode ;

}
}

12 52

addFirst(E elem)

head

newNode

head

A

newNode

head

A

newNode

head

A

newNode

head

DB C

newNode

head

DB C

A
newNode

head

DB C

A
newNode

head

DB CA

newNode

13 52

Discussion

Is this distinction between the case of the empty list and the case of the list having
elements really necessary?
What do you think of this implementation?
pub l i c vo id a d dF i r s t (E elem ) {

head = new Node(elem , head ) ;
}

14 52

Discussion (continued)

Does that work for the special case and the general case?
Yes, it does.
Why?

Because Java first evaluates the right side of the expression.

15 52

addFirst(E elem)

Evaluation on the right side.
head = new Node(elem , head ) ;

head

DB C

A

16 52

addFirst(E elem)

The result (a reference to the newly created element) is assigned to the variable head.
head = new Node ( elem , head ) ;

head

DB C

A

17 52

addFirst(E elem)

Similarly, the result of the evaluation of the right side, here head is null, is assigned to the
instance variable next of the node.
head = new Node(elem , head ) ;

head

A

18 52

addFirst(E elem)

The result (a reference to the newly created element) is assigned to the variable head.
head = new Node( elem , head ) ;

head

A

19 52

Implementations

add(E elem)

Discussion add(E elem)

head

DB CA

The method add(E Elem) adds the element at the end of the list.
Without adding a reference to the last node, how is the element added to the end of the
list?

The solution has to be general!

20 52

add(E elem)

head

DB CA

21 52

add(E elem)

What will be the termination condition of the loop?

pub l i c vo id add (E elem ) {

Node newNode , p ;

newNode = new Node(elem , nu l l ) ;

p = head ;
whi le ( ) {

p = p . nex t ;
}

p . nex t = newNode ;
}

22 52

add(E elem)

What do you think?

pub l i c vo id add (E elem ) {

Node newNode , p ;

newNode = new Node(elem , nu l l ) ;

p = head ;
whi le ( p != nu l l ) {

p = p . nex t ;
}

p . nex t = newNode ;
}

23 52

add(E elem)

head

DB CA

p

head

DB CA

p

head

DB CA

p

head

DB CA

p

head

DB CA

p

head

DB CA

p

24 52

add(E elem)

After executing the loop, the value of p is null, an exception of type
NullPointerException will be thrown when executing p.next = newNode.

pub l i c vo id add (E elem ) {

Node newNode , p ;

newNode = new Node(elem , nu l l ) ;
p = head ;

whi le ( p . nex t != nu l l ) {
p = p . nex t ;

}

p . nex t = newNode ;
}

25 52

add(E elem)

New proposal!
What do you think of that?

pub l i c vo id add (E elem ) {

Node newNode , p ;

newNode = new Node(elem , nu l l ) ;
p = head ;

whi le ( p != nu l l ) {
p = p . nex t ;

}

p = newNode ;
}

26 52

add(E elem)

head

DB CA

p

E

27 52

add(E elem)

What will be the termination condition of the loop?

pub l i c vo id add (E elem ) {

Node newNode , p ;

newNode = new Node(elem , nu l l ) ;

p = head ;
whi le ( ) {

p = p . nex t ;
}

p . nex t = newNode ;
}

28 52

add(E elem)

pub l i c vo id add (E elem ) {

Node newNode , p ;

newNode = new Node(elem , nu l l ) ;

p = head ;
whi le ( p . nex t != nu l l ) {

p = p . nex t ;
}

p . nex t = newNode ;
}

29 52

add(E elem)

head

DB CA

p

head

DB CA

p

head

DB CA

p

head

DB CA

p

head

DB CA E

p

30 52

add(E elem)

What happens if the list is empty?
p.next != null causes a NullPointerException!

What variable should be pointing at the new element?

pub l i c vo id add (E elem ) {
Node newNode , p ;
newNode = new Node(elem , nu l l ) ;
p = head ;
whi le ( p . nex t != nu l l ) {

p = p . nex t ;
}
p . nex t = newNode ;

}

31 52

add(E elem)

pub l i c vo id add (E elem ) {
Node newNode ;
newNode = new Node(elem , nu l l ) ;

i f ( head == nu l l ) {
head = newNode ;

} e l s e {
Node p ;
p = head ;
whi le ( p . nex t != nu l l ) {

p = p . nex t ;
}
p . nex t = newNode ;

}
}

32 52

Pitfall!

pub l i c vo id add (E elem ) {
Node newNode ;
newNode = new Node(elem , nu l l ) ;

i f ( head == nu l l ) {
head = newNode ;

} e l s e {
whi le ( head . nex t != nu l l )

head = head . nex t ;
head . nex t = newNode ;

}
}

33 52

add(E elem)

head

DB CA

34 52

Implementations

Exercises

Exercises

Implement these methods:
E removeFirst()
E removeLast()

What will be the stop-criterion for the loop?

35 52

Implementations

remove(E elem)

remove(E elem)

Accessing elements through content!
Return true is elem has been removed and false otherwise.

36 52

remove(E elem)

Formulate your strategy!
1. Traverse the list
2. Stop criterium?
3. Removal

37 52

remove(E elem)

head

DB CA

38 52

remove(E elem)

What do you think?

pub l i c boolean remove (E elem ) {
Node p , r ;
p = head ;
whi le ( p != nu l l && ! p . v a l u e . e qu a l s ( elem ) ) {

p = p . nex t ;
}
r = p ;
// . . .

re tu rn t rue ;
}

39 52

pub l i c boolean remove (E elem ) {

Node p , r ;
p = head ;

whi le ( p . nex t != nu l l && ! p . nex t . v a l u e . e qu a l s ( elem ) ) {
p = p . nex t ;

}

r = p . nex t ;
p . nex t = r . nex t ;

re tu rn t rue ;
}

What happens if the list is empty
What happens if the element is missing from the list?

pub l i c boolean remove (E elem ) {
boolean r e s u l t = t rue ;
i f ( head == nu l l ) {

r e s u l t = f a l s e ;
} e l s e i f ( head . v a l u e . e qu a l s ( elem ) ) {

head = head . nex t ;
} e l s e {

Node p ;
p = head ;
whi le ( p . nex t != nu l l && ! p . nex t . v a l u e . e qu a l s ( elem ) ) {

p = p . nex t ;
}
i f ( p . nex t == nu l l ) {

r e s u l t = f a l s e ;
} e l s e {

p . nex t = p . nex t . nex t ;
}

}
re tu rn r e s u l t ;

}

Implementations

E get(int pos)

E get(int pos)

Returns the value saved at the position pos in the list.
Accessing by position!

The first element in the list is at position 0.
Elaborate your strategy.

42 52

E get(int pos)

head

DB CA

43 52

E get(int pos)

pub l i c E get ( i n t pos ) {

Node p ;
p = head ;

f o r ( i n t i =0; i r ;
Node p ;
p = head ;
f o r ( i n t i =0; i <(pos −1); i++) { p = p . nex t ; } r = p . nex t ; p . nex t = r . nex t ; saved = r . v a l u e ; re tu rn saved ; } What happens if pos == 0? 47 52 E remove(int pos) pub l i c E remove ( i n t pos ) { E saved ; Node r ;
i f ( pos == 0) {

r = head ;
head = head . nex t ;

} e l s e {
Node p ;
p = head ;
f o r ( i n t i =0; i <(pos −1); i++) { p = p . nex t ; } r = p . nex t ; p . nex t = r . nex t ; } saved = r . v a l u e ; re tu rn saved ; } 48 52 Prologue Summary A list (List) is an abstract data type (ADT) to store objects, such that each element has a predecessor and a successor (thus linear), and having no restrictions on data access; one can inspect, insert or delete anywhere. in the list. To traverse a list, we use a local variable of type Node that we initialize with the value of head. 49 52 Next module List : implementation techniques 50 52 References I E. B. Koffman and Wolfgang P. A. T. Data Structures: Abstraction and Design Using Java. John Wiley & Sons, 3e edition, 2016. 51 52 Marcel Turcotte Marcel. School of Electrical Engineering and Computer Science (EECS) University of Ottawa 52 / 52 Marcel. Preamble Overview Learning objectives Plan Definitions Implementations ArrayList Singly linked list addFirst(E elem) add(E elem) Exercises remove(E elem) E get(int pos) E remove(int pos) Prologue