Department of Computer Science
Data Structures
Lists and List ADT
August 30, 2023 CS 225
Brad Solomon
No class Monday September 2nd
mp_stickers will be releasing next week
Staff Office Hours will begin next week
Add your own music to music-suggestions!
Learning Objectives
Dene the functions and operations of the List ADT
Discuss list implementation strategies
Explore how to code and use a linked list
Practice fundamentals of C++ in the context of lists
Last time: Memory management
Local memory on the stack is managed by the computer
Heap memory allocated by new and freed by delete
Pass by value makes a copy of the object
Pass by pointer can be dereferenced to modify an object
Pass by reference modifies the object directly
Templates
A way to write generic code whose type is determined
during completion
Templates
A way to write generic code whose type is determined
during completion
1. Templates are a recipe for code using generic types
Templates
A way to write generic code whose type is determined
during completion
1. Templates are a recipe for code using generic types
2. The compiler uses templates to generate C++ code when needed
T sum(T a, T b){
...
}
T max(T a, T b) {
T result;
result = (a > b) ? a : b;
return result;
}
template1.cpp
1
2
3
4
5
6
7
Templates are very useful!
What is your favorite data structure?
A) Lists
B) Trees
C) Graphs D) Hash Tables
5
4
6
v
u
w
a c
b
z
d
!
"##$%
&
∅
'
(%)*
Join Code: 225
Your favorite data structure: Trees
5
15
9
25
4
6
7
13
11
16
12
14
Your favorite data structure: Trees
5
15
9
25
4
6
7
13
11
16
12
14
4
5
6
15
9
7
20
16
25
14
12
11
1 2 3 4
5 6 7 8
9 10 11 120 13 1514
-3
8
23
25
31
42
43
55
80
90
Lists
Your favorite data structure: Graphs
v
u
w
a c
b
z
d
Your favorite data structure: Graphs
v
u
w
a c
b
z
d
u
v
w
z
u
v
a
v
w
b
u
w
c
w
z
d
Lists
Your favorite data structure: Hash Tables
!
&
∅
'
+
∅
,
-
∅
.
∅
/
0
∅
1
∅
&!
∅
2*%3
"
∅
4*%5
"6
4%57
4
489
4:
∅
"$;
4:
"$;<%
":
"==)
"6
∅
>;$7
4:
>)?*)
"
@?%
4
∅
1
0
1
0
1
0
0
1
0
0
0
H = {h
1
, h
2
, . . . , h
k
}
So 100% of people are excited about lists!
A) Lists
B) Trees
C) Graphs D) Hash Tables
5
4
6
v
u
w
a c
b
z
d
!
"##$%
&
∅
'
(%)*
Note: Not every tree / graph / hash is actually a list :)
Abstract Data Types
A way of describing a data type as a combination of:
Data being stored by the data type
Operations that can be performed on the data type
The actual implementation details of the ADT aren’t relevant!
List ADT (What do we want our list to do?)
List ADT
A list is an ordered collection of items
Items can be either heterogeneous or homogenous
The list can be of a xed size or is resizable
A minimal set of operations (that can be used to create all others):
1. Insert
2. Delete
3. isEmpty
4. getData
5. Create an empty list
List Implementations
1.
2.
Linked List
C
S
2
2
5
Ø
class ListNode {
T & data;
ListNode * next;
ListNode(T & data) : data(data), next(NULL) { }
};
List.h
28
29
30
31
32
Why is data stored as a reference?
Why is next a pointer?
#pragma once
class List {
public:
/* ... */
void insertAtFront(const T& t);
private:
class ListNode {
T & data;
ListNode * next;
ListNode(T & data) :
data(data), next(NULL) { }
};
ListNode *head_;
/* ... */
};
List.h
1
2
3
4
5
…
28
29
30
31
32
33
34
35
36
37
38
39
40
…
…
…
79
79
How do I access list given head_?
C
S
head_
#pragma once
class List {
public:
/* ... */
void insertAtFront(const T& t);
private:
class ListNode {
T & data;
ListNode * next;
ListNode(T & data) :
data(data), next(NULL) { }
};
ListNode *head_;
/* ... */
};
List.h
1
2
3
4
5
…
28
29
30
31
32
33
34
35
36
37
38
39
40
…
…
…
79
79
What is missing in this code?
#pragma once
template <typename T>
class List {
public:
/* ... */
void insertAtFront(const T& t);
private:
class ListNode {
T & data;
ListNode * next;
ListNode(T & data) :
data(data), next(NULL) { }
};
ListNode *head_;
/* ... */
};
#include "List.hpp"
List.h
1
2
3
4
5
…
28
29
30
31
32
33
34
35
36
37
38
39
40
…
…
…
79
79
void List<T>::insertAtFront(const T& t)
{
}
List.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Linked List: insertAtFront(data)
C
S
2
2
5
Ø
head_
#pragma once
template <typename T>
class List {
public:
/* ... */
private:
class ListNode {
T & data;
ListNode * next;
ListNode(T & data) :
data(data), next(NULL) { }
};
ListNode *head_;
/* ... */
};
#include "List.hpp"
List.h
1
2
3
4
5
…
28
29
30
31
32
33
34
35
36
37
38
39
…
…
79
79
template <typename T>
void List<T>::insertAtFront(const T& t)
{
ListNode *tmp = new ListNode(data);
tmp->next = head_;
head_ = tmp;
}
List.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Linked List: insert(data, index)
C
S
2
2
5
Ø
head_
Linked List: _index(index)
C
S
2
2
5
Ø
head_
Linked List: _index(index)
What should the return type of _index() be?
(A) T & (B) ListNode
(C) ListNode *
(D) ListNode *&
[ template <class T>]
C
S
2
2
head_
Join Code: 225
template <typename T>
typename List<T>::ListNode *& List<T>::_index(unsigned index){
return _index(index, head_)
}
List.hpp
58
59
60
61
template <typename T>
typename List<T>::ListNode *& List<T>::_index(unsigned index, ListNode *& root){
}
63
64
65
66
67
68
69
70
71
72
73
template <typename T>
typename List<T>::ListNode *& List<T>::_index(unsigned index){
return _index(index, head_)
}
List.hpp
58
59
60
61
template <typename T>
typename List<T>::ListNode *& List<T>::_index(unsigned index, ListNode *& root){
if (index == 0 || node == nullptr){
return node;
}
return _index(index - 1, root -> next);
}
63
64
65
66
67
68
69
70
71
72
73
// Iterative Solution:
template <typename T>
typename List<T>::ListNode *& List<T>::_index(unsigned index) {
if (index == 0) { return head; }
else {
ListNode *curr = head;
for (unsigned i = 0; i < index - 1; i++) {
curr = curr->next;
}
return curr->next;
}
}
List.hpp
1
2
3
4
5
6
7
8
9
10
11
12
Which solution is better (iterative or recursive)?
Linked List: insert(data, index)
C
S
2
2
5
Ø
head_
1) Get reference to previous node’s next
ListNode *& curr = _index(index);
2) Create new ListNode
ListNode * tmp = new ListNode(data);
3) Update new ListNode’s next
tmp->next = curr;
4) Modify the previous node to point to new ListNode
curr = tmp;
template <typename T>
void List<T>::insert(const T & data,
unsigned index) {
ListNode *& curr = _index(index);
ListNode * tmp = new ListNode(data);
tmp->next = curr;
curr = tmp;
}
List.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename T>
void List<T>::insertAtFront(const T& t)
{
ListNode *tmp = new ListNode(t);
tmp->next = head_;
head_ = tmp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Next Time: List Random Access []
Given a list L, what operations can we do on L[]?
What return type should this function have?
