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
p r i v a t e Node (T va lue , Node
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
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
p r i v a t e Node (T va lue , Node
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
p r i v a t e Node
// . . .
}
14 51
addLast
pub l i c vo id addLast (E elem ) {
Node
newNode = new Node
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
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
p r i v a t e Node
p r i v a t e Node (T va lue , Node
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
p r i v a t e Node
// . . .
}
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
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
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
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
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
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
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
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
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
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
p r i v a t e Node
p r i v a t e Node (T va lue , Node
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
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