ulfben

linked_list_2020_start

Nov 29th, 2020
580
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.  
  14. public:
  15.    linked_list();
  16.    ~linked_list();
  17.  
  18.    void push_front(int value);
  19.    void push_back(int value);
  20.    void insert(int value, int index);
  21.    void pop_front();
  22.    void pop_back();
  23.    void remove(int index);
  24.    void clear();
  25.    int size() const;
  26.    int front() const;
  27.    int back() const;
  28.    int at(int index) const;
  29.  
  30. private:
  31.    struct node
  32.    {
  33.       node();
  34.       explicit node(int value, node *next);
  35.  
  36.       int value_;
  37.       node *next_;
  38.    };
  39.  
  40.    int count_;
  41.    node *head_;
  42.    node *tail_;
  43. };
  44.  
  45. #endif // !LINKED_LIST_H_INCLUDED
  46.  
  47. // linked_list.cpp
  48.  
  49. #include "linked_list.h"
  50.  
  51. linked_list::node::node()
  52.    : value_(0)
  53.    , next_(nullptr)
  54. {
  55.  
  56. }
  57.  
  58. linked_list::node::node(int value, node *next)
  59.    : value_(value)
  60.    , next_(next)
  61. {
  62.  
  63. }
  64.  
  65. linked_list::linked_list()
  66.    : count_(0)
  67.    , head_(nullptr)
  68.    , tail_(nullptr)
  69. {
  70.  
  71. }
  72.  
  73. linked_list::~linked_list()
  74. {
  75.  
  76. }
  77.  
  78. void linked_list::push_front(int value)
  79. {
  80.     node* Tmp_Node;
  81.  
  82.     if (head_ != nullptr) // If the list is not empty.
  83.     {
  84.         Tmp_Node = head_;
  85.         head_ = new node{ value, Tmp_Node }; // Connects the old head to the new head as the "next" node.
  86.         count_++;
  87.     }
  88.     else // If the list is empty.
  89.     {
  90.         Tmp_Node = new node{value, nullptr };
  91.         head_ = Tmp_Node;
  92.         tail_ = Tmp_Node;
  93.         count_++;
  94.     }
  95. }
  96.  
  97. void linked_list::push_back(int value)
  98. {
  99.     node* Tmp_Node;
  100.  
  101.     if (tail_ != nullptr) // If the list is not empty.
  102.     {
  103.         Tmp_Node = new node{ value, nullptr };
  104.         tail_->next_ = Tmp_Node;
  105.         tail_ = Tmp_Node;
  106.         count_++;
  107.     }
  108.     else // If the list is empty.
  109.     {
  110.         Tmp_Node = new node{ value, nullptr };
  111.         tail_ = Tmp_Node;
  112.         head_ = Tmp_Node;
  113.         count_++;
  114.     }
  115. }
  116.  
  117. void linked_list::insert(int value, int index)
  118. {
  119.     if (index >= 0 && index <= count_) // Validates index. (Range is 0 to tail + 1)
  120.     {
  121.         node* Tmp_Node;
  122.  
  123.         if (index == 0) // If index is head.
  124.         {
  125.             if (head_ == nullptr) // If list is empty.
  126.             {
  127.                 Tmp_Node = new node{ value, nullptr };
  128.                 head_ = Tmp_Node;
  129.                 tail_ = Tmp_Node;
  130.                 count_++;
  131.                 return;
  132.             }
  133.             else // If list is not empty.
  134.             {
  135.                 Tmp_Node = head_;
  136.                 head_ = new node{ value, Tmp_Node }; // Connects the old head to the new head as the "next" node.
  137.                 count_++;
  138.                 return;
  139.             }
  140.         }
  141.         else if (index == count_) // If index is after tail.
  142.         {
  143.             Tmp_Node = new node{ value, nullptr };
  144.             tail_->next_ = Tmp_Node;
  145.             tail_ = Tmp_Node;
  146.             count_++;
  147.         }
  148.         else // If index is in the middle.
  149.         {
  150.             node* Tmp_CurrentNode = head_;
  151.             node* Tmp_PreviousNode = head_; // Initialized as head to avoid warnings.
  152.             int IterationCounter = 0;
  153.  
  154.             while (IterationCounter != index)
  155.             {
  156.                 if (IterationCounter == (index - 1)) // Captures the previous node.
  157.                 {
  158.                     Tmp_PreviousNode = Tmp_CurrentNode;
  159.                 }
  160.  
  161.                 Tmp_CurrentNode = Tmp_CurrentNode->next_;
  162.                 IterationCounter++;
  163.             }
  164.  
  165.             Tmp_Node = Tmp_CurrentNode;
  166.             Tmp_CurrentNode = new node{ value, Tmp_Node };
  167.             Tmp_PreviousNode->next_ = Tmp_CurrentNode;
  168.             count_++;
  169.         }
  170.     }
  171. }
  172.  
  173. void linked_list::pop_front()
  174. {
  175.     if (count_ > 0) // If the list is not empty.
  176.     {  
  177.         if (count_ == 1) // If the list has only 1 node.
  178.         {
  179.             delete head_;
  180.             head_ = nullptr;
  181.             tail_ = nullptr;
  182.             count_--;
  183.             return;
  184.         }
  185.         else // If the list has more than 1 node.
  186.         {
  187.             node* Tmp_Node;
  188.             Tmp_Node = head_->next_;
  189.             delete head_;
  190.             head_ = Tmp_Node;
  191.             count_--;
  192.             return;
  193.         }
  194.     }
  195. }
  196.  
  197. void linked_list::pop_back()
  198. {
  199.     if (count_ > 0) // If the list is not empty.
  200.     {
  201.         if (count_ == 1) // If the list has 1 node.
  202.         {
  203.             delete tail_;
  204.             tail_ = nullptr;
  205.             head_ = nullptr;
  206.             count_--;
  207.             return;
  208.         }
  209.         else // If list has more than 1 node.
  210.         {
  211.             node* Tmp_CurrentNode = head_;
  212.             node* Tmp_PreviousNode = head_; // Initialized as head just to avoid warnings.
  213.             int IterationCounter = 0;
  214.  
  215.             while (Tmp_CurrentNode != tail_)
  216.             {
  217.                 if (IterationCounter == (count_ - 2)) // Captures the before last node.
  218.                 {
  219.                     Tmp_PreviousNode = Tmp_CurrentNode;
  220.                 }
  221.  
  222.                 Tmp_CurrentNode = Tmp_CurrentNode->next_;
  223.                 IterationCounter++;
  224.             }
  225.  
  226.             delete Tmp_CurrentNode;
  227.             Tmp_PreviousNode->next_ = nullptr;
  228.             tail_ = Tmp_PreviousNode;
  229.             count_--;
  230.             return;
  231.         }
  232.     }
  233. }
  234.  
  235. void linked_list::remove(int index)
  236. {
  237.     if (index >= 0 && index < count_) // Validates if index exists in the list.
  238.     {
  239.         node* Tmp_Node;
  240.  
  241.         if (index == 0) // If index is head.
  242.         {
  243.             if (head_->next_ == nullptr) // If there is nothing after the head.
  244.             {
  245.                 delete head_;
  246.                 head_ = nullptr;
  247.                 tail_ = nullptr;
  248.                 count_--;
  249.                 return;
  250.             }
  251.             else // If there is something after the head.
  252.             {
  253.                 Tmp_Node = head_->next_;
  254.                 delete head_;
  255.                 head_ = Tmp_Node;
  256.                 count_--;
  257.                 return;
  258.             }
  259.         }
  260.  
  261.         node* Tmp_CurrentNode = head_;
  262.         node* Tmp_PreviousNode = head_; // Initialized as head just to avoid warnings.
  263.         int IterationCounter = 0;
  264.  
  265.         if (index == (count_ - 1)) // If index is tail.
  266.         {
  267.             while (IterationCounter != index)
  268.             {
  269.                 if (IterationCounter == (index - 1)) // Captures the previous node.
  270.                 {
  271.                     Tmp_PreviousNode = Tmp_CurrentNode;
  272.                 }
  273.  
  274.                 Tmp_CurrentNode = Tmp_CurrentNode->next_;
  275.                 IterationCounter++;
  276.             }
  277.  
  278.             delete Tmp_CurrentNode;
  279.             Tmp_PreviousNode->next_ = nullptr;
  280.             tail_ = Tmp_PreviousNode;
  281.             count_--;
  282.             return;
  283.         }
  284.         else // If index is in the middle.
  285.         {
  286.             while (IterationCounter != index)
  287.             {
  288.                 if (IterationCounter == (index - 1)) // Captures the previous node.
  289.                 {
  290.                     Tmp_PreviousNode = Tmp_CurrentNode;
  291.                 }
  292.  
  293.                 Tmp_CurrentNode = Tmp_CurrentNode->next_;
  294.                 IterationCounter++;
  295.             }
  296.  
  297.             Tmp_Node = Tmp_CurrentNode->next_;
  298.             delete Tmp_CurrentNode;
  299.             Tmp_PreviousNode->next_ = Tmp_Node;
  300.             count_--;
  301.             return;
  302.         }
  303.     }
  304. }
  305.  
  306. void linked_list::clear()
  307. {
  308.     if (count_ > 0) // If list is not empty.
  309.     {
  310.         node* Tmp_CurrentNode = head_;
  311.         node* Tmp_NextNode = nullptr;
  312.  
  313.         while (count_ != 0)
  314.         {
  315.             Tmp_NextNode = Tmp_CurrentNode->next_; // Sets next node.
  316.             delete Tmp_CurrentNode;
  317.             count_--;
  318.             Tmp_CurrentNode = Tmp_NextNode;
  319.         }
  320.         head_ = nullptr;
  321.         tail_ = nullptr;
  322.     }
  323. }
  324.  
  325. int linked_list::size() const
  326. {
  327.    return count_;
  328. }
  329.  
  330. int linked_list::front() const
  331. {
  332.     if (head_ != nullptr)
  333.     {
  334.         return head_->value_;
  335.     }
  336.  
  337.     return -1;
  338. }
  339.  
  340. int linked_list::back() const
  341. {
  342.     if (tail_ != nullptr)
  343.     {
  344.         return tail_->value_;
  345.     }
  346.  
  347.     return -1;
  348. }
  349.  
  350. int linked_list::at(int index) const
  351. {
  352.     if (index >= 0 && index <= (count_ - 1)) // Validates if index exists in the list.
  353.     {
  354.         node* Tmp_CurrentNode = head_;
  355.         int IterationCounter = 0;
  356.  
  357.         while (IterationCounter != index) // Gets skipped if index is 0.
  358.         {
  359.             Tmp_CurrentNode = Tmp_CurrentNode->next_;
  360.             IterationCounter++;
  361.         }
  362.         return Tmp_CurrentNode->value_;
  363.     }
  364.  
  365.     return -1;
  366. }
  367.  
RAW Paste Data