Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // linked_list.h
- #ifndef LINKED_LIST_H_INCLUDED
- #define LINKED_LIST_H_INCLUDED
- // note: implementation required for pass
- class linked_list
- {
- linked_list(linked_list &&rhs) = delete;
- linked_list(const linked_list &rhs) = delete;
- linked_list &operator=(const linked_list &rhs) = delete;
- public:
- linked_list();
- ~linked_list();
- void push_front(int value);
- void push_back(int value);
- void insert(int value, int index);
- void pop_front();
- void pop_back();
- void remove(int index);
- void clear();
- int size() const;
- int front() const;
- int back() const;
- int at(int index) const;
- private:
- struct node
- {
- node();
- explicit node(int value, node *next);
- int value_;
- node *next_;
- };
- int count_;
- node *head_;
- node *tail_;
- };
- #endif // !LINKED_LIST_H_INCLUDED
- // linked_list.cpp
- #include "linked_list.h"
- linked_list::node::node()
- : value_(0)
- , next_(nullptr)
- {
- }
- linked_list::node::node(int value, node *next)
- : value_(value)
- , next_(next)
- {
- }
- linked_list::linked_list()
- : count_(0)
- , head_(nullptr)
- , tail_(nullptr)
- {
- }
- linked_list::~linked_list()
- {
- }
- void linked_list::push_front(int value)
- {
- node* Tmp_Node;
- if (head_ != nullptr) // If the list is not empty.
- {
- Tmp_Node = head_;
- head_ = new node{ value, Tmp_Node }; // Connects the old head to the new head as the "next" node.
- count_++;
- }
- else // If the list is empty.
- {
- Tmp_Node = new node{value, nullptr };
- head_ = Tmp_Node;
- tail_ = Tmp_Node;
- count_++;
- }
- }
- void linked_list::push_back(int value)
- {
- node* Tmp_Node;
- if (tail_ != nullptr) // If the list is not empty.
- {
- Tmp_Node = new node{ value, nullptr };
- tail_->next_ = Tmp_Node;
- tail_ = Tmp_Node;
- count_++;
- }
- else // If the list is empty.
- {
- Tmp_Node = new node{ value, nullptr };
- tail_ = Tmp_Node;
- head_ = Tmp_Node;
- count_++;
- }
- }
- void linked_list::insert(int value, int index)
- {
- if (index >= 0 && index <= count_) // Validates index. (Range is 0 to tail + 1)
- {
- node* Tmp_Node;
- if (index == 0) // If index is head.
- {
- if (head_ == nullptr) // If list is empty.
- {
- Tmp_Node = new node{ value, nullptr };
- head_ = Tmp_Node;
- tail_ = Tmp_Node;
- count_++;
- return;
- }
- else // If list is not empty.
- {
- Tmp_Node = head_;
- head_ = new node{ value, Tmp_Node }; // Connects the old head to the new head as the "next" node.
- count_++;
- return;
- }
- }
- else if (index == count_) // If index is after tail.
- {
- Tmp_Node = new node{ value, nullptr };
- tail_->next_ = Tmp_Node;
- tail_ = Tmp_Node;
- count_++;
- }
- else // If index is in the middle.
- {
- node* Tmp_CurrentNode = head_;
- node* Tmp_PreviousNode = head_; // Initialized as head to avoid warnings.
- int IterationCounter = 0;
- while (IterationCounter != index)
- {
- if (IterationCounter == (index - 1)) // Captures the previous node.
- {
- Tmp_PreviousNode = Tmp_CurrentNode;
- }
- Tmp_CurrentNode = Tmp_CurrentNode->next_;
- IterationCounter++;
- }
- Tmp_Node = Tmp_CurrentNode;
- Tmp_CurrentNode = new node{ value, Tmp_Node };
- Tmp_PreviousNode->next_ = Tmp_CurrentNode;
- count_++;
- }
- }
- }
- void linked_list::pop_front()
- {
- if (count_ > 0) // If the list is not empty.
- {
- if (count_ == 1) // If the list has only 1 node.
- {
- delete head_;
- head_ = nullptr;
- tail_ = nullptr;
- count_--;
- return;
- }
- else // If the list has more than 1 node.
- {
- node* Tmp_Node;
- Tmp_Node = head_->next_;
- delete head_;
- head_ = Tmp_Node;
- count_--;
- return;
- }
- }
- }
- void linked_list::pop_back()
- {
- if (count_ > 0) // If the list is not empty.
- {
- if (count_ == 1) // If the list has 1 node.
- {
- delete tail_;
- tail_ = nullptr;
- head_ = nullptr;
- count_--;
- return;
- }
- else // If list has more than 1 node.
- {
- node* Tmp_CurrentNode = head_;
- node* Tmp_PreviousNode = head_; // Initialized as head just to avoid warnings.
- int IterationCounter = 0;
- while (Tmp_CurrentNode != tail_)
- {
- if (IterationCounter == (count_ - 2)) // Captures the before last node.
- {
- Tmp_PreviousNode = Tmp_CurrentNode;
- }
- Tmp_CurrentNode = Tmp_CurrentNode->next_;
- IterationCounter++;
- }
- delete Tmp_CurrentNode;
- Tmp_PreviousNode->next_ = nullptr;
- tail_ = Tmp_PreviousNode;
- count_--;
- return;
- }
- }
- }
- void linked_list::remove(int index)
- {
- if (index >= 0 && index < count_) // Validates if index exists in the list.
- {
- node* Tmp_Node;
- if (index == 0) // If index is head.
- {
- if (head_->next_ == nullptr) // If there is nothing after the head.
- {
- delete head_;
- head_ = nullptr;
- tail_ = nullptr;
- count_--;
- return;
- }
- else // If there is something after the head.
- {
- Tmp_Node = head_->next_;
- delete head_;
- head_ = Tmp_Node;
- count_--;
- return;
- }
- }
- node* Tmp_CurrentNode = head_;
- node* Tmp_PreviousNode = head_; // Initialized as head just to avoid warnings.
- int IterationCounter = 0;
- if (index == (count_ - 1)) // If index is tail.
- {
- while (IterationCounter != index)
- {
- if (IterationCounter == (index - 1)) // Captures the previous node.
- {
- Tmp_PreviousNode = Tmp_CurrentNode;
- }
- Tmp_CurrentNode = Tmp_CurrentNode->next_;
- IterationCounter++;
- }
- delete Tmp_CurrentNode;
- Tmp_PreviousNode->next_ = nullptr;
- tail_ = Tmp_PreviousNode;
- count_--;
- return;
- }
- else // If index is in the middle.
- {
- while (IterationCounter != index)
- {
- if (IterationCounter == (index - 1)) // Captures the previous node.
- {
- Tmp_PreviousNode = Tmp_CurrentNode;
- }
- Tmp_CurrentNode = Tmp_CurrentNode->next_;
- IterationCounter++;
- }
- Tmp_Node = Tmp_CurrentNode->next_;
- delete Tmp_CurrentNode;
- Tmp_PreviousNode->next_ = Tmp_Node;
- count_--;
- return;
- }
- }
- }
- void linked_list::clear()
- {
- if (count_ > 0) // If list is not empty.
- {
- node* Tmp_CurrentNode = head_;
- node* Tmp_NextNode = nullptr;
- while (count_ != 0)
- {
- Tmp_NextNode = Tmp_CurrentNode->next_; // Sets next node.
- delete Tmp_CurrentNode;
- count_--;
- Tmp_CurrentNode = Tmp_NextNode;
- }
- head_ = nullptr;
- tail_ = nullptr;
- }
- }
- int linked_list::size() const
- {
- return count_;
- }
- int linked_list::front() const
- {
- if (head_ != nullptr)
- {
- return head_->value_;
- }
- return -1;
- }
- int linked_list::back() const
- {
- if (tail_ != nullptr)
- {
- return tail_->value_;
- }
- return -1;
- }
- int linked_list::at(int index) const
- {
- if (index >= 0 && index <= (count_ - 1)) // Validates if index exists in the list.
- {
- node* Tmp_CurrentNode = head_;
- int IterationCounter = 0;
- while (IterationCounter != index) // Gets skipped if index is 0.
- {
- Tmp_CurrentNode = Tmp_CurrentNode->next_;
- IterationCounter++;
- }
- return Tmp_CurrentNode->value_;
- }
- return -1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement