(C++) linked_list class (both the header file and the template file)

By SnipBot | Published: November 2, 2011

This is a linked list that can be used like an array where instead of using [] after the reference you just used .get() (and some other methods) but now you don’t have to worry about sizing.

For example, with an array you would do:

cout

  1. /*#########################################################
  2. HEADER FILE "linked_list.h":
  3. ###########################################################*/
  4.  
  5. /* Joe Pea – Linked List */
  6.  
  7. #ifndef LINKED_LIST_H
  8. #define LINKED_LIST_H
  9.  
  10. #include <cstdlib>  // Provides size_t
  11. #include "node.h"  // Provides node class
  12.  
  13. namespace CISP430_A5
  14. {
  15.     template <class Item>
  16.     class linked_list
  17.         /*TODO: * Optimize so that we don’t have to iterate through each address to reach a desired position.
  18.                           Make a "position" field for each Node object or something?
  19.                           Or create a "last_position" variable in this class so we can iterate forward
  20.                           or backward from the last position instead of from the beginning each time?
  21.                         * Add post and pre conditions for all the new functions above.
  22.         */
  23.         /**
  24.                         The /*REMOVED*//*, /*STAYS THE SAME*//*, and /*ADDED*//* comments show the
  25.                         differences in converting from the sequence class to the linked_list class.
  26.         */
  27.     {
  28.                 public:
  29.                 /* TYPEDEFS and MEMBER CONSTANTS: */
  30.                         typedef Item value_type;
  31.                         typedef size_t size_type;
  32.                        
  33.                
  34.                
  35.                 /* CONSTRUCTORS and DESTRUCTOR: */
  36.                         linked_list( );
  37.                         linked_list(const linked_list& source);
  38.                         ~linked_list( );
  39.                        
  40.                
  41.                
  42.                 /* MODIFICATION MEMBER FUNCTIONS */
  43.                         /*ADDED:*/
  44.                                 value_type get(int position); // get item at position x
  45.                                 void set(int position, const value_type& entry); // set item at position x, if past boundaries, just modify at beginning or at end.
  46.                                 void add(const value_type& entry); // add to the end of list
  47.                                 void insert(int position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
  48.                                 void attach(int position, const value_type& entry); // set item at position x, if past boundaries, just insert at beginning or attach at end.
  49.                                 void remove(int position);
  50.                
  51.                         /*REMOVED:*/
  52.                                 /*void remove_current( );*/
  53.                                 /*void start( );*/
  54.                                 /*void advance( );*/
  55.                                 /*void insert(const value_type& entry);*/
  56.                                 /*void attach(const value_type& entry);*/
  57.                
  58.                         /*STAYS THE SAME:*/
  59.                                 void operator=(const linked_list& source);
  60.                        
  61.                
  62.                
  63.                 /* CONSTANT MEMBER FUNCTIONS */
  64.                         /*STAYS THE SAME:*/
  65.                                 value_type current( ) const;
  66.                                 size_type size( ) const { return many_nodes; }
  67.                                 bool is_item( ) const { return (cursor != NULL); }
  68.  
  69.                
  70.                
  71.                 private:
  72.                 /*PRIVATE HELPER FUNCTIONS*/
  73.                         /*ADDED:*/
  74.                                 void remove_current( );
  75.                                 void start( );
  76.                                 void advance( );
  77.                                 void insert_here(const value_type& entry); // same as insert() from sequence. insert at current position.
  78.                                 void attach_here(const value_type& entry); // same as attach() from sequence. attach at current position.
  79.                
  80.                
  81.                
  82.                 /*PRIVATE VARIABLES*/  
  83.                         /*STAYS THE SAME:*/
  84.                                 node<Item> *cursor;
  85.                                 node<Item> *precursor;
  86.                                 node<Item> *head_ptr;
  87.                                 node<Item> *tail_ptr;
  88.                                 size_type many_nodes;
  89.     };
  90. }
  91.  
  92.  
  93.  
  94.  
  95.  
  96. /* Sample usage:
  97. int main(void) {
  98.  
  99.         linked_list items = new linked_list;
  100.         items.attach(10);
  101.         items.insert(30);
  102.         items.attach(20);
  103.         items.insert(40);
  104.  
  105.         // for each item in the list:
  106.         for (int i=0; i<items.size(); ++i) {
  107.                 cout << items.get(i) << endl;
  108.         }
  109.        
  110.         items.set(2, 50);
  111.         // item at position 2 is now 50.
  112. }
  113. */
  114.  
  115.  
  116.  
  117.  
  118. // The implementation of a template class must be included in its header file:
  119. #include "linked_list.template"
  120. #endif
  121.  
  122. /*#########################################################
  123. TEMPLATE FILE "linked_list.template":
  124. ###########################################################*/
  125.  
  126.  
  127. /* Joe Pea – CISP430 Assignment 5 */
  128.  
  129. namespace CISP430_A5 {
  130. /*I’ve marked lines/blocks as REMOVED or ADDED in order to tell what I changed
  131.         from the sequence class to create my ideal linked_list class*/
  132. /*TODO: Add previous field to Node class and remove usage of precursor.*/
  133.                        
  134.         /* CONSTRUCTORS and DESTRUCTOR */
  135.        
  136.         template <class Item>
  137.         linked_list<Item>::linked_list() {
  138.                 head_ptr = NULL;
  139.                 tail_ptr = NULL;
  140.                 cursor = NULL;
  141.                 precursor = NULL; // no need for this if Node objects have a "previous" link field.
  142.                 many_nodes = 0;
  143.         }
  144.        
  145.         template <class Item>
  146.         linked_list<Item>::linked_list( const linked_list& source ) { // copier
  147.                
  148.                 int src_size = source.size(); // to replicate cursor position
  149.                 int many_til_end = 0; // to replicate cursor position
  150.                 int many_til_mid = 0; // to replicate cursor position
  151.                 node<Item> *src_cursor = source.cursor; // to replicate cursor position
  152.                
  153.                 list_copy(source.head_ptr, head_ptr, tail_ptr);
  154.                
  155.                 /*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
  156.                         many_nodes = source.many_nodes;
  157.                
  158.                 /*replicate the cursor position*/
  159.                         if (src_cursor != NULL) {
  160.                                 while (src_cursor != NULL) {
  161.                                         ++many_til_end;
  162.                                         src_cursor = src_cursor->link();
  163.                                 }
  164.                                 many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
  165.                                 start(); // put this.cursor at beginning. // DEPENDS ON VALUE OF many_nodes ABOVE
  166.                                 for (int i=0; i<many_til_mid; ++i) {
  167.                                         advance(); // DEPENDS ON VALUE OF many_nodes ABOVE
  168.                                 }
  169.                                 /* after the for loop, the new linked_list’s cursor should be at the same position as the source’s cursor was.*/
  170.                         }
  171.                         else {
  172.                                 cursor = NULL;
  173.                                 precursor = NULL;
  174.                         }
  175.         }
  176.        
  177.         template <class Item>
  178.         linked_list<Item>::~linked_list() { // Destructor
  179.                 list_clear(head_ptr);
  180.                 head_ptr = tail_ptr = cursor = precursor = NULL;
  181.                 many_nodes = 0;
  182.         }
  183.                        
  184.         /* MODIFICATION MEMBER FUNCTIONS */
  185.        
  186.         template <class Item>
  187.         void linked_list<Item>::start() {
  188.                 if (many_nodes > 0) { // if at least one item exists
  189.                         cursor = head_ptr;
  190.                         precursor = NULL;
  191.                 }
  192.         }
  193.        
  194.         template <class Item>
  195.         void linked_list<Item>::advance() {
  196.                 if (is_item()) {
  197.                         precursor = cursor;
  198.                         cursor = cursor->link();
  199.                         if ( cursor == NULL ) {
  200.                                 precursor = NULL;
  201.                         }
  202.                 }
  203.         }
  204.        
  205.         /*
  206.         ADDED [
  207.         */
  208.                 template <class Item>
  209.                 typename linked_list<Item>::value_type linked_list<Item>::get(int position) {
  210.                         for (int i=0; i<=position; ++i) { // advance the cursor to the position then return item
  211.                                 if (i==0)
  212.                                         start();
  213.                                 else
  214.                                         advance();
  215.                                
  216.                                 if (i==position) {
  217.                                         return current();
  218.                                 }
  219.                         }
  220.                 }
  221.                
  222.                 template <class Item>
  223.                 void linked_list<Item>::set(int position, const value_type& entry) {
  224.                         if (is_item()) { // only set at a valid position.
  225.                        
  226.                                 insert(position, entry); // insert new item to list
  227.                                
  228.                                 advance();
  229.                                 remove_current(); // remove old item from list.
  230.                         }
  231.                 }
  232.                
  233.                 template <class Item>
  234.                 void linked_list<Item>::add(const value_type& entry) {
  235.                         cursor = precursor = NULL; // remove cursor
  236.                         attach_here(entry); // <<-- attaches at end when no cursor.
  237.                 }
  238.                
  239.                 template <class Item>
  240.                 void linked_list<Item>::remove(int position) {
  241.                         for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
  242.                                 if (i==0)
  243.                                         start();
  244.                                 else
  245.                                         advance();
  246.                                
  247.                                 if (i==position) {
  248.                                         remove_current();
  249.                                 }
  250.                         }
  251.                 }
  252.                
  253.                 template <class Item>
  254.                 void linked_list<Item>::insert(int position, const value_type& entry) {
  255.                         for (int i=0; i<=position; ++i) { // advance the cursor to the position then insert item
  256.                                 if (i==0)
  257.                                         start();
  258.                                 else
  259.                                         advance();
  260.                                
  261.                                 if (i==position) {
  262.                                         insert_here(entry);
  263.                                 }
  264.                         }
  265.                 }
  266.         /*
  267.         ]
  268.         */
  269.        
  270.         template <class Item>
  271.         void linked_list<Item>::insert_here(const value_type &entry) {
  272.         /*REMOVED*/
  273.                 // void linked_list<Item>::insert(const value_type &entry) {
  274.                
  275.                 /*if the list is empty*/
  276.                 if (!is_item() && !many_nodes) {
  277.                         cursor = new node<Item>(entry);
  278.                         head_ptr = cursor;
  279.                         tail_ptr = cursor;
  280.                 }
  281.                
  282.                 /*if the list is not empty and cursor points to the first item*/
  283.                 else if (is_item() && cursor == head_ptr) {
  284.                         cursor = new node<Item>( entry );
  285.                         cursor->set_link( head_ptr );
  286.                         head_ptr = cursor;
  287.                 }
  288.                
  289.                 /*if the list is not empty and there is no current item*/
  290.                 else if (!is_item() && many_nodes) {
  291.                         cursor = new node<Item>( entry );
  292.                         cursor->set_link( head_ptr );
  293.                         head_ptr = cursor;
  294.                 }
  295.                
  296.                 /*if the list is not empty and the cursor points somewhere in
  297.                         the middle(including last item)*/
  298.                 else if (is_item() && cursor != head_ptr) {
  299.                         cursor = new node<Item>( entry );
  300.                         cursor->set_link( precursor->link() );
  301.                         precursor->set_link( cursor );
  302.                 }
  303.                
  304.                 ++many_nodes; //increase the node count
  305.         }
  306.        
  307.         /*ADDED*/
  308.                 template <class Item>
  309.                 void linked_list<Item>::attach(int position, const value_type& entry) {
  310.                         for (int i=0; i<=position; ++i) { // advance the cursor to the position then attach item
  311.                                 if (i==0)
  312.                                         start();
  313.                                 else
  314.                                         advance();
  315.                                
  316.                                 if (i==position) {
  317.                                         attach_here(entry);
  318.                                 }
  319.                         }
  320.                 }
  321.        
  322.         template <class Item>
  323.         void linked_list<Item>::attach_here(const value_type& entry) {
  324.         /*REMOVED*/
  325.                 // void linked_list<Item>::attach(const value_type& entry) {
  326.                
  327.                 /*if the list is empty*/
  328.                 if (!is_item() && !many_nodes) {
  329.                         cursor = new node<Item>(entry);
  330.                         head_ptr = cursor;
  331.                         tail_ptr = cursor;
  332.                         precursor = NULL;
  333.                 }
  334.                
  335.                 /*if the list is not empty and cursor points to the first item and there’s only one item*/
  336.                 else if (is_item() && many_nodes == 1) {
  337.                         cursor = new node<Item>( entry );
  338.                         cursor->set_link( head_ptr->link() );
  339.                         head_ptr->set_link( cursor );
  340.                         precursor = head_ptr;
  341.                         tail_ptr = cursor;
  342.                 }
  343.                
  344.                 /*if the list is not empty and cursor points to the first item and there’s more than one item*/
  345.                 else if (is_item() && many_nodes > 1 && cursor == head_ptr ) {
  346.                         cursor = new node<Item>( entry );
  347.                         cursor->set_link( head_ptr->link() );
  348.                         head_ptr->set_link( cursor );
  349.                         precursor = head_ptr;
  350.                 }
  351.                
  352.                 /*if the list is not empty and there is no current item*/
  353.                 else if (!is_item() && many_nodes) {
  354.                         cursor = new node<Item>( entry );
  355.                         tail_ptr->set_link( cursor );
  356.                         precursor = tail_ptr;
  357.                         tail_ptr = cursor;
  358.                 }
  359.                
  360.                 /*if the list is not empty and the cursor points somewhere in
  361.                         the middle(including last item)*/
  362.                 else if (is_item() && cursor != head_ptr) {
  363.                         if (cursor != tail_ptr) { // if cursor is not at last item
  364.                                 cursor = new node<Item>( entry );
  365.                         }
  366.                         else if (cursor == tail_ptr) { // if cursor is at last item
  367.                                 cursor = new node<Item>( entry );
  368.                                 tail_ptr = cursor;
  369.                         }
  370.                         cursor->set_link( (precursor->link())->link() );
  371.                         (precursor->link())->set_link( cursor );
  372.                         precursor = precursor->link();
  373.                 }
  374.                
  375.                 ++many_nodes; // increase the node count
  376.         }
  377.        
  378.         template <class Item>
  379.         void linked_list<Item>::remove_current() {
  380.                 if ( is_item() ) {
  381.                        
  382.                         /*If the cursor points to an item in the middle of the list, not tail, not head:*/
  383.                         if (cursor != head_ptr && cursor != tail_ptr) {
  384.                                 precursor->set_link( cursor->link() );
  385.                                 delete cursor;
  386.                                 cursor = precursor->link();
  387.                         }
  388.                
  389.                         /*If the cursor points to the first item in the list and that is the only item:*/
  390.                         else if (many_nodes == 1) {
  391.                                 delete cursor;
  392.                                 cursor = head_ptr = tail_ptr = precursor = NULL;
  393.                         }
  394.                        
  395.                         /*If the cursor points to the first item in the list and there is more than one item:*/
  396.                         else if ( cursor == head_ptr && many_nodes > 1) {
  397.                                 cursor = cursor->link();
  398.                                 delete head_ptr;
  399.                                 head_ptr = cursor;
  400.                         }
  401.                        
  402.                         /*If the cursor points to the last item in the list (and there is more than one item)*/
  403.                         else if ( cursor == tail_ptr && many_nodes > 1) {
  404.                                 delete cursor;
  405.                                 tail_ptr = precursor;
  406.                                 /* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
  407.                                 tail_ptr->set_link(NULL);
  408.                                 /* #!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!#!# */
  409.                                 precursor = cursor = NULL;
  410.                         }
  411.                        
  412.                         –many_nodes;
  413.                 }
  414.         }
  415.        
  416.         template <class Item>
  417.         void linked_list<Item>::operator =(const linked_list& source) {
  418.                 if (this != &source) {
  419.                         list_clear(head_ptr);
  420.                         head_ptr = tail_ptr = cursor = precursor = NULL;
  421.                         many_nodes = 0;
  422.                
  423.                         int src_size = source.size(); // to replicate cursor position
  424.                         int many_til_end = 0; // to replicate cursor position
  425.                         int many_til_mid = 0; // to replicate cursor position
  426.                         node<Item> *src_cursor = source.cursor; // to replicate cursor position
  427.                        
  428.                         list_copy(source.head_ptr, head_ptr, tail_ptr);
  429.                        
  430.                         /*replicate the size value (before cursor position because functions used for that depend on many_nodes value*/
  431.                                 many_nodes = source.many_nodes;
  432.                        
  433.                         /*replicate the cursor position*/
  434.                                 if (src_cursor != NULL) {
  435.                                         while (src_cursor != NULL) {
  436.                                                 ++many_til_end;
  437.                                                 src_cursor = src_cursor->link();
  438.                                         }
  439.                                         many_til_mid = src_size - many_til_end; // this is how many to advance to replicate cursor position.
  440.                                         start(); // put this.cursor at beginning.
  441.                                         for (int i=0; i<many_til_mid; ++i) {
  442.                                                 advance();
  443.                                         }
  444.                                         /* after the for loop, the new linked_list’s cursor should be at the same position as the source’s cursor was.*/
  445.                                 }
  446.                                 else {
  447.                                         cursor = NULL;
  448.                                         precursor = NULL;
  449.                                 }
  450.                 }
  451.         }
  452.                        
  453.         /* CONSTANT MEMBER FUNCTIONS */
  454.        
  455.         template <class Item>
  456.         typename linked_list<Item>::value_type linked_list<Item>::current() const {
  457.                 if ( is_item() ) {
  458.                         return cursor->data();
  459.                 }
  460.         }
  461.  
  462. }
This entry was posted in C++ and tagged , , , , , , . Bookmark the permalink. Trackbacks are closed, but you can post a comment.

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Why ask?