Singly Linked List
8 10 11 12
Head Tail
Doubly Linked List
A B C D
Head Tail
Iterator
4 9 10 13
head tail
Iterator
4 9 10 13
head tail
Iterator++
Iterator
4 9 10 13
head tail
Iterator++ Iterator--
Iterator
A B C
Head Tail
Iterators
Data Structures and Algo Analysis in C++
Mark Allen Weiss
Chapter 3.3
Iterators
Why we need Iterators?
Iterator++ Iterator--
Let’s assume you have created a DLList and shipped it
as a DDL file (library) for others to use
• Just like iostream library or string library
Now the user of this library wish to write new functionality
• find min, max, merge two lists, or do some other work that
require iterating the list or comparing some nodes of the list
But !!! the next ptr in List node class are private
Iterators
• An iterator allows a user to process every element of a container
(List) while isolating the user from the internal structure of the
container.
Iterator
4 9 10 13
• Iterators provide a consistent way to iterate on data structures of
all kinds, and make the code more
– readable,
– reusable, and
– less sensitive to a change
ITERATORS
ITERATORS
• An iterator is a pointer to an item of the LIST
• An iterator can
– Access: Get data of an item in the List
– Traversal: Modify itself to be able to point to next item
Iterator
4 9 10 13
List Iterator
template<class T>
class List {
private:
struct Node; // forward declaration
Node * head, *tail;
class ListIterator {
public:
ListIterator(Node * ptr = NULL) { iptr = ptr; };
ListIterator & operator++() {//prefix ++
if (iptr) iptr = iptr->next;
return (*this);
}
private:
Node * iptr;
};
public:
typedef ListIterator Iterator;
Iterator begin() {Iterator I(head); return I; }
Iterator end() { Iterator I(tail); return I; }
List() { head = tail = 0; };
~List();
Node * find(const T & val);
};
The caller
void main() {
cout << "SL list Iterator" << endl;
List<int> L;
for (int i = 0; i < 5; i++)
[Link](i);
List<int>::Iterator lit;
for (lit = [Link](); lit != nullptr; lit++)
cout << *lit << endl;
}
lit
4 9 10 13
List Iterator- with forward class declaration
template<class T>
class List {
private:
struct Node; // forward declaration
Node * head, *tail;
class ListIterator;
public:
typedef ListIterator Iterator;
void insert(Iterator it, const T & val);
Iterator begin() { return head;};
Iterator end() {return tail; };
List() { head = tail = 0; };
~List();
bool isEmpty() {return head == NULL;};
Node * find(const T & val);
void addToStart(const T & val);
bool deleteFromTail();
void print();
};
List Iterator- forward declaration
template<class T>
class List<T>::ListIterator {
public:
ListIterator(Node* t = NULL) { iptr = t; };
ListIterator operator++(int) {
//dummy int param give info that it is postfix ++
ListIterator old = *this;
++(*this)
return old;
}
private:
Node * iptr;
};
List Iterator- forward declaration
template<class T>
class List<T>::ListIterator {
public:
ListIterator(Node* t = NULL) { iptr = t; };
ListIterator operator++(int) {
//dummy int param give info that it is postfix ++
ListIterator old = *this;
++(*this)
return old;
}
ListIterator & operator++() {//prefix ++
if (iptr) iptr = iptr->next;
return (*this);
}
private:
Node * iptr;
};
List Iterator- forward declaration
template<class T>
class List<T>::ListIterator {
public:
ListIterator(Node* t = NULL) { iptr = t; };
T & operator*(){
return iptr->data;
}
bool operator==(const ListIterator & l) const
{
return iptr == [Link];
}
bool operator!=(const ListIterator & l) const {
return !(iptr == [Link]);
}
private:
Node * iptr;
};
List Iterator- forward declaration
template<class T>
class List<T>::ListIterator {
public:
friend class List;
ListIterator(Node* t = NULL) { iptr = t; };
ListIterator operator++(int) {//dummy int param give info that it is postfix ++
ListIterator old = *this;
++(*this)
return old;
}
ListIterator & operator++() {//prefix ++
if (iptr) iptr = iptr->next;
return (*this);
}
bool operator==(const ListIterator & l) const {
return iptr == [Link];
}
T & operator*() { return iptr->data; }
bool operator!=(const ListIterator & l) const {
return !(iptr == [Link]); }
private:
Node * iptr;
};
The caller
void main() {
cout << "SL list Iterator" << endl;
List<int> L;
for (int i = 0; i < 5; i++)
[Link](i);
List<int>::Iterator lit=[Link](), it2=[Link]();
it2++;
*lit = *it2
// this will copy the data of the object iterator it2 points at to the object
pointed at by lit
//we can do this because T & operator*() { return iptr->data; }
for (lit = L.begin2(); lit != nullptr ;lit++)
cout << *lit << endl;
What does this loop Do ?
for (it = [Link]();it != [Link]();){
} if(*it % 2 == 0)
it = [Link](it);
else
++it;
}
What does this function DO?
template<class T>
void Mystery(List<T> L1, List<T> L2, List<T> & L3 ) {
List<int>::Iterator L1i = [Link](), L2i = [Link]();
while (L1i != nullptr && L2i != nullptr) {
if (*L1i == *L2i) {
[Link](*L1i);
L2i++;
L1i++;
}
else if (*L1i < *L2i)
L2i++;
else
L1i++;
}
}
insert
ite
4 9 11 13
ite
4 9 11 13
10
Insert
template<class T>
void List<T>::insert(const Iterator ite, const T & val) {
Node * tmp = [Link]; Can we access the private member
of nested class ListIterator in List ?
Node * nptr = new Node(val, tmp->next);
tmp->next = nptr;
Make List class friend of ListIterator class
So only List class can use the functions of
} tmp ite iterator class.
Will this code work in all
scenarios ???
4 9 11 13
10
Insert
template<class T>
void List<T>::insert(const Iterator ite, const T & val) {
Node * tmp = [Link];
if (head != NULL && tmp != NULL) {// not empty
if (head == tail) {// only one element in current list
if (head == tmp)
head->next = tail = new Node(val);
}
else {
Node * nptr = new Node(val, tmp->next);
tmp->next = nptr;
if (tmp == tail)//last element
tail = nptr;
Make List class friend of iterator class
} So only List class can use the functions of iterator class.
} Or
Make getter to access iptr – Note with getter any
} function can access the elements of the list
TO-DO Iterators
• random shuffle(p,q):
– Rearrange the elements in the range from p to q in random order.
• reverse(p,q):
– Reverse the elements in the range from p to q.
• find(p,q,e):
– Return an iterator to the first element in the range
• min element(p,q):
– Return an iterator to the minimum element in the range from p to q.
• max element(p,q):
– Return an iterator to the maximum element in the range from p to q.
• for each(p,q, f ):
– Apply the function f the elements in the range from p to q.
Defining Functions outside the class
template<class T>
class List<T>::ListIterator {
public:
ListIterator(Node* t = NULL) { iptr = t; };
ListIterator & operator++();
bool & operator== (const ListIterator & l) const;
private:
Node * iptr;
};
template<class T>
bool List<T>::ListIterator::operator==(const ListIterator & l) const
{
return iptr == [Link];
}
template<class T>
typename List<T>::ListIterator & List<T>::ListIterator::operator++(){
if (iptr) iptr = iptr->next;
return (*this);
}