Skip to content

Instantly share code, notes, and snippets.

@flisboac
Created September 27, 2016 07:52
Show Gist options
  • Save flisboac/067ad8e2783b1595357015da22550912 to your computer and use it in GitHub Desktop.
Save flisboac/067ad8e2783b1595357015da22550912 to your computer and use it in GitHub Desktop.
A header-only circular doubly-linked list implementation in C++11. Don't know exactly how I came to need and implement it in the first place, but here it is, nonetheless.
#ifndef CIRCULAR_LIST_
#define CIRCULAR_LIST_
template <typename T>
class circular_list {
private: // static members
struct node {
public: // methods
node() = default;
node(const node& rhs) = default;
node(node&& rhs) = default;
node(T value_) : _value(value_), _next(this), _prev(this) {}
~node() {
node* curr = this->_next;
while (curr != nullptr && curr != this) {
node* ptr = curr;
curr = curr->_next;
ptr->_next = nullptr;
delete ptr;
}
}
inline T& value() { return _value; }
inline node* next() const { return _next; }
inline node* previous() const { return _next; }
inline node* insert_before(const T& value) {
node* new_elem = new node(value);
new_elem->_next = this;
new_elem->_prev = this->_prev;
this->_prev->_next = new_elem;
this->_prev = new_elem;
return new_elem;
}
inline node* insert_after(const T& value) {
node* new_elem = new node(value);
new_elem->_prev = this;
new_elem->_next = this->_next;
this->_next->_prev = new_elem;
this->_next = new_elem;
return new_elem;
}
inline node* erase_head() {
node* new_head = nullptr;
if (_next != this) {
new_head = this->_next;
new_head->_prev = this->_prev;
this->_prev->_next = new_head;
this->_next = this->_prev = nullptr;
delete this;
}
return new_head;
}
inline node* erase_tail() {
node* new_tail = nullptr;
if (_prev != this) {
new_tail = this->_prev;
new_tail->_next = this->_next;
this->_next->_prev = new_tail;
this->_next = this->_prev = nullptr;
delete this;
}
return new_tail;
}
private: // methods
node* duplicate() {
node* curr = this->_next;
node* ret = new node(*this);
node* head = ret;
ret->_next = ret;
// If the assumptions do not hold at runtime, all hell will break loose
while (curr != this) {
ret->_next = new node(curr->_next);
ret->_next->_prev = ret;
ret = ret->_next;
curr = curr->_next;
}
head->_prev = ret;
}
private: // fields
node *_next = this;
node *_prev = this;
T _value = T();
};
public: // static members
class iterator {
public:
iterator() = default;
iterator(const iterator& rhs) = default;
iterator(iterator&& rhs) = default;
iterator(node* head_, bool end_ = false) : _head(head_), _curr(head_), _end(end_) {}
iterator& operator=(const iterator& rhs) = default;
iterator& operator=(iterator& rhs) = default;
T& operator*() { return _curr->value(); }
T* operator->() { return &_curr->value(); }
bool operator==(const iterator& rhs) { return this->_curr == rhs._curr && _end == rhs._end; }
bool operator!=(const iterator& rhs) { return !(*this == rhs); }
iterator operator++(int) { return ++(*this); }
iterator& operator++() {
node* next = _curr->next();
_end = next == _head;
_curr = next;
return *this;
}
iterator operator--(int) { return --(*this); }
iterator& operator--() {
_end = false;
_curr = _curr->previous();
return *this;
}
private:
node *_head = nullptr;
node *_curr = nullptr;
bool _end = false;
};
public: // methods
circular_list() = default;
circular_list(const circular_list& rhs) : _head(rhs._head.duplicate()) {}
circular_list(circular_list&& rhs) { rhs._head = _head; _head = nullptr; }
~circular_list() { delete _head; }
bool empty() const { return _head == nullptr || _tail == nullptr; }
size_t size() const { return _size; }
void clear() { delete _head; _head = nullptr; _tail = nullptr; _size = 0; }
T& front() { return _head->value(); }
T& back() { return _tail->value(); }
void push_back(const T& value) {
if (_head == nullptr) {
_head = new node(value);
_tail = _head;
} else {
_head = _head->insert_before(value);
}
++_size;
}
void push_front(const T& value) {
if (_tail == nullptr) {
_tail = new node(value);
_head = _tail;
} else {
_tail = _tail->insert_after(value);
}
--_size;
}
void pop_back() {
_head = _head->erase_head();
--_size;
if (_head == nullptr) _tail = nullptr;
}
void pop_front() {
_tail = _tail->erase_tail();
--_size;
if (_tail == nullptr) _head = nullptr;
}
iterator begin() { return empty() ? end() : iterator(_head, false); }
iterator end() { return iterator(_head, true); }
private: // fields
size_t _size = 0;
node *_head = nullptr;
node *_tail = nullptr;
};
#endif /* CIRCULAR_LIST_ */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment