Implementing a Doubly Linked List Iterator
This lesson contains approximately 29 minutes of video content.
Set-up
Implementing a DoublyLinkedListIterator<T>
Updating DoublyLinkedList<T> to use DoublyLinkedListIterator<T>
Using DoublyLinkedList<T>'s iterators
Activity: Doubly linked list iterator implementation
Graded Playground Autograder
Activity Prompt:
Member functions you must implement for
Member functions provided to you for
In this programming problem, you will implement a forward iterator type DoublyLinkedListIterator<T> for a DoublyLinkedList<T>. To understand the DoublyLinkedList<T>'s structure, you should read includes/doubly_linked_list.hpp and includes/node.hpp. Understanding the data structure for which you're writing an iterator is important.
After reviewing the structure of DoublyLinkedList<T>, you will implement a forward iterator type DoublyLinkedListIterator<T> for it. The member functions that you are responsible for follow.
Member functions you must implement for DoublyLinkedListIterator<T>
| public: | |
DoublyLinkedListIterator(Node<T>* ptr); |
Parameterized constructor. Initializes current_ with the value stored in ptr. |
T& operator*(); |
Returns a reference to the data member of the node pointed to by current_. |
DoublyLinkedListIterator<T>& operator++(); |
Pre-increment Operator (invoked as ++obj). This will move current_ one node forward in the sequence of nodes contained within the doubly linked list. This operator will return a self-reference (i.e., return *this) after the increment has been performed. |
DoublyLinkedListIterator<T> operator++(int); |
Post-increment Operator (invoked as obj++). A temporary DoublyLinkedListIterator<T> tmp is initialized with the state of this iterator object. You can accomplish this using the copy constructor in conjunction with *this. After recording the state of this iterator object in tmp, this->current_ is moved forward to the next node in the sequence of nodes contained within the doubly linked list. You then return tmp, which represents the state of this iterator prior to the increment.
|
bool DoublyLinkedListIterator<T>::operator!=(
const DoublyLinkedListIterator<T>& other); |
Returns true if the two iterators are not pointing to the same node in the sequence; false otherwise.
|
Member functions provided to you for DoublyLinkedListIterator<T>
| public: | |
DoublyLinkedListIterator() = default; |
Default constructor. |
DoublyLinkedListIterator<T>'s data members
| private: | |
Node<T>* current_ |
Pointer to the node in the doubly linked list's sequence to which the iterator currently "points". |
We will only transmit the contents of your doubly_linked_list_iterator.hpp file to the grader. Let's get started!
#include <iostream>
#include "doubly_linked_list.hpp"
int main() {
DoublyLinkedList<int> list;
list.push_back(11);
list.push_back(12);
for (auto i = list.begin(); i != list.end(); ++i)
std::cout << *i << std::endl;
}
#ifndef DOUBLY_LINKED_LIST_ITERATOR_HPP
#define DOUBLY_LINKED_LIST_ITERATOR_HPP
#include <iterator>
#include "node.hpp"
template <typename T>
class DoublyLinkedListIterator : std::iterator<std::forward_iterator_tag, T> {
public:
DoublyLinkedListIterator() = default;
DoublyLinkedListIterator(Node<T>* ptr);
T& operator*();
DoublyLinkedListIterator<T>& operator++();
DoublyLinkedListIterator<T> operator++(int);
bool operator!=(const DoublyLinkedListIterator<T>& other);
private:
Node<T>* current_ = nullptr;
};
template <typename T>
DoublyLinkedListIterator<T>::DoublyLinkedListIterator(Node<T>* ptr) {
/*
implement this function
*/
}
template <typename T>
T& DoublyLinkedListIterator<T>::operator*() {
/*
implement this function
*/
}
template <typename T>
DoublyLinkedListIterator<T>& DoublyLinkedListIterator<T>::operator++() {
/*
implement this function
*/
}
template <typename T>
DoublyLinkedListIterator<T> DoublyLinkedListIterator<T>::operator++(int) {
/*
implement this function
*/
}
template <typename T>
bool DoublyLinkedListIterator<T>::operator!=(
const DoublyLinkedListIterator<T>& other) {
/*
implement this function
*/
}
#endif
#ifndef DOUBLY_LINKED_LIST_HPP
#define DOUBLY_LINKED_LIST_HPP
#include <cstdlib> // provides definition for size_t, the maximum size of a theoretically possible object of any type
#include "doubly_linked_list_iterator.hpp"
#include "node.hpp"
template <typename T>
class DoublyLinkedList {
public:
DoublyLinkedList() = default;
DoublyLinkedList(const DoublyLinkedList<T>& rhs);
DoublyLinkedList<T>& operator=(const DoublyLinkedList<T>& rhs) = delete;
~DoublyLinkedList();
void push_back(T val);
using iterator = DoublyLinkedListIterator<T>;
iterator begin() { return DoublyLinkedListIterator<T>(head_); }
iterator end() { return DoublyLinkedListIterator<T>(nullptr); }
protected:
Node<T>* head_ = nullptr;
Node<T>* tail_ = nullptr;
size_t size_ = 0;
};
template <typename T>
void DoublyLinkedList<T>::push_back(T val) {
Node<T>* n = new Node<T>(val);
if (head_ == nullptr) head_ = n;
if (tail_ != nullptr) tail_->next = n;
n->prev = tail_;
tail_ = n;
size_ += 1;
}
template <typename T>
DoublyLinkedList<T>::DoublyLinkedList(const DoublyLinkedList<T>& rhs) {
Node<T>* curr = rhs.head_;
while (curr != nullptr) {
push_back(curr->data);
curr = curr->next;
}
}
template <typename T>
DoublyLinkedList<T>::~DoublyLinkedList() {
while (head_ != nullptr) {
Node<T>* tmp = head_->next;
delete head_;
head_ = tmp;
}
}
#endif
#ifndef NODE_HPP
#define NODE_HPP
template <typename T>
struct Node {
Node() = default;
Node(T data) : data(data) {}
T data;
Node *next = nullptr;
Node *prev = nullptr;
};
#endif
Submit is not supported in this site.