Created
December 4, 2014 03:51
-
-
Save dgodfrey206/5c0158901fd6018e1653 to your computer and use it in GitHub Desktop.
Circular linked list
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
#include <iostream> | |
template <class T> | |
class circular_linked_list | |
{ | |
struct node; | |
node* tail{nullptr}, **back_ptr{&tail}, **front_ptr{nullptr}; | |
int m_size{0}; | |
template <class U> | |
friend void Display(circular_linked_list<U> const&); | |
public: | |
circular_linked_list() = default; | |
circular_linked_list(int); | |
circular_linked_list(circular_linked_list const&); | |
T& front() const | |
{ | |
if (m_size == 1) | |
return tail->data; | |
if (m_size > 1) | |
return tail->next->data; | |
return tail->data; | |
} | |
T& back() const { return tail->data; } | |
int size() const { return m_size; } | |
bool empty() const { return !m_size; } | |
void push_back(T const&); | |
node* erase(T const&); | |
}; | |
template <class T> | |
struct circular_linked_list<T>::node | |
{ | |
friend class circular_linked_list<T>; | |
node(T const& data = T(), node* next = nullptr) | |
: data(data) | |
, next(next) | |
{} | |
template <class U> | |
friend void Display(circular_linked_list<U> const&); | |
private: | |
T data{0}; | |
node* next{nullptr}; | |
}; | |
template <class T> | |
circular_linked_list<T>::circular_linked_list(int size) | |
: m_size(0) | |
{ | |
while (size--) | |
push_back(0); | |
} | |
template <class T> | |
circular_linked_list<T>::circular_linked_list(circular_linked_list<T> const& other) | |
: m_size(other.m_size) | |
{ | |
for (node* pos = other.tail; pos != nullptr; pos = pos->next) | |
push_back(pos->data); | |
} | |
template <class T> | |
void circular_linked_list<T>::push_back(T const& value) | |
{ | |
node* new_last = new node{value, tail}; | |
if (empty()) | |
{ | |
tail = new_last; | |
front_ptr = &tail; | |
} | |
else | |
{ | |
if (size() == 1) | |
{ | |
tail->next = new_last; | |
tail = new_last; | |
} | |
else | |
{ | |
node* pos = tail; | |
while (pos->next != tail) | |
pos = pos->next; | |
pos->next = new_last; | |
} | |
} | |
++m_size; | |
} | |
template <class T> | |
typename circular_linked_list<T>::node* circular_linked_list<T>::erase(T const& value) | |
{ | |
node** p = &tail; | |
auto remove = [] (node** p) | |
{ | |
node* temp = *p; | |
*p = (*p)->next; | |
delete *temp; | |
}; | |
if (!*p) | |
return nullptr; | |
if ((*p)->data == value) | |
remove(p); | |
else | |
{ | |
for (p = &(*p)->next; *p != tail && (*p)->data != value; ) | |
p = &(*p)->next; | |
if ((*p)->data == value) | |
remove(p); | |
else | |
return nullptr; | |
} | |
--m_size; | |
return tail; | |
} | |
template <class T> | |
void Display(circular_linked_list<T> const& list) | |
{ | |
std::cout << list.front(); | |
//if (begin->next == list.tail) | |
// std::cout << list.tail->data; | |
} | |
int main() | |
{ | |
circular_linked_list<int> list; | |
list.push_back(1); | |
list.push_back(3); | |
Display(list); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment