CMPT 225
Lecture 4 – Data collection List ADT
1
Learning Outcomes
At the end of this lecture, a student will be able to:
manage memory in C++, allocate and free arrays
and individual elements in heap
differentiate between memory declared globally, on
the stack, and on the heap
define one of the concrete data types, namely linked
list, and demonstrate, simulate, and trace its
operations
manipulate pointers
2 write C++ code
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Last Lecture
Example: Temperature ADT class versus non-ADT class and
class test driver
✓ Terminology
✓ Data Collection (ADT) versus Data Structure (CDT)
✓ Categories of data organizations
As part of solving the
✓ Introduced our first data collection: List FriendsBook problem
✓ Step 2 – Design List as an ADT class
What is hidden 1. Design its public section (public interface) -> its operations
behind the wall 2. Design its private section -> its data and the implementation of its
operations At least, a CDT + a
Step 3 – Implementation of List ADT class variable to keep track
3 of number of elements
1. Array-based implementation of List ADT in List: elementCount
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
From last lecture: List Public Interface
1. Insert element into List
Prepend (insert at the front – position 1)
Position-oriented List Append (insert at the back – position elementCount + 1)
Insert at a particular position (between the above two positions)
Value-oriented List Insert in sort order using the element’s search key
2. Remove element from List
Position-oriented List Remove element from either position 1, position elementCount, or
any position in between
Value-oriented List Remove element that matches the search key (require Searching)
3. Get/retrieve a particular element from List …
Position-oriented List … located at position X where range of X is [1 .. elementCount ]
Return a pointer or reference to target element
Value-oriented List … that matches the given search key (require Searching)
4 Return a pointer or reference to target element or its index
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Today’s menu
Continue with Step 3 – Implementation of List ADT class
1. Array-based implementation of List ADT
Differentiate between stack-allocated (automatically
allocated) and heap-allocated (dynamically allocated) arrays
Introduce 2nd data structure (CDT): linked list
Build linked list: pointers and node objects
Linked list operations
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Step 3 – Array-based implementation of List ADT
Considering a value-based List: Class invariant: List kept in sort order
and no duplications allowed
Insert element into List -> O(n)
Find where the element is to be inserted in the array (make sure element
not already there): O(n) or O(log n)
Shift elements right from this location onwards to make room: O(n)
Insert element: O(1) and elementCount++: O(1)
Remove element from List –> O(n)
Find element’s location using its search key: O(n) or O(log n)
Shift elements left to overwrite it: O(n) and elementCount--: O(1)
No need to “erase” an element from an array cell, simply overwrite it
Traverse (iterate through) the List -> O(n)
Get/retrieve a particular element from List using its search key -> O(n) or
O(log n)
“Expand” (resize) the List (i.e., expand the underlying array): O(?)
6 (see Expandable Array under Lecture 3 for more information)
Note: Easier to manage when there are no gaps in the array!
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Step 3 – Array-based implementation of List ADT
Public interface (Specifications)
List ADT class
Insert
Class data
members The stack segment
(private):
of memory may not
be the best place to
FriendsBook Search
Etc...
(client code) hold (potentially) large
array of Profile objects
amount of data
(Profile objects) … Hum!
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Activity: Stack versus heap memory allocation
ListTestDriver.cpp:
int main() { List.h #1 List.h #2
// Object instantiation /* Header Comment Block */ /* Header Comment Block */
List profiles = List(); ... ...
class List { class List {
private: private:
Memory layout constexpr static int SIZE = 5; constexpr static int SIZE = 5;
Profile elements[SIZE]; Profile * elements;
stack
unsigned int elementCount; unsigned int elementCount;
public: public:
... // Destructor
heap delete [] elements;
insert(...) ~List();
}; ... in List.cpp
insert(...)
}; if (elementCount == 0)
elements = new Profile[SIZE];
static if (elements == nullptr) // error!
else // insert new element
8 code
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Step 3 – Array-based implementation of List ADT
When Always implement methods optimizing their time efficient
implementing,
we need to
consider … Differentiate between stack-allocated and heap-allocated arrays
When to use stack-allocated memory?
When to use heap-allocated memory?
When using heap-allocated array, we need to consider:
Copy constructor
Overload assignment operator
new operator
Destructor
9 delete [ ] operator
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Introducing 2nd concrete data structure:
linked list
Made of pointers and node Node Node Node
Head
Characteristics:
Adv:
Flexible/unbounded size: it grows or shrinks as needed
Operations on linked list do not require the shifting of elements
Disadv: Sequential access
Elements must be accessed in some specific order dictated
by the links
10
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
What can we do with a linked list?
1. Insert element into List
Prepend (insert at the front – position 1)
Position-oriented List Append (insert at the back – position elementCount + 1)
Insert at a particular position (between the above two positions)
Value-oriented List Insert in sort order using the element’s search key
2. Remove element from List
Position-oriented List Remove element from either position 1, position elementCount, or
any position in between
Value-oriented List Remove element that matches the search key (require Searching)
3. Get/retrieve a particular element from List …
Position-oriented List … located at position X where range of X is [1 .. elementCount ]
Return a pointer or reference to target element
Value-oriented List … that matches the given search key (require Searching)
11 List Public
Return a pointer or reference to target element or its position Interface
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
REVIEW Insert an element into a linked list
insert @ front (prepend)
head
3 7 5 8
4
elementCount
6 pseudocode
... prepend(int newElement) // prepend into a List newNode
1. Node *newNode = new Node(newElement);
2. if (newNode != nullptr)
Order is 3. newNode->next = head; // Whether Head NULL or not
important 4. head = newNode;
12 5. elementCount++;
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
REVIEW Generalisation Principle
Ensuring that our code works in all situations – all the
states a linked list can have – all test cases:
1. When linked list is empty
2. When it has 1 element,
3. When it has many elements,
4. etc.
Here, will our code work when the linked list is empty?
head newNode
0
13 elementCount
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
REVIEW Traverse a linked list
head
3 7 5 8
4
elementCount
pseudocode
Local // Anchor head of linked list
variable: current 1. if ( head != nullptr )
2. Node* current = head;
3. while (current->next != nullptr)
4. current = current->next;
14
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
REVIEW Traverse - Do we need the anchor?
head
3 7 5 8
4
elementCount
pseudocode
// Traverse linked list
1. if ( head != nullptr )
2. while (head->next != nullptr)
3. head = head->next;
15
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
REVIEW Insert an element into a linked list
insert @ end (append)
head
3 7 5
3 pseudocode
elementCount ... append(int newElement)
1. Node *newNode = new Node(newElement);
2. if (newNode != nullptr)
3. if (head == nullptr)
newNode
4. head = newNode;
Local else
variable: current // Move to the end of the list
5. Node* current = head; // Anchor
6. while (current->next != nullptr)
7. current = current->next;
8. current->next = newNode;
16
9. elementCount++;
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
A word about inserting an element into a linked list
@ specific location
When linked list is used as a data structure (CDT) for a position-
oriented data collection ADT class like a List, we can indicate at
which position we would like to insert an element
position is a parameter of the insert method
Class invariant for this OR
List class: the List is When linked list is used as a data structure (CDT) for a value-
always sorted by … oriented data collection ADT class like a List (which is kept
e.g. ascending or descending
alphabetical/numerical sort
sorted), in order to keep it sorted, we insert the element in sort Algorithm 1
order of search key … order into the List using a search key (i.e., an element’s attribute)
depending on the problem we
are solving.
Alternatively, we could first prepend the element into the List (this
is time efficient, i.e., O(1)), then we sort the List (sorting algorithms
can be O(n2) or O(n log(n)). As you can see, this 2nd way of Algorithm 2
“keeping the List sorted when we insert” is not time efficient!
data
List kept in descending 36 89 53 27 12
sort order of data: head
17
next Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
REVIEW Remove an element from a linked list
remove @ front List object
head
3 7 5 8
4
elementCount
pseudocode
... removeAtFront( )
nodeToRemove 1. if (head != nullptr)
2. Node * nodeToRemove = head;
3. head = head->next;
// Return node to the system
4. nodeToRemove->next = nullptr;
5. delete nodeToRemove;
18 6. nodeToRemove = nullptr;
7. elementCount--;
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Remove an element from a linked list
remove @ end List object
head
3 7 5 8
4
elementCount
pseudocode
current ... removeAtEnd( )
1. if (head != nullptr)
// Move to the end of the list
2. Node * current = head; // Anchor
3. while (current->next != nullptr)
4. current = current->next;
19 // Then what???
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Learning Check
✓ Continued with Step 3 – Implementation of List ADT class
✓ Array-based implementation of List ADT
✓ Differentiated between stack-allocated (automatically
allocated) and heap-allocated (dynamically allocated) arrays
✓ Introduced 2nd data structure (CDT): linked list
✓ Built linked list: pointers and node objects
✓ Linked list operations
20
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
Next Lecture
Finish looking at Linked list operations
And various configurations of linked lists
Know when to use them (know their forte)
Step 3 – Implementation - Linked list-based implementation
of List ADT class
Introduce a Node class
Compare the two implementations of our List ADT class:
Array-based implementation
21 Linked list-based implementation
Copyright © Anne Lavergne, School of Computing Science, Simon Fraser University
