Programming Languages Chapter 17 Programming From Problem Analysis Program Design Eighth Edition Linked Lists Guide

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

Explain that using an iterator to process a list or other type of generic container is

a standard technique in object-oriented programming languages.

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

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