SHARE
TWEET

Untitled

a guest Oct 17th, 2019 76 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. typedef string Elem;                // list base element type
  6. class NodeList {                // node-based list
  7. private:
  8.     struct Node {               // a node of the list
  9.         Elem elem;              // element value
  10.         Node* prev;             // previous in list
  11.         Node* next;             // next in list
  12.     };
  13. public:
  14.     class Iterator {                // an iterator for the list
  15.     public:
  16.         Elem& operator*();          // reference to the element
  17.         bool operator==(const Iterator& p) const;   // compare positions
  18.         bool operator!=(const Iterator& p) const;
  19.         Iterator& operator++();         // move to next position
  20.         Iterator& operator--();         // move to previous position
  21.         friend class NodeList;          // give NodeList access
  22.     private:
  23.         Node* v;                    // pointer to the node
  24.         Iterator(Node* u);          // create from node
  25.     };
  26. public:
  27.     NodeList();                 // default constructor
  28.     int size() const;               // list size
  29.     bool empty() const;             // is the list empty?
  30.     Iterator begin() const;         // beginning position
  31.     Iterator end() const;           // (just beyond) last position
  32.     void insertFront(const Elem& e);        // insert at front
  33.     void insertBack(const Elem& e);     // insert at rear
  34.     void insert(const Iterator& p, const Elem& e); // insert e before p
  35.     void eraseFront();              // remove first
  36.     void eraseBack();               // remove last
  37.     void erase(const Iterator& p);      // remove p
  38.     // housekeeping functions omitted...
  39. private:                    // data members
  40.     int     n;                  // number of items
  41.     Node*   header;             // head-of-list sentinel
  42.     Node*   trailer;                // tail-of-list sentinel
  43. };
  44.  
  45. NodeList::NodeList() {          // constructor
  46.     n = 0;                  // initially empty
  47.     header = new Node;              // create sentinels
  48.     trailer = new Node;
  49.     header->next = trailer;         // have them point to each other
  50.     trailer->prev = header;
  51. }
  52.  
  53. int NodeList::size() const          // list size
  54. {
  55.     return n;
  56. }
  57.  
  58. bool NodeList::empty() const            // is the list empty?
  59. {
  60.     return (n == 0);
  61. }
  62.  
  63. NodeList::Iterator::Iterator(Node* u)       // constructor from Node*
  64. {
  65.     v = u;
  66. }
  67.  
  68. Elem& NodeList::Iterator::operator*()       // reference to the element
  69. {
  70.     return v->elem;
  71. }
  72. // compare positions
  73. bool NodeList::Iterator::operator==(const Iterator& p) const
  74. {
  75.     return v == p.v;
  76. }
  77.  
  78. bool NodeList::Iterator::operator!=(const Iterator& p) const
  79. {
  80.     return v != p.v;
  81. }
  82. // move to next position
  83. NodeList::Iterator& NodeList::Iterator::operator++()
  84. {
  85.     v = v->next; return *this;
  86. }
  87. // move to previous position
  88. NodeList::Iterator& NodeList::Iterator::operator--()
  89. {
  90.     v = v->prev; return *this;
  91. }
  92.  
  93. // insert e before p
  94. void NodeList::insert(const NodeList::Iterator& p, const Elem& e) {
  95.     Node* w = p.v;              // p's node
  96.     Node* u = w->prev;              // p's predecessor
  97.     Node* v = new Node;             // new node to insert
  98.     v->elem = e;
  99.     v->next = w;  w->prev = v;          // link in v before w
  100.     v->prev = u;  u->next = v;          // link in v after u
  101.     n++;
  102. }
  103.  
  104. void NodeList::insertFront(const Elem& e)   // insert at front
  105. {
  106.     insert(begin(), e);
  107. }
  108.  
  109. void NodeList::insertBack(const Elem& e)    // insert at rear
  110. {
  111.     insert(end(), e);
  112. }
  113.  
  114. void NodeList::erase(const Iterator& p) {   // remove p
  115.     Node* v = p.v;              // node to remove
  116.     Node* w = v->next;              // successor
  117.     Node* u = v->prev;              // predecessor
  118.     u->next = w;  w->prev = u;          // unlink p
  119.     delete v;                   // delete this node
  120.     n--;                    // one fewer element
  121. }
  122.  
  123. void NodeList::eraseFront()         // remove first
  124. {
  125.     erase(begin());
  126. }
  127.  
  128. void NodeList::eraseBack()          // remove last
  129. {
  130.     erase(--end());
  131. }
  132.  
  133. NodeList::Iterator NodeList::begin() const  // begin position is first item
  134. {
  135.     return Iterator(header->next);
  136. }
  137.  
  138. NodeList::Iterator NodeList::end() const    // end position is just beyond last
  139. {
  140.     return Iterator(trailer);
  141. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top