C++ Iterators of a double linked list Goal: To understand how to work with itera

Question

C++ Iterators of a double linked list

Goal: To understand how to work with iterators of a linked list. To also learn how iterators are used, and why iterators are useful. The doublyLinkedList begin() method: This should create a temporary iterator object. Then set the temp's offTheRightEdge to false (unless the list is empty then set it to true), and temp's current should be assigned to the list's first. Then the temp object is returned. The doublyLinkedList end() method: This should create a temporary iterator object. Then set the temp's offTheRightEdge to true, and temp's current should be assigned to the list's last. Then the temp object is returned, overloaded * operator: This just returns the data that is in the node that current is pointing to. A one-liner, overloaded != operator: This checks to see if both objects have the same offTheRightEdge and the same current values. If both objects have the same values, then return false. Otherwise just return true. overloaded ++ prefix operator: The iterator should be moved forward one node, if possible. If moving it forward would mean it would become NULL, don't move it forward, and instead set the Boolean offTheRightEdge to true. If offTheRightEdge is already true, you don't need to do anything. You need a return type. You need to return a copy of the iterator, and you can do that with return *this. overloaded ++ postfix operator: Very similar to the prefix operator with one addition. You first have to make a copy of itself. Increment the object pointed to by this. Return the copy you previously made. overloaded - prefix operator: Same as the operator++ prefix, but going backwards. You need to return a copy of the iterator, and you can do that with return *this. You must also complete an ourReverse() method. This method passes in two iterators. You may only use knowledge obtained from iterators to complete this section. The most helpful tool will be swap() which takes any two values and swaps them. You don't want to pass the begin and end iterators. That just swaps what they point to, not the values inside. You instead want to get their values (i.e. dereference) and swap them. Besides that, you will likely want to use prefix ++, prefix --, !=, and making temporary copies of iterators to complete your logic. This ourReverse () method is then tested against our DoublyLinkedList object and a vector object. Note that I added one additional test on this assignment, testlterationTricky (). Those test the ability to handle a one node and a zero node linked list. Make sure you use the data member offTheRightEdge appropriately

Explanation / Answer

#include <string>
#include <vector>
#include <list>
#include <iostream>
#include <memory>

class Node ;

class LinkedList : public std::enable_shared_from_this<std::list>
{

public:
   static std::shared_ptr<Node> head ;

public:
   class Node : public std::enable_shared_from_this<Node>
   {

   public:
       int data = 0 ;
       std::shared_ptr<Node> next, prev ;

       Node( int d ) ;
   } ;

   /* Function to reverse a Doubly Linked List */
public:
   virtual void reverse() ;

   virtual void push( int new_data ) ;

   virtual void printList( const std::shared_ptr<Node> &node ) ;

   static void main( std::vector<std::wstring> &args ) ;
};

//.cpp file code:

LinkedList::Node::Node( int d )
{
   data = d ;
   next = prev = nullptr ;
}

void LinkedList::reverse()
{
   std::shared_ptr<Node> temp = nullptr ;
   std::shared_ptr<Node> current = head ;

   /* swap next and prev for all nodes of
   doubly linked list */
   while ( current != nullptr )
   {
       temp = current->prev ;
       current->prev = current->next ;
       current->next = temp ;
       current = current->prev ;
   }

   /* Before changing head, check for the cases like empty
   list and list with only one node */
   if ( temp != nullptr )
   {
       head = temp->prev ;
   }
}

void LinkedList::push( int new_data )
{
   /* allocate node */
   std::shared_ptr<Node> new_node = std::make_shared<Node>( new_data ) ;

   /* since we are adding at the begining,
   prev is always NULL */
   new_node->prev.reset() ;

   /* link the old list off the new node */
   new_node->next = head ;

   /* change prev of head node to new node */
   if( head != nullptr )
   {
       head->prev = new_node ;
   }

   /* move the head to point to the new node */
   head = new_node ;
}

void LinkedList::printList( const std::shared_ptr<Node> &node )
{
   while ( node != nullptr )
   {
       std::wcout << node->data << std::wstring( L" " ) ;
       node = node->next ;
   }
}

void LinkedList::main( std::vector<std::wstring> &args )
{
   std::list list = std::list() ;

   /* Let us create a sorted linked list to test the functions
   Created linked list will be 10->8->4->2 */
   list.push(2) ;
   list.push(4) ;
   list.push(8) ;
   list.push(10) ;

   std::wcout << std::wstring( L" Original linked list " ) << std::endl ;
   list.printList( head ) ;

   list.reverse() ;
   std::wcout << std::wstring( L"" ) << std::endl ;
   std::wcout << std::wstring( L" The reversed Linked List is " ) << std::endl ;
   list.printList( head ) ;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.