PowerPoint Presentation
Link Based Implementations
Chapter 4
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Contents
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Preliminaries
A Link-Based Implementation of the ADT Bag
Using Recursion in Link-Based Implementations
Testing Multiple ADT Implementations
Comparing Array-Based and Link-Based Implementations
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Preliminaries
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Components that can be linked
FIGURE 4-1 A node
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Preliminaries
FIGURE 4-2 Several nodes linked together
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Preliminaries
FIGURE 4-3 A head pointer to the first
of several linked nodes
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Preliminaries
FIGURE 4-4 A lost node
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Class Node
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
View Node header file, Listing 4-1
Note implementation of class Node,
Listing 4-2
.htm code listing files must be in the same folder as the .ppt files for these links to work
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Link-Based Implementation of ADT Bag
View header file, Listing 4-3
Note methods to be implemented
FIGURE 4-5 A link-based implementation
of the ADT bag
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Link-Based Implementation of ADT Bag
FIGURE 4-6 Inserting at the beginning of a linked chain
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
FIGURE 4-7 The effect of the assignment
curPtr = curPtr->getNext()
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Link-Based Implementation of ADT Bag
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
FIGURE 4-8 (a) A linked chain and its shallow copy;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Link-Based Implementation of ADT Bag
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Testing Multiple ADT Implementations
Note program which tests core methods,
Listing 4-4
FIGURE 4-8 (b) a linked chain and its deep copy
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Testing Multiple ADT Implementations
Sample output 1 of test program
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Testing Multiple ADT Implementations
Sample output 2 of test program
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Comparing Array-Based
and Link-Based Implementations
Arrays easy to use, but have fixed size
Increasing size of dynamically allocated array can waste storage, time
Array based implementation good for small bag
Linked chains do not have fixed size
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Comparing Array-Based
and Link-Based Implementations
Item after an array item is implied
Item in a chain of linked nodes points explicitly to next item
Array based implementation requires less memory
Array items accessed directly, equal access time
Must traverse linked chain for ith item – access time varies
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
End
Chapter 4
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013