Last active
March 5, 2021 19:34
-
-
Save f0lie/ae376ff51834479e3a139b68c3a4cbea to your computer and use it in GitHub Desktop.
C++11 Linked List implemented with smart pointers
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// https://gist.github.com/f0lie/ae376ff51834479e3a139b68c3a4cbea | |
#include <memory> | |
#include <exception> | |
template <typename T> | |
//class deque { | |
struct node { | |
T data; | |
// Do not use a shared pointer when a plain pointer can be used. | |
// Unique ptrs represent ownership. You can't just add them everywhere. | |
std::unique_ptr<node> next = nullptr; | |
struct node* prev = nullptr; | |
node(T data) : data(data) {}; | |
}; | |
public: | |
void push_front(T data); | |
void push_back(T data); | |
void pop_front(); | |
void pop_back(); | |
T front(); | |
T back(); | |
size_t size(); | |
bool empty(); | |
private: | |
// Root being a unique ptr means all the nodes will recursively be destoried | |
// You can do it iteratively so don't use too much of the call stack. | |
std::unique_ptr<node> head = nullptr; | |
struct node* tail = nullptr; | |
int size_int = 0; | |
}; | |
template <typename T> | |
void deque<T>::push_front(T data) { | |
auto newNode = std::make_unique<node>(data); | |
newNode->next = std::move(head); | |
head = std::move(newNode); | |
if(head->next == nullptr) { | |
tail = head.get(); | |
} | |
size_int++; | |
} | |
template <typename T> | |
void deque<T>::push_back(T data) { | |
auto newNode = std::make_unique<node>(data); | |
newNode->prev = tail; | |
if(head == nullptr) { | |
head = std::move(newNode); | |
tail = head.get(); | |
} else { | |
tail->next = std::move(newNode); | |
tail = tail->next.get(); | |
} | |
size_int++; | |
} | |
template <typename T> | |
void deque<T>::pop_front() { | |
if (head == nullptr) { | |
throw std::runtime_error("Cannot pop empty list"); | |
} | |
head = std::move(head->next); | |
size_int--; | |
} | |
template <typename T> | |
void deque<T>::pop_back() { | |
if (tail == nullptr) { | |
throw std::runtime_error("Cannot pop empty list"); | |
} | |
tail->next.reset(); | |
tail = tail->prev; | |
size_int--; | |
} | |
template <typename T> | |
T deque<T>::front() { | |
if (head == nullptr) { | |
throw std::runtime_error("Empty list"); | |
} | |
return head->data; | |
} | |
template <typename T> | |
T deque<T>::back() { | |
if (tail == nullptr) { | |
throw std::runtime_error("Empty list"); | |
} | |
return tail->data; | |
} | |
template <typename T> | |
size_t deque<T>::size() { | |
return size_int; | |
} | |
template <typename T> | |
bool deque<T>::empty() { | |
return head == nullptr; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment