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
p r i v a t e Node (T va lue , Node
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 = new Node
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
}
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
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
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
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 = new Node
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 = new Node
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 = new Node
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 = new Node
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 = new Node
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 = new Node
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 = new Node
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 = new Node
i f ( head == nu l l ) {
head = newNode ;
} e l s e {
Node
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 = new Node
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 = 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 = 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 = 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 = head ;
f o r ( i n t i =0; i
Node
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
i f ( pos == 0) {
r = head ;
head = head . nex t ;
} e l s e {
Node
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