ulfben

linked_list_2020_refactor (2 hours)

Nov 27th, 2020 (edited)
34
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // linked_list.h
  2.  
  3. #ifndef LINKED_LIST_H_INCLUDED
  4. #define LINKED_LIST_H_INCLUDED
  5.  
  6. // note: implementation required for pass
  7.  
  8. class linked_list
  9. {
  10.    linked_list(linked_list&& rhs) = delete;
  11.    linked_list(const linked_list& rhs) = delete;
  12.    linked_list& operator=(const linked_list &rhs) = delete;
  13.    linked_list& operator=(linked_list&& rhs) = delete;
  14.     struct node
  15.     {
  16.         node();
  17.         node(int value, node* next);
  18.  
  19.         int value_ = 0;
  20.         node* next_ = nullptr;
  21.     };
  22. public:
  23.    linked_list();
  24.    ~linked_list();
  25.  
  26.    void push_front(int value);
  27.    void push_back(int value);
  28.    void insert(int value, int index);
  29.    void pop_front();
  30.    void pop_back();
  31.    void remove(int index);
  32.    void clear();
  33.    int size() const noexcept;
  34.    int front() const noexcept;
  35.    int back() const noexcept;
  36.    int at(int index) const noexcept;
  37.    node* getNodeAt(int index) const noexcept;
  38.    bool empty() const noexcept;
  39.    bool isInRange(int index) const noexcept;
  40.  
  41. private:
  42.    int count_;
  43.    node *head_;
  44.    node *tail_;
  45. };
  46.  
  47. #endif // !LINKED_LIST_H_INCLUDED
  48.  
  49. // linked_list.cpp
  50.  
  51. #include "linked_list.h"
  52.  
  53. linked_list::node::node(int value, node *next)
  54.    : value_(value)
  55.    , next_(next)
  56. {
  57.  
  58. }
  59.  
  60. linked_list::linked_list()
  61.    : count_(0)
  62.    , head_(nullptr)
  63.    , tail_(nullptr)
  64. {
  65.  
  66. }
  67.  
  68. linked_list::~linked_list()
  69. {
  70.     clear();
  71. }
  72.  
  73. void linked_list::push_front(int value) {
  74.     head_ = new node{ value, head_ };
  75.     if (empty()){
  76.         tail_ = head_;     
  77.     }
  78.     count_++;
  79. }
  80.  
  81. void linked_list::push_back(int value) {
  82.     node* Tmp_Node = new node{ value, nullptr };
  83.     if (empty()) {     
  84.         head_ = Tmp_Node;      
  85.     }else{         
  86.         tail_->next_ = Tmp_Node;
  87.     }
  88.     tail_ = Tmp_Node;
  89.     count_++;
  90. }
  91.  
  92. void linked_list::insert(int value, int index)
  93. {
  94.     if (!(isInRange(index) || index == count_)){ //WARNING, count_ should not be valid. The test is wrong.
  95.         return;
  96.     }
  97.     if (index == 0){       
  98.         return push_front(value);
  99.     }
  100.     if (index == count_) { // If index is after tail. TODO: probably a logic error.    
  101.         return push_back(value);
  102.     }  
  103.     node* infront = getNodeAt(index - 1);
  104.     node* after = infront->next_;
  105.     infront->next_ = new node{ value, after }; 
  106.     count_++;      
  107. }
  108.  
  109. void linked_list::pop_front()
  110. {
  111.     if (empty()) {
  112.         return; //TODO: do we want pop_front on empty containers to be allowed? consider exceptions
  113.     }
  114.     if (count_ == 1) // If the list has only 1 node.
  115.     {
  116.         delete head_;
  117.         head_ = nullptr;
  118.         tail_ = nullptr;
  119.         count_--;
  120.         return;
  121.     }
  122.     else // If the list has more than 1 node.
  123.     {
  124.         node* Tmp_Node;
  125.         Tmp_Node = head_->next_;
  126.         delete head_;
  127.         head_ = Tmp_Node;
  128.         count_--;
  129.         return;
  130.     }
  131.    
  132. }
  133.  
  134. void linked_list::pop_back(){
  135.     if (empty()) {
  136.         return;//TODO: pop back on empty should be undefined behavior
  137.     }  
  138.     /*node* secondToLast = getNodeAt(size() - 1);  
  139.     delete tail_;
  140.     secondToLast->next_ = nullptr;
  141.     tail_ = secondToLast;
  142.     count_--;
  143.     if (empty()) {
  144.         head_ = nullptr;
  145.         tail_ = nullptr;
  146.     }*/
  147.     if (count_ == 1) // If the list has 1 node.
  148.     {
  149.         delete tail_;
  150.         tail_ = nullptr;
  151.         head_ = nullptr;
  152.         count_--;
  153.         return;
  154.     }
  155.     else // If list has more than 1 node.
  156.     {
  157.         node* Tmp_CurrentNode = head_;
  158.         node* Tmp_PreviousNode = head_; // Initialized as head just to avoid warnings.
  159.         int IterationCounter = 0;
  160.  
  161.         while (Tmp_CurrentNode != tail_)
  162.         {
  163.             if (IterationCounter == (count_ - 2)) // Captures the before last node.
  164.             {
  165.                 Tmp_PreviousNode = Tmp_CurrentNode;
  166.             }
  167.  
  168.             Tmp_CurrentNode = Tmp_CurrentNode->next_;
  169.             IterationCounter++;
  170.         }
  171.  
  172.         delete Tmp_CurrentNode;
  173.         Tmp_PreviousNode->next_ = nullptr;
  174.         tail_ = Tmp_PreviousNode;
  175.         count_--;
  176.         return;
  177.     }
  178. }
  179.  
  180. void linked_list::remove(int index)
  181. {
  182.     if (isInRange(index)) // Validates if index exists in the list.
  183.     {
  184.         node* Tmp_Node;
  185.  
  186.         if (index == 0) // If index is head.
  187.         {
  188.             if (head_->next_ == nullptr) // If there is nothing after the head.
  189.             {
  190.                 delete head_;
  191.                 head_ = nullptr;
  192.                 tail_ = nullptr;
  193.                 count_--;
  194.                 return;
  195.             }
  196.             else // If there is something after the head.
  197.             {
  198.                 Tmp_Node = head_->next_;
  199.                 delete head_;
  200.                 head_ = Tmp_Node;
  201.                 count_--;
  202.                 return;
  203.             }
  204.         }
  205.  
  206.         node* Tmp_CurrentNode = head_;
  207.         node* Tmp_PreviousNode = head_; // Initialized as head just to avoid warnings.
  208.         int IterationCounter = 0;
  209.  
  210.         if (index == (count_ - 1)) // If index is tail.
  211.         {
  212.             while (IterationCounter != index)
  213.             {
  214.                 if (IterationCounter == (index - 1)) // Captures the previous node.
  215.                 {
  216.                     Tmp_PreviousNode = Tmp_CurrentNode;
  217.                 }
  218.  
  219.                 Tmp_CurrentNode = Tmp_CurrentNode->next_;
  220.                 IterationCounter++;
  221.             }
  222.  
  223.             delete Tmp_CurrentNode;
  224.             Tmp_PreviousNode->next_ = nullptr;
  225.             tail_ = Tmp_PreviousNode;
  226.             count_--;
  227.             return;
  228.         }
  229.         else // If index is in the middle.
  230.         {
  231.             while (IterationCounter != index)
  232.             {
  233.                 if (IterationCounter == (index - 1)) // Captures the previous node.
  234.                 {
  235.                     Tmp_PreviousNode = Tmp_CurrentNode;
  236.                 }
  237.  
  238.                 Tmp_CurrentNode = Tmp_CurrentNode->next_;
  239.                 IterationCounter++;
  240.             }
  241.  
  242.             Tmp_Node = Tmp_CurrentNode->next_;
  243.             delete Tmp_CurrentNode;
  244.             Tmp_PreviousNode->next_ = Tmp_Node;
  245.             count_--;
  246.             return;
  247.         }
  248.     }
  249. }
  250.  
  251. void linked_list::clear(){ 
  252.     while (!empty()) {
  253.         pop_back(); //assumes pop_back assigns nullptr to members when empty
  254.     }
  255. }
  256.  
  257. int linked_list::size() const noexcept {
  258.    return count_;
  259. }
  260.  
  261. int linked_list::front() const noexcept {
  262.     if (head_ == nullptr){
  263.         return -1;  //WARNING: error sentinel value is a valid int value.  
  264.     }
  265.     return head_->value_;
  266. }
  267.  
  268. int linked_list::back() const noexcept {
  269.     if (tail_ == nullptr){
  270.         return -1;  //WARNING: error sentinel value is a valid int value.  
  271.     }
  272.     return tail_->value_;  
  273. }
  274.  
  275. int linked_list::at(int index) const noexcept {
  276.     if (!isInRange(index)) {       
  277.         return -1; //WARNING: error sentinel value is a valid value.       
  278.         //invalid indexes should perhaps throw an exception, or assert.
  279.     }
  280.     node* tmp = getNodeAt(index);
  281.     return tmp ? tmp->value_ : -1;
  282. }
  283.  
  284. linked_list::node* linked_list::getNodeAt(int index) const noexcept {
  285.     if (!isInRange(index)) {
  286.         return nullptr;
  287.     }
  288.     node* temp = head_;
  289.     for (int i = 0; i < index && temp->next_; i++) {
  290.         temp = temp->next_;
  291.     }
  292.     return temp;
  293. }
  294.  
  295. bool linked_list::empty() const noexcept{
  296.     return count_ <= 0; //TODO: change count_ to std::size_t
  297. }
  298.  
  299. bool linked_list::isInRange(int index) const noexcept{
  300.     return !empty() && index > -1 && index < size();       
  301. }
  302.  
RAW Paste Data