ulfben

linked_list_2020_start

Nov 29th, 2020
619
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×