Skip to content

Instantly share code, notes, and snippets.

@ryanwarsaw ryanwarsaw/list.h
Created Apr 26, 2018

Embed
What would you like to do?
#ifndef LINKED_LIST_LIST_H_
#define LINKED_LIST_LIST_H_
#include <stdexcept>
#include <ostream>
using namespace std;
template<class T>
class Node {
public:
Node();
Node(const T&, Node *, Node *);
T data_;
Node *next_;
Node *previous_;
};
template<class T>
inline Node<T>::Node()
{
this->next_ = 0;
this->previous_ = 0;
this->data_ = NULL;
}
template<class T>
inline Node<T>::Node(const T &element, Node *next, Node *previous) {
this->data_ = element;
this->next_ = next;
this->previous_ = previous;
}
template<class T>
class List {
private:
int size_;
public:
List();
~List();
bool IsEmpty() const;
int size() const;
void AddToFront(const T&);
void AddToEnd(const T&);
void AddBeforeNode(const T&, Node<T> *);
T DeleteFromFront();
Node<T>* PeekHead();
Node<T> *head_;
Node<T> *tail_;
protected:
friend ostream& operator<<(ostream& out, const List<T>& list) {
Node<T> *temp = list.head_;
while (temp != nullptr) {
out << temp->data_ << ' ';
temp = temp->next_;
}
return out;
}
};
template<class T>
inline List<T>::List() {
this->size_ = 0;
this->head_ = nullptr;
this->tail_ = nullptr;
}
template<class T>
inline List<T>::~List() {
Node<T> *temp;
while (this->head_ != nullptr) {
temp = this->head_;
this->head_ = this->head_->next_;
delete temp;
}
this->size_ = 0;
}
template<class T>
inline bool List<T>::IsEmpty() const {
return this->size() == 0;
}
template<class T>
inline int List<T>::size() const {
return this->size_;
}
template<class T>
void List<T>::AddToFront(const T &element) {
if (this->IsEmpty()) {
this->head_ = this->tail_ = new Node<T>(element, nullptr, nullptr);
} else {
// step 1 and 2!
this->head_ = new Node<T>(element, this->head_, nullptr);
// step 3 (remove the nullptr from the old head.
this->head_->next_->previous_ = this->head_;
}
this->size_++;
}
template<class T>
inline void List<T>::AddToEnd(const T &element) {
if (this->IsEmpty()) {
this->tail_ = this->head_ = new Node<T>(element, nullptr, nullptr);
} else {
this->tail_ = new Node<T>(element, nullptr, this->tail_);
this->tail_->previous_->next_ = this->tail_;
}
this->size_++;
}
template<class T>
inline T List<T>::DeleteFromFront() {
if (!this->IsEmpty()) {
T data = this->head_->data_;
if (this->size() == 1) {
// head and tail are the same.
delete this->head_;
this->head_ = this->tail_ = nullptr;
} else {
// we must have more than 1 element.
this->head_ = this->head_->next_;
delete this->head_->previous_;
this->head_->previous_ = nullptr;
}
this->size_--;
return data;
} // else, Empty list DoNothing();
throw std::out_of_range("List is empty!");
}
template<class T>
inline Node<T>* List<T>::PeekHead() {
if (!this->IsEmpty()) {
return this->head_;
} // else, the list is empty DoNothing();
throw std::out_of_range("List is empty!");
}
template<class T>
void List<T>::AddBeforeNode(const T &element, Node<T> *node) {
if (node != nullptr) {
auto *new_node = new Node<T>(element, node, node->previous_);
// Need to update the head, since this is a new head node.
if (node->previous_ == nullptr) {
node->previous_ = new_node;
this->head_ = new_node;
} else {
// else, it's just a regular node and we update both node links.
node->previous_->next_ = new_node;
node->previous_ = new_node;
}
this->size_++;
} else {
throw std::out_of_range("Can't add a node before a non-existent Node.");
}
}
#endif
#ifndef LINKED_LIST_QUEUE_H_
#define LINKED_LIST_QUEUE_H_
#include <stdexcept>
#include "list.h"
template<typename T>
class PriorityQueue {
private:
List<T> *data_;
public:
PriorityQueue();
~PriorityQueue();
bool IsEmpty();
void Enqueue(const T&);
T Dequeue();
T Front();
};
template<typename T>
inline PriorityQueue<T>::PriorityQueue() {
this->data_ = new List<T>;
}
template<typename T>
inline PriorityQueue<T>::~PriorityQueue() {
delete this->data_;
}
template<typename T>
inline bool PriorityQueue<T>::IsEmpty() {
return this->data_->IsEmpty();
}
template<typename T>
inline void PriorityQueue<T>::Enqueue(const T &element) {
if (this->data_->IsEmpty()) {
this->data_->AddToEnd(element);
} else {
Node<T> *node = this->data_->PeekHead();
// Iterate through each of the elements in the Queue
while (node != nullptr) {
// Only consider adding an element if it doesn't exist.
if (node->data_ != element) {
if (element < node->data_) {
this->data_->AddBeforeNode(element, node);
return;
}
} else return; // the element already exists in the PriorityQueue, StopLoop();
node = node->next_;
}
}
}
template<typename T>
inline T PriorityQueue<T>::Dequeue() {
if (!this->IsEmpty()) {
return this->data_->DeleteFromFront();
} // else, the queue is empty, DoNothing();
throw std::out_of_range("PriorityQueue is empty");
}
template<typename T>
inline T PriorityQueue<T>::Front() {
if (!this->IsEmpty()) {
return this->data_->PeekHead();
} // else, the queue is empty, DoNothing();
throw std::out_of_range("PriorityQueue is empty");
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.