Skip to content

Instantly share code, notes, and snippets.

@f0lie
Last active March 5, 2021 19:34
Show Gist options
  • Save f0lie/ae376ff51834479e3a139b68c3a4cbea to your computer and use it in GitHub Desktop.
Save f0lie/ae376ff51834479e3a139b68c3a4cbea to your computer and use it in GitHub Desktop.
C++11 Linked List implemented with smart pointers
// 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