Iterator on double Linkedlist class

Question

This code is from a "Data Structures" book By Micheal T.Goodrigh. I'm studying on my own so I have no one to explain this code for me:

typedef int Elem;               // list base element type
class NodeList {              // node-based list
private:
  struct Node {               // a node of the list
    Elem elem;                // element value
    Node* prev;               // previous in list
    Node* next;               // next in list
  };
public:
  class Iterator {                // an iterator for the list
  public:
    Elem& operator*();            // reference to the element
    bool operator==(const Iterator& p) const; // compare positions
    bool operator!=(const Iterator& p) const;
    Iterator& operator++();           // move to next position
    Iterator& operator--();           // move to previous position
    friend class NodeList;            // give NodeList access
  private:
    Node* v;                  // pointer to the node
    Iterator(Node* u);            // create from node
  };
public:
  NodeList();                 // default constructor
  int size() const;               // list size
  bool empty() const;             // is the list empty?
  Iterator begin() const;         // beginning position
  Iterator end() const;           // (just beyond) last position
  void insertFront(const Elem& e);        // insert at front
  void insertBack(const Elem& e);     // insert at rear
  void insert(const Iterator& p, const Elem& e); // insert e before p
  void eraseFront();              // remove first
  void eraseBack();               // remove last
  void erase(const Iterator& p);      // remove p
private:                  // data members
  int     n;                  // number of items
  Node*   header;             // head-of-list sentinel
  Node*   trailer;                // tail-of-list sentinel
};

I'm very confused how I use the insert() method. How do I pass an iterator to it while the iteretor is inside its class and Node is private?

int main () {
  NodeList Nl;
  N1.insert(p,5)      // How to create this p iterator and pass it to insert?
  return 0; 
}

Most of this code is similar to the STL's containers and iterators. I'd suggest you read a generic C++ tutorial, which will also cover the parts of the standard library that have their root in the STL. — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Apr 18, 2018 at 19:10

Remy Lebeau · Accepted Answer · 2018-04-18 19:18:24Z

1

The begin() method returns an Iterator to the front of the list. Iterator is a public nested class of NodeList, so you have to quality Iterator when declaring a variable of that type, eg:

int main ()
{
    NodeList Nl;

    // optionally, insert some items into the list...

    NodeList::Iterator p = Nl.begin();
    // optionally, increment p if you want to insert in the middle of the list...

    N1.insert(p, 5);

    return 0; 
}

edited Apr 18, 2018 at 19:18

answered Apr 18, 2018 at 19:10

Remy Lebeau

610k36 gold badges516 silver badges875 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Sara Alan Over a year ago

Thanks a lot dear , really I'm very thankful for this

SergeyA · Accepted Answer · 2018-04-18 19:22:10Z

0

To insert in the front or back of the list, you have to obtain the begin or end iterator.

To insert in the middle of the list, you have to obtain the begin iterator and than increment it until you reach the desired position (making sure you do not reach past the end iterator).

Alternatively, you can start with the end iterator and decrement it.

Example:

NodeList list;
list.insertFront(10); // put one element
list.insertFront(20); // put another element
// list is now 20 -> 10
NodeList::iterator it = list.begin();
++it;
list.insert(it, 15); // this inserts 15 before 10
// List now is 20 -> 15 -> 10

edited Apr 18, 2018 at 19:22

answered Apr 18, 2018 at 19:04

SergeyA

62.9k5 gold badges85 silver badges143 bronze badges

6 Comments

Remy Lebeau Over a year ago

"the only two insertable positions in the list are list beginning and list end" - that is not true. Once you have the begin iterator, you can advance it to the desired item before then calling insert(). This is how linked-list iterators always work, since a linked list does not allow for random access.

SergeyA Over a year ago

@RemyLebeau, good point, I missed the increment/decrement. Edited.

Sara Alan Over a year ago

dear, if I make a list and call the Begin function, it's returning an iterator object how I'll use it on may main function. Can I use the iterator function on it ( ++ , == , .. etc ) I'm really don't understand why he made this operator ( ++ , == , .. etc ) while I can't use them

Remy Lebeau Over a year ago

@SaraMohamed what makes you think you can't use them? That are all public. The only things that are private are the Nodes themselves, and you don't need direct access to them. Simply call the begin() method and save the iterator to a NodeList::Iterator variable, then use that variable as needed.

SergeyA Over a year ago

@SaraMohamed i added some code which hopefully clears your confusion.

|

Collectives™ on Stack Overflow

Iterator on double Linkedlist class

2 Answers 2

1 Comment

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related