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: implementation

by

Marcel Turcotte

Version March 19, 2020

Preamble

Preamble

Overview

Overview

List: implementation

We focus on three implementations of the interface List using linked elements: the
singly-linked list, the doubly-linked list, and the doubly-linked circular 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 51

Preamble

Learning objectives

Learning objectives

Explain the role of reference variables in the implementation of a linked list.
Modify the implementation of a singly or doubly linked list in order to add a new
method to it.
Justify the purpose of the dummy node in the implementation of a doubly linked
circular list.
Discuss the advantages and disadvantages, particularly in terms of execution time and
memory usage, for the three implementations of a list seen in this course, the singly
linked list, the doubly linked list, and the doubly linked circular list starting with a
dummy node.

Readings:
Pages 84-89, 103 of E. Koffman and P. Wolfgang.

2 51

Preamble

Plan

Plan

1 Preamble

2 Definitions

3 Implementations

4 Prologue

3 51

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 51

Implementations

ArrayList
LinkedList

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

5 51

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 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 ;

}
}

6 51

LinkedList

head

DB CA

7 51

Definition

We compare the efficiency of array-based (ArrayList) and linked-element-based
(LinkedList) implementations.

Both can hold an unlimited number of objects, so ArrayList uses a dynamic array.
We will say that the execution time is variable (slow), if the number of operations
varies according to the number of elements currently saved in the data structure, and
constant (fast) otherwise.

8 51

LinkedList

head

DB CA

9 51

Implementations

Comparer ArrayList et LinkedList

Can you predict which of the two implementations will be faster?

ArrayList LinkedList
void addFirst(E elem)
void addLast(E elem)

void add(E elem, int pos)
E get(int pos)

void removeFirst()
void removeLast()

10 51

Discussion

For some operations, when one implementation is fast, the other is slow;
Looking at the table above, when should we use an implementation based on arrays?

For direct access (random).

When should a linked list be used?

If all the accesses are at the start of the list;

Which implementation consumes more memory?

11 51

Implementations

Reference to the rear node

Accelerate addLast for a singly linked list

There is a simple implementation technique for accelerating the addition of an element
at the end of a linked structure.
What makes the current implementation costly?
Yes, you have to traverse the list from one end to the other in order to add the item
at the very end.
We could of course add the elements in reverse order, but that would only move the
problem, the method addFirst() would be slow.
For the method size(), we saw that the use of an additional instance variable, count,
could save us from going through the list unnecessarily.
What would we need in this case to avoid traversing the list?
Yes, a new variable pointing to the last item on the list.

12 51

Memory diagram

Representing the empty list:

head

tail

General case:

head

DB CA

tail

13 51

LinkedList

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 ;
p r i v a t e Node t a i l ;

// . . .
}

14 51

addLast

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

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

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

} e l s e {
t a i l . nex t = newNode ;
t a i l = newNode ;

}
}

15 51

Modify all the other methods accordingly

pub l i c E r e m o v e F i r s t ( ) {

E saved ;
saved = head . v a l u e ;

head = head . nex t ;

i f ( head == nu l l ) {
t a i l = nu l l ;

}

re tu rn saved ;
}

16 51

Compare the ArrayList and LinkedList

Adding a reference to the last node.

ArrayList LinkedList
void addFirst(E elem) variable constant
void addLast(E elem) variable constant

void add(E elem, int pos) variable variable
E get(int pos) constant variable

void removeFirst() variable constant
void removeLast() constant variable

Is removeLast faster now, as well?

17 51

Implementations

Doubly linked nodes

Accelerate removeLast

head

DB CA

tail

previous

What do you think?

18 51

Accelerate removeLast

head

DB CA

tail

previous

Moving the rear reference is now easy and fast!
Except moving the reference previous is difficult and expensive.

19 51

LinkedList

head

DB CA

20 51

LinkedList

head

B CA

tail

D

21 51

Doubly 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 prev ;
p r i v a t e Node next ;
p r i v a t e Node (T va lue , Node prev , Node next ) {

t h i s . v a l u e = v a l u e ;
t h i s . p r ev = prev ;
t h i s . nex t = next ;

}
}

p r i v a t e Node head ;
p r i v a t e Node t a i l ;

// . . .
}

22 51

removeLast: general case

head

B CA

tail

D

23 51

removeLast: special case

head

tail

A

24 51

pub l i c E removeLast ( ) {

E saved ;
saved = t a i l . v a l u e ;

i f ( head . nex t == nu l l ) {
head = nu l l ;
t a i l = nu l l ;

} e l s e {
t a i l = t a i l . p r ev ;
t a i l . nex t = nu l l ;

}

re tu rn saved ;
}

Compare ArrayList and LinkedList

