Code Snippets

  

C++ Source Code

Linked Lists

Provides base classes for fifo lifo and chained lists.

Submitted By: Martyn.Rae
Actions:
Rating:
Views: 847

Language: C++
Last Modified: February 4, 2010
Instructions: Copy the include part to a .h file, and the code part to a .cpp file. These classes are intended to be derived from, in order that they be of any use.

Snippet


  1. // Here is the include file
  2. #ifndef NULL
  3. #define NULL 0
  4. #endif
  5.  
  6. class list_base {
  7.         private:        list_base *next;                                                                                        // pointer to next chained item
  8.         public:                list_base() : next(NULL) { }                                                                 // constructor for list_base object
  9.                                 list_base * get_next() { return next; }                                         // get the next item pointer
  10.                                 void set_next(list_base * item) { next = item; } };                        // set next item pointer
  11.  
  12. class chain_base {
  13.         private:        chain_base * next;                                                                                        // pointer to next chained item
  14.                                 chain_base * prev;                                                                                        // pointer to previous chained item
  15.         public:                chain_base() : next(NULL), prev(NULL) { }                                         // constructor for chain_base object
  16.                                 chain_base * get_next() { return next; }                                         // return the next item in the list
  17.                                 void set_next(chain_base * item) { next = item; }                         // set next item pointer
  18.                                 chain_base * get_prev() { return prev; }                                         // return the previous item in the list
  19.                                 void set_prev(chain_base * item) { prev = item; } };                // set next item pointer
  20.  
  21. class fifo_list {
  22.         private:        list_base * first;                                                                                        // pointer to first chained item
  23.                                 list_base * last;                                                                                        // pointer to last chained item
  24.         public:                fifo_list() : first(NULL), last(NULL) { }                                         // constructor for fifo list object
  25.                                 ~fifo_list();                                                                                                // destructor for fifo list object
  26.                                 void push(list_base * item);                                                                // push item onto list at end
  27.                                 list_base * pop();        };                                                                                // pop item off front of list
  28.  
  29. class lifo_list {
  30.         private:        list_base * first;                                                                                        // pointer to first chained item
  31.                                 list_base * last;                                                                                        // pointer to last chained item
  32.         public:                lifo_list() : first(NULL), last(NULL) { }                                         // constructor for chain_base object
  33.                                 void push(list_base * item);                                                                // push item onto list at end
  34.                                 list_base * pop();        };                                                                                // pop item off front of list
  35.  
  36. class chain_list {
  37.         private:        chain_base * first;                                                                                        // pointer to first chained item
  38.                                 chain_base * last;                                                                                        // pointer to last chained item
  39.                                 chain_base * _current;                                                                                // pointer to current position in chain
  40.         public:                chain_list() : first(NULL), last(NULL) { }                                         // constructor for chain_base object
  41.                                 void push_front(chain_base * item);                                                        // push item onto chain at front
  42.                                 void push_back(chain_base * item);                                                        // push item onto chain at end
  43.                                 bool insert(chain_base * item);                                                                // insert item into chain after current
  44.                                 bool remove();                                                                                                // remove current item from chain
  45.                                 chain_base * top();                                                                                        // get first item in chain
  46.                                 chain_base * bottom();                                                                                // get last item in chain
  47.                                 chain_base * forward();                                                                                // get next item in chain
  48.                                 chain_base * backward();                                                                         // get previous item in chain
  49.                                 chain_base * current(); };                                                                        // return the current item
  50.  
  51. // And here is the code
  52.  
  53. #include "Linked Lists.h"
  54.  
  55. void fifo_list::push(list_base * item) {                                                                        // push item onto list at end
  56.         if ( first == NULL )                                                                                                        // if there are no items
  57.                 first = item;                                                                                                                // this item is the first item
  58.         else                                                                                                                                        // otherwise
  59.                 last->set_next(item);                                                                                                // set last item's next as being this item
  60.         last = item;                                                                                                                        // set this item as the new last
  61.         return;                                                                                                                                 // return to caller
  62. }
  63.  
  64. list_base * fifo_list::pop()                                                                                                // pop item off front of list
  65. {
  66.         list_base * item = first;                                                                                                // set item's the first item
  67.         first = first->get_next();                                                                                                // set first item as being first item's next item
  68.         if ( first == NULL ) last = NULL;                                                                                // if the first item is now null, then make last also
  69.         return item;                                                                                                                        // return item to caller
  70. }
  71.  
  72. void lifo_list::push(list_base * item)                                                                                // push item onto list at front
  73. {
  74.         if ( first == NULL )                                                                                                        // if there are no items
  75.                 last = item;                                                                                                                // this item is the last item
  76.         else                                                                                                                                        // otherwise
  77.                 item->set_next(first);                                                                                                // set this item's next as being current first
  78.         first = item;                                                                                                                        // set this item as the new first
  79.         return;                                                                                                                                        // return to caller
  80. }
  81.  
  82. list_base * lifo_list::pop()                                                                                                // pop item off front of list
  83. {
  84.         list_base * item = first;                                                                                                // set item's the first item
  85.         first = first->get_next();                                                                                                // set first item as being first item's next item
  86.         if ( first == NULL ) last = NULL;                                                                                // if the first item is now null, then make last also
  87.         return item;                                                                                                                        // return item to caller
  88. }
  89.  
  90. void chain_list::push_front(chain_base * item) {                                                        // push item onto chain at front
  91.         if ( first == NULL ) {                                                                                                        // if there are no items
  92.                 first = last = _current = item;                                                                                // set first, last and current to item
  93.                 return;                                                                                                                                // return to caller
  94.         }
  95.         item->set_next(first);                                                                                                        // set this item's next to first item
  96.         first->set_prev(item);                                                                                                        // set first item's previous to this item
  97.         first = item;                                                                                                                        // set this item as the new first item
  98. }
  99.  
  100. void chain_list::push_back(chain_base * item) {                                                                // push item onto chain at end
  101.         if ( first == NULL ) {                                                                                                        // if there are no items
  102.                 first = last = _current = item;                                                                                // set first, last and current to item
  103.                 return;                                                                                                                                // return to caller
  104.         }
  105.         last->set_next(item);                                                                                                        // set last item's next to this item
  106.         item->set_prev(last);                                                                                                        // set this item's previous to last item
  107.         last = item;                                                                                                                        // set this item as the new last item
  108. }
  109.  
  110. bool chain_list::insert(chain_base * item) {                                                                // insert item into chain after current
  111.         if ( _current == NULL ) return false;                                                                        // fail if there is not current item
  112.         if ( first == NULL ) {                                                                                                        // if this is the first item in chain
  113.                 first = last = _current = item;                                                                                // set first, last and current to item
  114.                 return true;                                                                                                                // tell caller we have completed ok
  115.         }
  116.         if ( _current->get_next() == NULL ) {                                                                        // if there is no current next item ...
  117.                 push_back(item);                                                                                                        // ... we are adding to end of list so push_back
  118.                 return true;                                                                                                                // tell caller we have completed ok
  119.         }
  120.         item->set_next(_current->get_next());                                                                        // set item being inserted's next to current's next
  121.         item->set_prev(_current);                                                                                                // set item being inserted's previous to current
  122.         _current->set_next(item);                                                                                                // set current's next to item being inserted
  123.         _current->get_next()->set_prev(item);                                                                        // set current's next's previous to item being inserted
  124.         return true;                                                                                                                        // tell caller we have completed ok
  125. }
  126.  
  127. bool chain_list::remove() {                                                                                                        // remove current item from chain
  128.         if ( _current == NULL ) return false;                                                                        // fail if there is not current item
  129.         if ( _current->get_next() == NULL )                                                                                // if this is the last item
  130.                 last = _current->get_prev();                                                                                // set last item as being current's previous item
  131.         else                                                                                                                                        // otherwise
  132.                 _current->get_prev()->set_next(_current->get_next());                                // set current's previous's next to current's next
  133.         if ( _current->get_prev() == NULL )                                                                                // if this is the first item
  134.                 first = _current->get_next();                                                                                // set first item to current's next item
  135.         else                                                                                                                                        // otherwise
  136.                 _current->get_next()->set_prev(_current->get_prev());                                // set current's next's previous to current's previous
  137.         _current = NULL;                                                                                                                // there is now no current item
  138.         return true;                                                                                                                        // tell caller we have completed ok
  139. }
  140.  
  141. chain_base * chain_list::top() {                                                                                        // get first item in chain
  142.         return _current = first;                                                                                                // return the start of the list
  143. }
  144.  
  145. chain_base * chain_list::bottom() {                                                                                        // get last item in chain
  146.         return _current = last;                                                                                                        // return the end of the list
  147. }
  148.  
  149. chain_base * chain_list::forward() {                                                                                // get next item in chain
  150.         return _current = _current->get_next();                                                                        // return the next item in list
  151. }
  152.  
  153. chain_base * chain_list::backward() {                                                                                // get previous item in chain
  154.         return _current = _current->get_prev();                                                                        // return the previous item in list
  155. }
  156.  
  157. chain_base * chain_list::current() {                                                                                // return the current item
  158.         return _current;                                                                                                                // return it!
  159. }
  160.  
  161.  

Copy & Paste

Comments
There are currently no comments for this snippet. Be the first to comment!

Add comment
You must be registered and logged on to </dream.in.code> to leave comments.