Chapter 17

Linked Data
Structures

Copyright © 2016 Pearson, Inc.

All rights reserved.
 Learning Objectives
• Nodes and Linked Lists
– Creating, searching
• Linked List Applications
– Stacks, queues, sets, hash tables
– Friend classes, alternatives
• Iterators
– Pointers as iterators
• Trees

Copyright © 2016 Pearson Inc. All rights reserved. 17-2

 Introduction
• Linked list
– Constructed using pointers
– Grows and shrinks during run-time
– Doubly Linked List : A variation with pointers in both
directions
• Trees also use pointers
• Pointers backbone of such structures
– Use dynamic variables
• Standard Template Library
– Has predefined versions of some structures
Copyright © 2016 Pearson Inc. All rights reserved. 17-3
 Approaches
• Three ways to handle such data structures:
1. C-style approach: global functions and
structs with everything public
2. Classes with private member variables and
accessor and mutator functions
3. Friend classes
• Linked lists will use method 1
• Stacks, queues, sets, and hash tables will use
method 2
• Trees will use method 3

Copyright © 2016 Pearson Inc. All rights reserved. 17-4

 Nodes and Linked Lists
• Linked list
– Simple example of "dynamic data structure"
– Composed of nodes
• Each "node" is variable of struct or class
type that’s dynamically created with new
– Nodes also contain pointers to other nodes
– Provide "links"

Copyright © 2016 Pearson Inc. All rights reserved. 17-5

 Display 17.1 Nodes and Pointers

Copyright © 2016 Pearson Inc. All rights reserved. 17-6

 Node Definition
• struct ListNode
{
string item;
int count;
ListNode *link;
};
typedef ListNode* ListNodePtr;
• Order here is important!
– Listnode defined 1st, since used in typedef
• Also notice "circularity"

Copyright © 2016 Pearson Inc. All rights reserved. 17-7

 Head Pointer
• Box labeled "head" not a node:
ListNodePtr head;
– A simple pointer to a node
– Set to point to 1st node in list
• Head used to "maintain" start of list
• Also used as argument to functions

Copyright © 2016 Pearson Inc. All rights reserved. 17-8

 Example Node Access
• (*head).count = 12;
– Sets count member of node pointed to by
head equal to 12
• Alternate operator, ->
– Called "arrow operator"
– Shorthand notation that combines * and .
– head->count = 12;
• Identical to above
• cin >> head->item
– Assigns entered string to item member

Copyright © 2016 Pearson Inc. All rights reserved. 17-9

 End Markers
• Use NULL or nullptr (in C++11) for node
pointer
– Considered "sentinel" for nodes
– Indicates no further "links" after this node
• Provides end marker similar to how we
use partially-filled arrays

Copyright © 2016 Pearson Inc. All rights reserved. 17-10

 Display 17.2 Accessing Node Data

Copyright © 2016 Pearson Inc. All rights reserved. 17-11

 Linked List
• Lists as illustrated called linked lists
• First node called head
– Pointed to by pointer named head
• Last node special also
– It’s member pointer variable is NULL (or nullptr in
C++11)
– Easy test for "end" of linked list

Copyright © 2016 Pearson Inc. All rights reserved. 17-12

 Linked List Class Definition
• class IntNode
{
public:
IntNode() { }
IntNode(int theData, IntNode* theLink)
: data(theData), link(theLink) { }
IntNode* getLink() const {return link;}
int getData() const {return data;}
void setData(int theData) {data = theData;}
void setLink(IntNode* pointer) {link=pointer;}
private:
int data;
IntNode *link;
};
typedef IntNode* IntNodePtr;

Copyright © 2016 Pearson Inc. All rights reserved. 17-13

 Linked List Class
• Notice all member function definitions are
inline
– Small and simple enough
• Notice two-parameter constructor
– Allows creation of nodes with specific data
value and specified link member
– Example:
IntNodePtr p2 = new IntNode(42, p1);

Copyright © 2016 Pearson Inc. All rights reserved. 17-14

 Create 1st Node