Doubly linked nodes.

ArrayList LinkedList
void addFirst(E elem) variable constant
void addLast(E elem) variable constant

void add(E elem, int pos) variable variable
E get(int pos) constant variable

void removeFirst() variable constant
void removeLast() constant constant

26 51

Discussion

What will be the impact of this change?

27 51

Preconditions : add(int pos, E elem)

What are the prerequisites to the method add?

i f ( elem == 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 ( ” n u l l ” ) ;

}
i f ( pos < 0 | | pos > s i z e ) {

throw new IndexOutOfBoundsExcept ion ( pos ) ;
}

28 51

Special cases : add(int pos, E elem)

What are the special cases?

head

B C

tail

29 51

Special case : add(int pos, E elem)

Special case: head = new Node(elem, null, head)

head

B CA

tail

What’s missing?

30 51

Special case : add(int pos, E elem)

Special case: head.next.previous = head

head

B CA

tail

31 51

Special case : add(int pos, E elem)

Special case:
i f ( pos == 0) {

head = new Node(elem , nu l l , head ) ;
head . nex t . p r e v i o u s = head ;

}

Have we thought about every possible case?
What if the list is empty?

32 51

Special case : add(int pos, E elem)

Special case:
i f ( pos == 0) {

head = new Node(elem , nu l l , head ) ;
i f ( t a i l == nu l l ) {

t a i l = head ;
} e l s e {

head . nex t . p r e v i o u s = head ;
}

}

33 51

General case: add(int pos, E elem)

General case: addint at position 2.

head

BA

tail

D

34 51

General case : add( int pos, E elem)

General case: traverse the list until pos-1

head

BA

tail

D

p

35 51

General case : add(int pos, E elem)

General case: q = p.next

head

BA

tail

D

p q

36 51

General case : add(int pos, E elem)

General case: p.next = new Node(elem, p, q)

head

BA

tail

D

p q

B

37 51

General case add(int pos, E elem)

General case: q.previous = p.next

head

BA

tail

D

p q

B

38 51

General case add(int pos, E elem)

General case:
Node be fo r e , a f t e r ;
b e f o r e = head ;

f o r ( i n t i = 0 ; i < ( pos −1); i ++) { b e f o r e = b e f o r e . nex t ; } a f t e r = b e f o r e . nex t ; b e f o r e . nex t = new Node(elem , be fo r e , a f t e r ) ;
a f t e r . p r e v i o u s = b e f o r e . nex t ;

Have we thought of all the cases?
What if before refers to the last element?

39 51

add(int pos, E elem)

Node be fo r e , a f t e r ;

b e f o r e = head ;

f o r ( i n t i = 0 ; i < ( pos −1); i ++) { b e f o r e = b e f o r e . nex t ; } a f t e r = b e f o r e . nex t ; b e f o r e . nex t = new Node(elem , be fo r e , a f t e r ) ;

i f ( b e f o r e == t a i l ) {
t a i l = b e f o r e . nex t ;

} e l s e {
a f t e r . p r e v i o u s = b e f o r e . nex t ;

}

40 51

Implementations

Dummy node

Dummy node

The following implementation technique allows you to eliminate multiple special
cases.

The technique uses a dummy node containing no element (data).
Plus, the list is circular!

42 51

Dummy node

Empty list:

head

size
0

General case:

head

B

size

FD

3

43 51

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 prev ;
p r i v a t e Node next ;
p r i v a t e Node (T va lue , Node prev , Node next ) {

t h i s . v a l u e = v a l u e ;
t h i s . p r ev = prev ;
t h i s . nex t = next ;

}
}
p r i v a t e Node head ;

Give the implementation of the constructor.

Discussion

What complicates the implementation of linked-list methods without a dummy
node?

The methods usually have a special case for modifying in first position.
In general, one must change the variable next of the preceding node, unless one is
processing the first node, in which case one must change the variable head.
Changes at the end of the list are also a problem since the value of tail must be changed.

For the implementation having a dummy node, the treatments are uniform, we always
change the variable next of the preceding node.

45 51

head

size
0

head

B

size
1

head

B

size

FD

3

head

size
0

head

B

size
1

head

B

size

D

2

head

B

size

FD

3

Prologue

Summary

A reference to the last node makes it easy to add an element to the end of the list.
The double linked nodes make it easy to remove the last element, but also to
navigate the list in reverse order.
Circular lists with dummy nodes have no special cases!

48 51

Next module

List : iterator

49 51

References I

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

50 51

Marcel Turcotte
Marcel.

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

51 / 51

Marcel.

Preamble
Overview
Learning objectives
Plan

Definitions
Implementations
Reference to the rear node
Doubly linked nodes
Dummy node

Prologue