Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-1
Chapter 17
Linked Lists
A Guide to this Instructor’s Manual:
We have designed this Instructor’s Manual to supplement and enhance your teaching
experience through classroom activities and a cohesive chapter summary.
This document is organized chronologically, using the same headings that you see in the
textbook. Under the headings, you will find lecture notes that summarize the section, Teacher
Tips, Classroom Activities, and Lab Activities. Pay special attention to teaching tips and
activities geared towards quizzing your students and enhancing their critical thinking skills.
In addition to this Instructor’s Manual, our Instructor’s Resources also contain PowerPoint
Presentations, Test Banks, and other supplements to aid in your teaching experience.
At a Glance
Instructor’s Manual Table of Contents
• Overview
• Objectives
• Teaching Tips
• Quick Quizzes
• Class Discussion Topics
• Additional Projects
• Additional Resources
• Key Terms
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-2
Lecture Notes
Overview
Chapter 17 introduces students to the linked list data structure. Until this point, students
have used sequential lists, or arrays, to manipulate a group of items of the same type. In
this chapter, they will explore how to use linked lists to overcome some of the
performance and efficiency issues of arrays. Students will learn how to build and
manipulate a linked list, as well as examine how to perform various operations on them.
They will also be introduced to various types of linked lists, including the doubly linked
list and the circular linked list.
Objectives
In this chapter, the student will:
• Learn about linked lists
• Become familiar with the basic properties of linked lists
• Explore the insertion and deletion operations on linked lists
• Discover how to build and manipulate a linked list
• Learn how to implement linked lists as ADTs
• Learn how to create linked list iterators
• Learn how to implement the basic operations on a linked list
• Learn how to create unordered linked lists
• Learn how to create ordered linked lists
• Learn how to construct a doubly linked list
• Become familiar with circular linked lists
Teaching Tips
Linked Lists
Teaching
Tip
Review the performance of various array operations before discussing linked
lists. Explain that insertions and deletions are inefficient on arrays, and that
searching can be inefficient as well if the array is not already sorted.
1. Define a linked list as a collection of nodes. Explain that each node contains the data as
well as the address of the next node in the list.
2. Use Figures 17-1 through 17-3 to illustrate a linked list graphically.
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-3
Teaching
Tip
Discuss the differences between a dynamic array and a linked list. Note that
although a dynamic array’s size does not have to be allocated until run time, it
remains fixed after it is allocated. In addition, emphasize that the memory for an
array is contiguous. With linked lists, the data is only connected by the link
provided in each node.
3. Define the terms head and link as they relate to linked lists.
4. Examine the definition of a node structure.
Teaching
Tip
The node structure may be intimidating to students on first reading. Emphasize
that the pointer type on the node structure is of the node type because it is
pointing to another node. Verify that students understand the difference between
a “link” pointer and a pointer to an array’s base address.
Linked Lists: Some Properties
1. Describe in detail how arrow notation is used in accessing items in a linked list. Use
Figures 17-4 through 17-6 to clarify.
Teaching
Tip
Make sure students understand the use of multiple arrows in a statement to move
through a list, and remind them that indexing is not used to access items in a
linked list.
2. Explain how to traverse a list with node pointers. Emphasize that the head pointer
cannot be used to traverse a list because we would lose the nodes in the list. Instead,
another pointer is set to the same address as the head pointer and used to traverse the
list.
Teaching
Tip
Explain that the identifier current is commonly used by programmers to refer
to a node pointer that is used to traverse the list, and the identifier link is
commonly used to refer to the node pointer member of a node. The identifier
next is also often used to denote the node pointer member.
3. Describe how to insert a new node into a list using the code in this section. Use Figures
17-7 through 17-9 and Tables 17-1 and 17-2 to illustrate how the node links must be
4. Using Figures 17-10 and 17-11 along with Table 17-3, describe how to delete a node
from a linked list. Remind students to deallocate memory during this process.
Teaching
Tip
Insertion into and deletion from linked lists is tricky, particularly with the pointer
rearrangements. Assure students that after they become familiar with the code for
each process, it will become instinctive.
Building a Linked List
1. Describe how to build a linked list forward. First, discuss node declarations and
initializations with Figures 17-12 through 17-17 as a graphical illustration. Then walk
through the function in this section that builds a complete list.
Teaching
Tip
Verify that students understand why so many node pointers are needed to build a
list by explaining the purpose of each pointer.
2. Describe how to build a list backward. Note the differences in the code from the
function for building a list forward. Use Figure 17-18 to illustrate the result.
Quick Quiz 1
1. What are the two components of a node in a linked list?
2. The address of the first node in a list is stored in a separate location, called the
____________________.
3. True or False: The data type of a node pointer is the node type itself.
4. The link of the last node in a linked list has the value ____________________.
Linked List as an ADT
1. Discuss why a linked list is typically implemented as an ADT.
2. List the typical operations for a linked list ADT.
4. Briefly describe the two classes that will be derived from the linked list ADT and note
the operations that will be implemented differently.
Structure of Linked List Nodes
1. Examine the node structure of the linked list class. Note the use of the Type parameter.
Teaching
Tip
Explain why a struct is used for this implementation of a node rather than a
class. Do your students think implementing a list template with a node structure
is easier than with a node class? Why or why not?
Member Variables of the class linkedListType
1. Discuss the three member variables of the class linkedListType — first,
Linked List Iterators
1. Define the term iterator and explain its use in linked lists. Describe the typical
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-6
Teaching
Tip
Ask students why they think the print function is not implemented as an
overloaded stream friend function. Note the parameter types in the stream
functions.
Length of a List
Retrieve the Data of the First Node
1. Examine the implementation of the front function in the linkedListType
class.
Retrieve the Data of the Last Node
1. Examine the implementation of the back function in the linkedListType class.
Teaching
Tip
Note that the first and last pointers provide constant time access to the first
and last nodes.
Begin and End
1. Discuss the implementations of the begin and end functions in the
Copy the List
1. Examine the implementation of the copyList function of the linkedListType
class.
Teaching
Tip
Ask students if this function creates a shallow or deep copy of the list, primarily
in order to give them the opportunity to take a closer look at code using node
pointers.
Destructor
1. Discuss the implementation of the destructor function in the linkedListType
class.
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-7
Teaching
Tip
Discuss why the destroyList function is implemented as a separate function
rather than simply placing its code in the destructor.
Copy Constructor
1. Discuss the implementation of the copy constructor function of the linkedListType
Overloading the Assignment Operator
1. Briefly examine the overloaded assignment operator of the linkedListType
class.
Quick Quiz 2
1. In general, what are the two types of linked lists?
2. The node of a linked list is implemented as a(n) ____________________ in this
chapter.
3. A(n) ____________________ is an object that produces each element of a container,
such as a linked list, one element at a time.
4. True or False: The linkedListType class presented in this chapter has two
member variables.
Unordered Linked Lists
1. Examine the class definition and UML diagram of the unorderedLinkedList
class. Review the UML diagram in Figure 17-21.
Search the List
1. Discuss the implementation of the search function in the unorderedLinkedList
class.
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-8
Teaching
Tip
Note that this search must be implemented sequentially.
Insert the First Node
1. Discuss the implementation of the insertFirst function in the
Insert the Last Node
1. Discuss the implementation of the insertLast and the deleteNode functions in
Delete a Node
1. Describe each of the cases for deleting a node, using Figures 17-22 through 17-28.
Teaching
Tip
The deleteNode function contains a complicated set of cases and pointer
assignments. Step through the code slowly and verify that students understand
the implementation.
Header File of the Unordered Linked List
1. Review the header file for the unorderedLinkedList class. Remind students
that both the function declarations and definitions are in the header file because the
class is a template.
Ordered Linked Lists
1. Examine the class definition and UML diagram of the orderedLinkedList
class shown in Figure 17-29.
Search the List
1. Discuss the search function in the orderedLinkedList class. Note that the
Insert a Node
1. Examine the insert function in the orderedLinkedList class in detail.
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-9
Teaching
Tip
Like the deleteNode function in the unorderedList class, this function
has several cases involving complex pointer assignments. Step through the code
carefully with Figures 17-30 through 17-36 to clarify how the function works.
Insert First and Insert Last
1. Discuss the insertFirst and insertLast functions in the orderedListType
class.
Teaching
Tip
Since the functions above do not apply to ordered lists, ask your students if they
can think of a way to design the class hierarchy to avoid implementing them.
Delete a Node
1. Examine the deleteNode function of the orderedLinkedList class in detail.
Teaching
Tip
Ask students to work in groups and compare the ordered and unordered list
implementations and discuss their findings.
Header File of the Ordered Linked List
1. Briefly review the header file of the orderedLinkedList class.
Print a Linked List in Reverse Order (Recursion Revisited)
1. Discuss the recursive algorithm to print a list in reverse order. Note that the base case is
hidden. Clarify the recursive process with Figures 17-37 and 17-38.
Teaching
Tip
Note that this function would not be necessary with a list that has pointers in both
directions.
printListReverse
1. Explain how to start the recursive print process by calling it from a caller print function.
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-10
Doubly Linked Lists
2. Note that the operations for a doubly linked list are the same as for a singly linked list.
3. Examine the node structure for a node in a doubly linked list.
4. Briefly display the class definition for an ordered doubly linked list.
Teaching
Tip
Discuss the implementation of the copy constructor, overloaded assignment
operator, and the destructor in preparation for the programming assignment at the
end of the chapter.
Default Constructor
1. Examine the implementation of the default constructor in the doublyLinkedList
class.
isEmptyList
1. Examine the implementation of the isEmptyList function in the
doublyLinkedList class.
Teaching
Tip
Discuss why this function does not have to verify that the back pointer is NULL
as well.
Destroy the List
Initialize the List
1. Briefly describe the implementation of the initializeList function in the
Length of the List
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-11
Print the List
Reverse Print the List
1. Examine the implementation of the reversePrint function in the
Search the List
First and Last Elements
1. Briefly note the implementation of the front and back functions in the
doublyLinkedList class.
Teaching
Tip
Ask the students to work in groups and compare the doubly linked list functions
to their singly linked list counterparts. The primary function of this exercise is to
acquaint your students with the code for linked lists. Ask them to consider if one
list is easier to conceptually understand than the other. Is the additional second
pointer a factor?
Circular Linked Lists
2. Note that the operations on a circular list are the same as the other types of lists
described in this chapter.
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-12
Quick Quiz 3
1. What operations does the unorderedLinkedList class in this chapter
implement?
2. The deleteNode function of an unordered list considers ____________________
general cases.
3. Define a circular linked list.
4. True or False: The list implementations in this chapter use a binary search algorithm for
the search function.
Class Discussion Topics
1. Discuss the factors that are involved in choosing a particular list implementation. For
example, is the overhead from the additional pointer in a doubly linked list a
consideration in whether to use a singly or doubly linked list? Is it always a better
2. Discuss the disadvantages of using a list data structure as opposed to other containers,
particularly in terms of its inefficiency in searches because of the lack of random
access.
3. Introduce your students to the list container in the C++ Standard Template Library.
You can find an overview of its functionality here:
Additional Projects
1. Rewrite the birthday program you created in Chapter 8 to use a sorted linked list
2. The orderedLinkedList presented in this chapter allows for duplicates. Modify
the search function of this class to return the number of items that match the search
C++ Programming: From Problem Analysis to Program Design, Eighth Edition 17-13
© 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part, except for use as permitted in a
license distributed with a certain product or service or otherwise on a password-protected website for classroom use.
Additional Resources
2. Linked List basics:
Key Terms