• IntNodePtr head;
– Declares pointer variable head
• head = new IntNode;
– Dynamically allocates new node
– Our 1st node in list, so assigned to head
• head->setData(3);
head->setLink(NULL);
– Sets head node data
– Link set to NULL since it’s the only node!

Copyright © 2016 Pearson Inc. All rights reserved. 17-15

 Display 17.3
Adding a Node
to the Head of
a Linked List

Copyright © 2016 Pearson Inc. All rights reserved. 17-16

 Lost Nodes Pitfall:
Display 17.5 Lost Nodes

Copyright © 2016 Pearson Inc. All rights reserved. 17-17

Display 17.6 Inserting in the Middle of a
Linked List (1 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-18

Display 17.6 Inserting in the Middle of a
Linked List (2 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-19

 Display 17.7
Removing
a Node

Copyright © 2016 Pearson Inc. All rights reserved. 17-20

 Searching a Linked List
• Function with two arguments:
IntNodePtr search(IntNodePtr head, int target);
//Precondition: pointer head points to head of
//linked list. Pointer in last node is NULL.
//If list is empty, head is NULL
//Returns pointer to 1st node containing target
//If not found, returns NULL
• Simple "traversal" of list
– Similar to array traversal

Copyright © 2016 Pearson Inc. All rights reserved. 17-21

 Pseudocode for search Function
• while (here doesn’t point to target node or
last node)
{
Make here point to next node in list
}
if (here node points to target)
return here;
else
return NULL;

Copyright © 2016 Pearson Inc. All rights reserved. 17-22

 Algorithm for search Function
• while (here->getData() != target &&
here->getLink() != NULL)
here = here->getLink();

if (here->getData() == target)
return here;
else
return NULL;
• Must make "special" case for empty list
– Not done here

Copyright © 2016 Pearson Inc. All rights reserved. 17-23

 Doubly Linked Lists
• What we just described is a singly linked list
– Can only follow links in one direction
• Doubly Linked List
– Links to the next node and another link to the previous
node
– Can follow links in either direction
– NULL signifies the beginning and end of the list
– Can make some operations easier, e.g. deletion since we
don’t need to search the list to find the node before the
one we want to remove

Copyright © 2016 Pearson Inc. All rights reserved. 17-24

 Doubly Linked Lists

class DoublyLinkedIntNode
{
public:
DoublyLinkedIntNode ( ){}
DoublyLinkedIntNode (int theData, DoublyLinkedIntNode* previous,
DoublyLinkedIntNode* next)
: data(theData), nextLink(next), previousLink(previous) {}
DoublyLinkedIntNode* getNextLink( ) const { return nextLink; }
DoublyLinkedIntNode* getPreviousLink( ) const { return previousLink; }
int getData( ) const { return data; }
void setData(int theData) { data = theData; }
void setNextLink(DoublyLinkedIntNode* pointer) { nextLink = pointer; }
void setPreviousLink(DoublyLinkedIntNode* pointer)
{ previousLink = pointer; }
private:
int data;
DoublyLinkedIntNode *nextLink;
DoublyLinkedIntNode *previousLink;
};
typedef DoublyLinkedIntNode* DoublyLinkedIntNodePtr;
Copyright © 2016 Pearson Inc. All rights reserved. 17-25
Adding a Node to the Front of a
Doubly Linked List (1 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-26

Adding a Node to the Front of a
Doubly Linked List (2 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-27

 Deleting a Node from a Doubly
Linked List
• Removing a node requires updating references
on both sides of the node we wish to delete
• Thanks to the backward link we do not need a
separate variable to keep track of the previous
node in the list like we did for the singly linked
list
– Can access via node->previous

Copyright © 2016 Pearson Inc. All rights reserved. 17-28

Deleting a Node from a Doubly
Linked List (1 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-29

Deleting a Node from a Doubly
Linked List (2 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-30

 Stacks
• Stack data structure:
– Retrieves data in reverse order of how stored
– LIFO – last-in/first-out
– Think of like "hole in ground"
• Stacks used for many tasks:
– Track C++ function calls
– Memory management
• Our use:
– Use linked lists to implement stacks

Copyright © 2016 Pearson Inc. All rights reserved. 17-31

 A Stack—Graphic:
Display 17.12 A Stack

Copyright © 2016 Pearson Inc. All rights reserved. 17-32

Display 17.17 Interface File for a Stack
Template Class (1 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-33

Display 17.17 Interface File for a Stack
Template Class (2 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-34

 Stack Template Class Driver:
Display 17.18 Program Using the Stack Template
Class (1 of 3)

Copyright © 2016 Pearson Inc. All rights reserved. 17-35

 Stack Template Class Driver:
Display 17.18 Program Using the Stack Template
Class (2 of 3)

Copyright © 2016 Pearson Inc. All rights reserved. 17-36

 Stack Template Class Driver:
Display 17.18 Program Using the Stack Template
Class (3 of 3)

Copyright © 2016 Pearson Inc. All rights reserved. 17-37

 Stack Push and Pop
• Adding data item to stack  push
– Considered "pushing" data onto stack
– Recall: goes to "top" of stack
• Removing data item from stack  pop
– Considered "popping" item off stack
– Recall: removed from "top" of stack

Copyright © 2016 Pearson Inc. All rights reserved. 17-38

 Queues
• Another common data structure:
– Handles data in first-in/first-out manner
(FIFO)
– Items inserted to end of list
– Items removed from front
• Representation of typical "line" forming
– Like bank teller lines, movie theatre
lines, etc.

Copyright © 2016 Pearson Inc. All rights reserved. 17-39

Display 17.20 Interface File for a Queue
Template Class (1 of 3)

Copyright © 2016 Pearson Inc. All rights reserved. 17-40

Display 17.20 Interface File for a Queue
Template Class (2 of 3)

Copyright © 2016 Pearson Inc. All rights reserved. 17-41

Display 17.20 Interface File for a Queue
Template Class (3 of 3)

Copyright © 2016 Pearson Inc. All rights reserved. 17-42

 Queue Template
Class Driver:
Display 17.21
Program Using
the Queue
Template Class

Copyright © 2016 Pearson Inc. All rights reserved. 17-43

 Hash Tables
• A hash table or hash map is a data structure
that efficiently stores and retrieves data from
memory
• Here we discuss a hash table that uses an
array in combination with singly linked lists
• Uses a hash function
– Maps an object to a key
– In our example, a string to an integer

Copyright © 2016 Pearson Inc. All rights reserved. 17-44

 Simple Hash Function for Strings
• Sum the ASCII value of every character in the
string and then compute the modulus of the
sum using the size of the fixed array.
int computeHash(string s)
{
int hash = 0;
for (int i = 0; i < s.length( ); i++)
{
hash = hash + s[i];
}
return hash % SIZE; // SIZE = 10 in example
}

Example: "dog" = ASCII 100, 111, 103

Hash = (100 + 111 + 103) % 10 = 4
Copyright © 2016 Pearson Inc. All rights reserved. 17-45
 Hash Table Idea
• Storage
– Make an array of fixed size, say 10
– In each array element store a linked list
– To add an item, map (i.e. hash) it to one of the 10
array elements, then add it to the linked list at
that location
• Retrieval
– To look up an item, determine its hash code then
search the linked list at the corresponding array
slot for the item
Copyright © 2016 Pearson Inc. All rights reserved. 17-46
 Constructing a Hash Table

Copyright © 2016 Pearson Inc. All rights reserved. 17-47

Interface File for a HashTable Class
(1 of 2)
1 // This is the header file hashtable.h. This is the interface
2 // for the class HashTable, which is a class for a hash table
3 // of strings.
4 #ifndef HASHTABLE_H
5 #define HASHTABLE_H

6 #include <string>
7 #include "listtools.h"
The library "listtools.h" is the linked list library
interface from Display 17.14.

8 using LinkedListSavitch::Node;
9 using std::string;

10 namespace HashTableSavitch
11 {
12 const int SIZE = 10; // Maximum size of the hash table array

Copyright © 2016 Pearson Inc. All rights reserved. 17-48

Interface File for a HashTable Class
(2 of 2)
13 class HashTable
14 {
15 public:
16 HashTable(); // Initialize empty hash table
17 // Normally a copy constructor and overloaded assignment
18 // operator would be included. They have been omitted
19 // to save space.
20 virtual ~HashTable(); // Destructor destroys hash table

21 bool containsString(string target) const;

22 // Returns true if target is in the hash table,
23 // false otherwise

24 void put(string s);

25 // Adds a new string to the hash table

26 private:
27 Node<string> *hashArray[SIZE]; // The actual hash table
28 static int computeHash(string s); // Compute a hash value
29 }; // HashTable
30 } // HashTableSavitch
31 #endif // HASHTABLE_H

Copyright © 2016 Pearson Inc. All rights reserved. 17-49

Implementation File for Hash Table
Class (1 of 3)
1 // This is the implementation file hashtable.cpp.
2 // This is the implementation of the class HashTable.

3 #include <string>
4 #include "listtools.h"
5 #include "hashtable.h"

6 using LinkedListSavitch::Node;
7 using LinkedListSavitch::search;
8 using LinkedListSavitch::headInsert;
9 using std::string;

10 namespace HashTableSavitch
11 {
12 HashTable::HashTable()
13 {
14 for (int i = 0; i < SIZE; i++)
15 {
16 hashArray[i] = NULL;
17 }
18 }

Copyright © 2016 Pearson Inc. All rights reserved. 17-50

Implementation File for Hash Table
Class (2 of 3)
19 HashTable::~HashTable()
20 {
21 for (int i=0; i<SIZE; i++)
22 {
23 Node<string> *next = hashArray[i];
24 while (next != NULL)
25 {
26 Node<string> *discard = next;
27 next = next->getLink( );
28 delete discard;
29 }
30 }
31 }

32 int HashTable::computeHash(string s)
33 {
34 int hash = 0;
35 for (int i = 0; i < s.length( ); i++)
36 {
37 hash = hash + s[i];
38 }
39 return hash % SIZE;
40 }
Copyright © 2016 Pearson Inc. All rights reserved. 17-51
Implementation File for Hash Table
Class (3 of 3)
41 void HashTable::put(string s)
42 {
43 int hash = computeHash(s);
44 if (search(hashArray[hash], s)==NULL)
45 {
46 // Only add the target if it's not in the list
47 headInsert(hashArray[hash], s);
48 }
49 }
50 } // HashTableSavitch

Copyright © 2016 Pearson Inc. All rights reserved. 17-52

 Hash Table Demonstration
1 // Program to demonstrate use of the HashTable class
2 #include <string>
3 #include <iostream> SAMPLE DIALOGUE
4 #include "hashtable.h" Adding dog, cat, turtle, bird
Contains dog? 1
5 #include "listtools.cpp"
Contains cat? 1
6 #include "hashtable.cpp" Contains turtle? 1
7 using std::string; Contains bird? 1
8 using std::cout; Contains fish? 0
9 using std::endl; Contains cow? 0
10 using HashTableSavitch::HashTable;

11 int main()
12 {
13 HashTable h;
14 cout << "Adding dog, cat, turtle, bird" << endl;
15 h.put("dog");
16 h.put("cat");
17 h.put("turtle");
18 h.put("bird");
19 cout << "Contains dog? " << h.containsString("dog") << endl;
20 cout << "Contains cat? " << h.containsString("cat") << endl;
21 cout << "Contains turtle? " << h.containsString("turtle") << endl;
22 cout << "Contains bird? " << h.containsString("bird") << endl;
23 cout << "Contains fish? " << h.containsString("fish") << endl;
24 cout << "Contains cow? " << h.containsString("cow") << endl;
25 return 0;
Copyright
26 } © 2016 Pearson Inc. All rights reserved. 17-53
 Hash Table Efficiency
• Worst Case
– Every item inserted into the table has the same hash key,
the find operation may have to search through all items
every time (same performance as a linked list)
• Best Case
– Every item inserted into the table has a different hash key,
the find operation will only have to search a list of size 1,
very fast
• Can decrease the chance of collisions with a better
hash function
• Tradeoff: Lower chance of collision with bigger hash
table, but more wasted memory space
Copyright © 2016 Pearson Inc. All rights reserved. 17-54
 Set Template Class
• A set is a collection of elements in which no
element occurs more than once
• We can implement a simple set that uses a
linked list to store the items in the set
• Fundamental set operations we will support:
– Add
Example
– Contains
– Union
– Intersection
Copyright © 2016 Pearson Inc. All rights reserved. 17-55
 Interface File for a Set Template
Class (1 of 2)
1 // This is the header file set.h. This is the interface
2 // for the class Set, which is a class for a generic set.
3 #ifndef SET_H
4 #define SET_H
5 #include "listtools.h"
"listtools.h" is the linked list library interface from Display 17.14.
6 using LinkedListSavitch::Node;

7 namespace SetSavitch
8 {
9 template<class T>
10 class Set
11 {
12 public:
13 Set() { head = NULL; } // Initialize empty set

14 // Normally a copy constructor and overloaded assignment

15 // operator would be included. They have been omitted
16 // to save space.

17 virtual ~Set(); // Destructor destroys set

Copyright © 2016 Pearson Inc. All rights reserved. 17-56

 Interface File for a Set Template
Class (2 of 2)
18 bool contains(T target) const;
19 // Returns true if target is in the set, false otherwise

20 void add(T item);

21 // Adds a new element to the set

22 void output();
23 // Outputs the set to the console

24 Set<T>* setUnion(const Set<T>& otherSet);

25 // Union calling object's set with otherSet
26 // and return a pointer to the new set

27 Set<T>* setIntersection(const Set<T>& otherSet);

28 // Intersect calling object's set with otherSet
29 // and return a pointer to the new set
30 private:
31 Node<T> *head;
32 }; // Set
33 } // SetSavitch
34 #endif // SET_H

Copyright © 2016 Pearson Inc. All rights reserved. 17-57

 Implementation File for a Set
Template Class (1 of 4)
1 // This is the implementation file set.cpp.
2 // This is the implementation of the class Set.
3 #include <iostream>
4 #include "listtools.h"
5 #include "set.h"
6 using std::cout;
7 using std::endl;
8 using LinkedListSavitch::Node;
9 using LinkedListSavitch::search;
10 using LinkedListSavitch::headInsert;
11 namespace SetSavitch
12 {
13 template<class T>
14 Set<T>::~Set()
15 {
16 Node<T> *toDelete = head;
17 while (head != NULL)
18 {
19 head = head->getLink( );
20 delete toDelete;
21 toDelete = head;
22 }
23 }
Copyright © 2016 Pearson Inc. All rights reserved. 17-58
 Implementation File for a Set
Template Class (2 of 4)
24 template<class T>
25 bool Set<T>::contains(T target) const
26 {
27 Node<T>* result = search(head, target);
28 if (result == NULL)
29 return false;
30 else
31 return true;
32 }

33 void Set<T>::output()
34 {
35 Node<T> *iterator = head;
36 while (iterator != NULL)
37 {
38 cout << iterator->getData( ) << " ";
39 iterator = iterator->getLink( );
40 }
41 cout << endl;
42 }

Copyright © 2016 Pearson Inc. All rights reserved. 17-59

 Implementation File for a Set
Template Class (3 of 4)
43 template<class T> 52 template<class T>
44 void Set<T>::add(T item) 53 Set<T>* Set<T>::setUnion(const
45 { Set<T>& otherSet)
46 if (search(head, item) 54 {
==NULL) 55 Set<T> *unionSet = new Set<T>();
47 { 56 Node<T>* iterator = head;
48 // Only add the target if 57 while (iterator != NULL)
it's not in the list 58 {
49 headInsert(head, item); 59 unionSet->add(iterator->getData(
50 } ));
51 } 60 iterator = iterator->getLink( );
61 }
62 iterator = otherSet.head;
63 while (iterator != NULL)
64 {
65 unionSet->add(iterator->getData(
));
66 iterator = iterator->getLink( );
67 }
68 return unionSet;
69 }

Copyright © 2016 Pearson Inc. All rights reserved. 17-60

 Implementation File for a Set
Template Class (4 of 4)
70 template<class T>
71 Set<T>* Set<T>::setIntersection(const Set<T>& otherSet)
72 {
73 Set<T> *interSet = new Set<T>();
74 Node<T>* iterator = head;
75 while (iterator != NULL)
76 {
77 if (otherSet.contains(iterator->getData( )))
78 {
79 interSet->add(iterator->getData( ));
80 }
81 iterator = iterator->getLink( );
82 }
83 return interSet;
84 }
85 } // SetSavitch

Copyright © 2016 Pearson Inc. All rights reserved. 17-61

 Set Demonstration (1 of 3)
1 // Program to demonstrate use of the Set class
2 #include <iostream>
3 #include <string>
4 #include "set.h"
5 #include "listtools.cpp"
6 #include "set.cpp"
7 using std::cout;
8 using std::endl;
9 using std::string;
10 using namespace SetSavitch;
11 int main()
12 {
13 Set<string> round; // Round things
14 Set<string> green; // Green things

15 round.add("peas"); // Sample data for both sets

16 round.add("ball");
17 round.add("pie");
18 round.add("grapes");
19 green.add("peas");
20 green.add("grapes");
21 green.add("garden hose");
22 green.add("grass");

Copyright © 2016 Pearson Inc. All rights reserved. 17-62

 Set Demonstration (2 of 3)
23 cout << "Contents of set round: ";
24 round.output();
25 cout << "Contents of set green: ";
26 green.output();

27 cout << "ball in set round? " <<

28 round.contains("ball") << endl;
29 cout << "ball in set green? " <<
30 green.contains("ball") << endl;

31 cout << "ball and peas in same set? ";

32 if ((round.contains("ball") && round.contains("peas")) ||
33 (green.contains("ball") && green.contains("peas")))
34 cout << " true" << endl;
35 else
36 cout << " false" << endl;

37 cout << "pie and grass in same set? ";

38 if ((round.contains("pie") && round.contains("grass")) ||
39 (green.contains("pie") && green.contains("grass")))
40 cout << " true" << endl;
41 else
42 cout << " false" << endl;

Copyright © 2016 Pearson Inc. All rights reserved. 17-63

 Set Demonstration (3 of 3)
43 cout << "Union of green and round: " << endl;
44 Set<string> *unionset = round.setUnion(green);
45 unionset->output();
46 delete unionset;

47 cout << "Intersection of green and round: " << endl;

48 Set<string> *interset = round.setIntersection(green);
49 interset->output();
50 delete interset;

51 return 0;
52 }

SAMPLE DIALOGUE
Contents of set round: grapes pie ball peas
Contents of set green: grass garden hose grapes peas
ball in set round? 1
ball in set green? 0
ball and peas in same set? true
pie and grass in same set? false
Union of green and round:
garden hose grass peas ball pie grapes
Intersection of green and round:
peas grapes

Copyright © 2016 Pearson Inc. All rights reserved. 17-64

 Friend Classes
• Recall constant use of getLink and
setlink accessor and mutator functions
– Somewhat of a nuisance
– Similar to making data public?!
• Public makes available to ALL!
• Use friend class
– Make queue template class "friend" of node
template class
– All private link members directly available in
member functions of queue class!

Copyright © 2016 Pearson Inc. All rights reserved. 17-65

 Forward Declaration
• Class friendships typically require classes
reference each other
– Presents problem
– How can "both" be declared at same time?
• Requires forward declaration
– Simple class heading given inside other:
class Queue; //Forward Dec.
– Announces "class Queue will exist"

Copyright © 2016 Pearson Inc. All rights reserved. 17-66

 Iterators
• Construct for cycling through data
– Like a "traversal"
– Allows "whatever" actions required on data
• Pointers typically used as iterators
– Seen in linked list implementation

Copyright © 2016 Pearson Inc. All rights reserved. 17-67

 Pointers as Iterators
• Recall: linked list: "prototypical" data structure
• Pointer: "prototypical" example of iterator
– Pointer used as iterator by moving thru
linked list node by node starting at head:
– Example:
Node_Type *iterator;
for (iterator = Head; iterator != NULL;
iterator=iterator->Link)
Do_Action

Copyright © 2016 Pearson Inc. All rights reserved. 17-68

 Iterator Classes
• More versatile than pointer
• Typical overloaded operators:
++ advances iterator to next item
-- retreats iterator to previous item
== Compares iterators
!= Compare for not equal
* Accesses one item
• Data structure class would have members:
begin(): returns iterator to 1st item in structure
end(): returns iterator to test if at end

Copyright © 2016 Pearson Inc. All rights reserved. 17-69

 Iterator Class Example
• Cycle through data structure named ds:

for (i=ds.begin();i!=ds.end();i++)
process *i //*i is current data item

• i is name of iterator

Copyright © 2016 Pearson Inc. All rights reserved. 17-70

 Trees Introduction
• Trees can be complex data structures
• Only basics here:
– Constructing, manipulating
– Using nodes and pointers
• Recall linked list: nodes have only one
pointer  next node
• Trees have two, & sometimes more,
pointers to other nodes

Copyright © 2016 Pearson Inc. All rights reserved. 17-71

 Tree Structure:
Display 17.35 A Binary Tree (1 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-72

 Tree Structure:
Display 17.35 A Binary Tree (2 of 2)

Copyright © 2016 Pearson Inc. All rights reserved. 17-73

 Tree Properties
• Notice paths
– From top to any node
– No "cycles" – follow pointers, will reach "end"
• Notice here each node has two links
– Called binary tree
– Most common type of tree
• Root node
– Similar to linked list’s head
• Leaf nodes
– Both link variables are NULL (no subtrees)

Copyright © 2016 Pearson Inc. All rights reserved. 17-74

 Trees and Recursion
• Note tree’s "recursive structure"
• Each tree has two subtrees
– Each subtree has two subtrees
• Etc., etc.
• Makes trees amenable to recursive
algorithms
– For searching especially!

Copyright © 2016 Pearson Inc. All rights reserved. 17-75

 Tree Processing
• Preorder Processing:
1. Process data in root node
2. Process left subtree
3. Process right subtree
• In-order Processing:
1. Process left subtree
2. Process data in root
3. Process right subtree
• Postorder Processing:
1. Process left subtree
2. Process right subtree
3. Process data in root

Copyright © 2016 Pearson Inc. All rights reserved. 17-76

 Tree Storage
• Our example stored values in special way:
– Called binary search tree storage rule:
1. values in left subtree less than root value
2. values in right subtree greater than root
3. rule applies recursively to each subtree
• Trees using this storage mechanism:
– Called binary search tree (BST)
– Traversals:
Inorder  values "in order"
Preorder  "prefix" notation
Postorder  "postfix" notation

Copyright © 2016 Pearson Inc. All rights reserved. 17-77

 Summary 1
• Node is struct or class object
– One or more members is pointer
– Nodes connected by member pointers
• Produce structures that grow and shrink at runtime
• Linked list
– List of nodes where each node points to next
– In a doubly linked lists there are pointers in both directions
• End of linked list marked with NULL pointer

Copyright © 2016 Pearson Inc. All rights reserved. 17-78

 Summary 2
• Stack is LIFO data structure
• Queue is FIFO data structure
• Hash Tables are data structures for quick storage and
retrieval; can be implemented with a linked list
• Sets can be implemented with linked lists
• Iterator construct allows cycling through
data items in given data structure
• Tree data structures
– Nodes have two member pointers
– Each point to other nodes/subtrees
• Binary search tree
– Special storage rules allow rapid searches

Copyright © 2016 Pearson Inc. All rights reserved. 17-79